/export/starexec/sandbox/solver/bin/starexec_run_c /export/starexec/sandbox/benchmark/theBenchmark.c /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.c # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given C Problem could be proven: (0) C Problem (1) CToLLVMProof [EQUIVALENT, 175 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 2539 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 3 ms] (6) LLVM Symbolic Execution SCC (7) SCC2IRS [SOUND, 124 ms] (8) IntTRS (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] (10) IntTRS (11) CaseAnalysis [EQUIVALENT, 29 ms] (12) AND (13) IntTRS (14) TerminationGraphProcessor [EQUIVALENT, 8 ms] (15) YES (16) IntTRS (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] (18) IntTRS (19) RankingReductionPairProof [EQUIVALENT, 0 ms] (20) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. ---------------------------------------- (2) Obligation: LLVM Problem Aliases: Data layout: "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" Machine: "x86_64-pc-linux-gnu" Type definitions: Global variables: Function declarations and definitions: *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %x = alloca i32, align 4 %y = alloca i32, align 4 %z = alloca i32, align 4 store 0, %1 %2 = call i32 @__VERIFIER_nondet_int() store %2, %x %3 = call i32 @__VERIFIER_nondet_int() store %3, %y %4 = call i32 @__VERIFIER_nondet_int() store %4, %z %5 = call i32 @random() %6 = call i32 @random() Unnamed Call-Instruction = call BasicVoidType @loop(i32 %5, i32 %6) %7 = load %1 ret %7 *BasicFunctionTypename: "loop" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: (a i32, b i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %2 = alloca i32, align 4 %r = alloca i32, align 4 store %a, %1 store %b, %2 %3 = load %2 %4 = icmp sgt %3 0 br %4, %5, %17 5: %6 = call i32 @random() store %6, %r %7 = load %1 %8 = sub %7 1 %9 = load %r %10 = sub %8 %9 store %10, %2 %11 = load %1 %12 = sub %11 1 %13 = load %r %14 = sub %12 %13 store %14, %1 %15 = load %1 %16 = load %2 Unnamed Call-Instruction = call BasicVoidType @loop(i32 %15, i32 %16) br %17 17: ret void *BasicFunctionTypename: "random" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %x = alloca i32, align 4 %2 = call i32 @__VERIFIER_nondet_int() store %2, %x %3 = load %x %4 = icmp slt %3 0 br %4, %5, %8 5: %6 = load %x %7 = sub 0 %6 store %7, %1 br %10 8: %9 = load %x store %9, %1 br %10 10: %11 = load %1 ret %11 Analyze Termination of all function calls matching the pattern: main() ---------------------------------------- (3) LLVMToTerminationGraphProof (EQUIVALENT) Constructed symbolic execution graph for LLVM program and proved memory safety. ---------------------------------------- (4) Obligation: SE Graph ---------------------------------------- (5) SymbolicExecutionGraphToSCCProof (SOUND) Splitted symbolic execution graph to 1 SCC. ---------------------------------------- (6) Obligation: SCC ---------------------------------------- (7) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 64 rulesP rules: f_310(v184, v185, v186, v187, 3, 1, 4) -> f_311(v184, v185, v186, v188, v187, v189, 3, 1, 4) :|: 1 <= v188 && v189 = 3 + v188 && 4 <= v189 f_311(v184, v185, v186, v188, v187, v189, 3, 1, 4) -> f_312(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) :|: 1 <= v190 && v191 = 3 + v190 && 4 <= v191 f_312(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) -> f_313(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) :|: TRUE f_313(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) -> f_314(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) :|: TRUE f_314(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) -> f_315(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) :|: 0 = 0 f_315(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) -> f_316(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) :|: 0 < v185 f_316(v184, v185, v186, v188, v190, v187, v189, v191, 3, 1, 4) -> f_318(v184, v185, v186, v188, v190, 1, v187, v189, v191, 3, 4) :|: 0 = 0 f_318(v184, v185, v186, v188, v190, 1, v187, v189, v191, 3, 4) -> f_320(v184, v185, v186, v188, v190, 1, v187, v189, v191, 3, 4) :|: TRUE f_320(v184, v185, v186, v188, v190, 1, v187, v189, v191, 3, 4) -> f_322(v186, v187, v188, v189, v190, v191, v184, v185, 1, 3, 4) :|: TRUE f_322(v186, v187, v188, v189, v190, v191, v184, v185, 1, 3, 4) -> f_325(v210, v186, v187, v188, v189, v190, v191, v211, v184, v185, 1, 3, 4) :|: 1 <= v210 && v211 = 3 + v210 && 4 <= v211 f_325(v210, v186, v187, v188, v189, v190, v191, v211, v184, v185, 1, 3, 4) -> f_327(v210, v212, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: 1 <= v212 && v213 = 3 + v212 && 4 <= v213 f_327(v210, v212, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_329(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: TRUE f_329(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_330(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: TRUE f_330(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_331(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: 0 = 0 f_331(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_332(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4, 0) :|: v214 < 0 f_331(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_333(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4, 0) :|: 0 <= v214 f_332(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4, 0) -> f_334(v210, v212, v214, 1, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 4, 0) :|: 0 = 0 f_334(v210, v212, v214, 1, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 4, 0) -> f_336(v210, v212, v214, 1, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 4, 0) :|: TRUE f_336(v210, v212, v214, 1, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 4, 0) -> f_338(v210, v212, v214, 1, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 4, 0) :|: 0 = 0 f_338(v210, v212, v214, 1, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 4, 0) -> f_340(v210, v212, v214, 1, v224, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 0, 4) :|: v224 + v214 = 0 && 1 <= v224 f_340(v210, v212, v214, 1, v224, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 0, 4) -> f_342(v210, v212, v214, 1, v224, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 0, 4) :|: TRUE f_342(v210, v212, v214, 1, v224, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 0, 4) -> f_344(v210, v212, v214, 1, v224, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 0, 4) :|: TRUE f_344(v210, v212, v214, 1, v224, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 0, 4) -> f_346(v210, v212, v214, 1, v224, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 0, 4) :|: 0 = 0 f_346(v210, v212, v214, 1, v224, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 3, 0, 4) -> f_348(v184, v185, v186, v188, v190, 1, v224, v187, v189, v191, 3, 4) :|: 0 = 0 f_348(v184, v185, v186, v188, v190, 1, v224, v187, v189, v191, 3, 4) -> f_350(v184, v185, v186, v188, v190, 1, v224, v187, v189, v191, 3, 4) :|: TRUE f_350(v184, v185, v186, v188, v190, 1, v224, v187, v189, v191, 3, 4) -> f_352(v184, v185, v186, v188, v190, 1, v224, v187, v189, v191, 3, 4) :|: 0 = 0 f_352(v184, v185, v186, v188, v190, 1, v224, v187, v189, v191, 3, 4) -> f_354(v184, v185, v186, v188, v190, 1, v224, v252, v187, v189, v191, 3, 4) :|: 1 + v252 = v184 f_354(v184, v185, v186, v188, v190, 1, v224, v252, v187, v189, v191, 3, 4) -> f_356(v184, v185, v186, v188, v190, 1, v224, v252, v187, v189, v191, 3, 4) :|: 0 = 0 f_356(v184, v185, v186, v188, v190, 1, v224, v252, v187, v189, v191, 3, 4) -> f_358(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) :|: v254 + v224 = v252 f_358(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) -> f_360(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) :|: TRUE f_360(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) -> f_362(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) :|: 0 = 0 f_362(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) -> f_364(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) :|: 1 + v252 = v184 f_364(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) -> f_366(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) :|: 0 = 0 f_366(v184, v185, v186, v188, v190, 1, v224, v252, v254, v187, v189, v191, 3, 4) -> f_368(v184, v185, v186, v188, v190, 1, v224, v252, v258, v187, v189, v191, 3, 4) :|: v258 + v224 = v252 && v254 = v258 f_368(v184, v185, v186, v188, v190, 1, v224, v252, v258, v187, v189, v191, 3, 4) -> f_370(v184, v185, v186, v188, v190, 1, v224, v252, v258, v187, v189, v191, 3, 4) :|: TRUE f_370(v184, v185, v186, v188, v190, 1, v224, v252, v258, v187, v189, v191, 3, 4) -> f_372(v184, v185, v186, v188, v190, 1, v224, v252, v258, v187, v189, v191, 3, 4) :|: 0 = 0 f_372(v184, v185, v186, v188, v190, 1, v224, v252, v258, v187, v189, v191, 3, 4) -> f_374(v184, v185, v186, v188, v190, 1, v224, v252, v258, v187, v189, v191, 3, 4) :|: 0 = 0 f_374(v184, v185, v186, v188, v190, 1, v224, v252, v258, v187, v189, v191, 3, 4) -> f_376(v258, v186, v187, v188, v189, v190, v191, v224, v184, v185, 1, v252, 3, 4) :|: 0 = 0 f_376(v258, v186, v187, v188, v189, v190, v191, v224, v184, v185, 1, v252, 3, 4) -> f_378(v258, v186, v187, v188, v189, v190, v191, v224, 3, 1, 4) :|: TRUE f_378(v258, v186, v187, v188, v189, v190, v191, v224, 3, 1, 4) -> f_309(v258, v258) :|: TRUE f_309(v184, v185) -> f_310(v184, v185, v186, v187, 3, 1, 4) :|: 1 <= v186 && v187 = 3 + v186 && 4 <= v187 f_333(v210, v212, v214, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4, 0) -> f_335(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: 0 = 0 f_335(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_337(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: TRUE f_337(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_339(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: 0 = 0 f_339(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_341(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: TRUE f_341(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_343(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: TRUE f_343(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_345(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) :|: 0 = 0 f_345(v210, v212, v214, 0, v186, v187, v188, v189, v190, v191, v211, v213, v184, v185, 1, 3, 4) -> f_347(v184, v185, v186, v188, v190, 1, v214, v187, v189, v191, 3, 4, 0) :|: 0 = 0 f_347(v184, v185, v186, v188, v190, 1, v214, v187, v189, v191, 3, 4, 0) -> f_349(v184, v185, v186, v188, v190, 1, v214, v187, v189, v191, 3, 4, 0) :|: TRUE f_349(v184, v185, v186, v188, v190, 1, v214, v187, v189, v191, 3, 4, 0) -> f_351(v184, v185, v186, v188, v190, 1, v214, v187, v189, v191, 3, 4, 0) :|: 0 = 0 f_351(v184, v185, v186, v188, v190, 1, v214, v187, v189, v191, 3, 4, 0) -> f_353(v184, v185, v186, v188, v190, 1, v214, v251, v187, v189, v191, 3, 4, 0) :|: 1 + v251 = v184 f_353(v184, v185, v186, v188, v190, 1, v214, v251, v187, v189, v191, 3, 4, 0) -> f_355(v184, v185, v186, v188, v190, 1, v214, v251, v187, v189, v191, 3, 4, 0) :|: 0 = 0 f_355(v184, v185, v186, v188, v190, 1, v214, v251, v187, v189, v191, 3, 4, 0) -> f_357(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) :|: v253 + v214 = v251 f_357(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) -> f_359(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) :|: TRUE f_359(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) -> f_361(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) :|: 0 = 0 f_361(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) -> f_363(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) :|: 1 + v251 = v184 f_363(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) -> f_365(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) :|: 0 = 0 f_365(v184, v185, v186, v188, v190, 1, v214, v251, v253, v187, v189, v191, 3, 4, 0) -> f_367(v184, v185, v186, v188, v190, 1, v214, v251, v257, v187, v189, v191, 3, 4, 0) :|: v257 + v214 = v251 && v253 = v257 f_367(v184, v185, v186, v188, v190, 1, v214, v251, v257, v187, v189, v191, 3, 4, 0) -> f_369(v184, v185, v186, v188, v190, 1, v214, v251, v257, v187, v189, v191, 3, 4, 0) :|: TRUE f_369(v184, v185, v186, v188, v190, 1, v214, v251, v257, v187, v189, v191, 3, 4, 0) -> f_371(v184, v185, v186, v188, v190, 1, v214, v251, v257, v187, v189, v191, 3, 4, 0) :|: 0 = 0 f_371(v184, v185, v186, v188, v190, 1, v214, v251, v257, v187, v189, v191, 3, 4, 0) -> f_373(v184, v185, v186, v188, v190, 1, v214, v251, v257, v187, v189, v191, 3, 4, 0) :|: 0 = 0 f_373(v184, v185, v186, v188, v190, 1, v214, v251, v257, v187, v189, v191, 3, 4, 0) -> f_375(v257, v186, v187, v188, v189, v190, v191, v214, v184, v185, 1, v251, 3, 4, 0) :|: 0 = 0 f_375(v257, v186, v187, v188, v189, v190, v191, v214, v184, v185, 1, v251, 3, 4, 0) -> f_377(v257, v186, v187, v188, v189, v190, v191, v214, 3, 1, 4, 0) :|: TRUE f_377(v257, v186, v187, v188, v189, v190, v191, v214, 3, 1, 4, 0) -> f_309(v257, v257) :|: TRUE Combined rules. Obtained 2 rulesP rules: f_310(1 + (v253:0 + v214:0), v185:0, v186:0, v187:0, 3, 1, 4) -> f_310(v253:0, v253:0, v186:1, 3 + v186:1, 3, 1, 4) :|: v190:0 > 0 && v188:0 > 0 && v185:0 > 0 && v210:0 > 0 && v212:0 > 0 && v214:0 > -1 && v186:1 > 0 f_310(1 + (v254:0 + v224:0), v185:0, v186:0, v187:0, 3, 1, 4) -> f_310(v254:0, v254:0, v186:1, 3 + v186:1, 3, 1, 4) :|: v190:0 > 0 && v188:0 > 0 && v185:0 > 0 && v210:0 > 0 && v212:0 > 0 && v214:0 < 0 && v224:0 > 0 && v224:0 + v214:0 = 0 && v186:1 > 0 Filtered unneeded arguments: f_310(x1, x2, x3, x4, x5, x6, x7) -> f_310(x1, x2) Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: f_310(sum~cons_1~sum~v253:0~v214:0, v185:0) -> f_310(v253:0, v253:0) :|: v185:0 > 0 && v214:0 > -1 && sum~cons_1~sum~v253:0~v214:0 = 1 + (v253:0 + v214:0) f_310(sum~cons_1~sum~v254:0~v224:0, v185:0) -> f_310(v254:0, v254:0) :|: v185:0 > 0 && v224:0 > 0 && sum~cons_1~sum~v254:0~v224:0 = 1 + (v254:0 + v224:0) ---------------------------------------- (8) Obligation: Rules: f_310(sum~cons_1~sum~v253:0~v214:0, v185:0) -> f_310(v253:0, v253:0) :|: v185:0 > 0 && v214:0 > -1 && sum~cons_1~sum~v253:0~v214:0 = 1 + (v253:0 + v214:0) f_310(x, x1) -> f_310(x2, x2) :|: x1 > 0 && x3 > 0 && x = 1 + (x2 + x3) ---------------------------------------- (9) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (10) Obligation: Rules: f_310(sum~cons_1~sum~v253:0:0~v214:0:0, v185:0:0) -> f_310(v253:0:0, v253:0:0) :|: v185:0:0 > 0 && v214:0:0 > -1 && sum~cons_1~sum~v253:0:0~v214:0:0 = 1 + (v253:0:0 + v214:0:0) f_310(sum~cons_1~sum~x2:0~x3:0, x1:0) -> f_310(x2:0, x2:0) :|: x1:0 > 0 && x3:0 > 0 && sum~cons_1~sum~x2:0~x3:0 = 1 + (x2:0 + x3:0) ---------------------------------------- (11) CaseAnalysis (EQUIVALENT) Found the following inductive condition: f_310(x, x1): -1 - 4*x>=0 ---------------------------------------- (12) Complex Obligation (AND) ---------------------------------------- (13) Obligation: Rules: f_310(sum~cons_1~sum~v253:0:0~v214:0:0, v185:0:0) -> f_310(v253:0:0, v253:0:0) :|: v185:0:0 > 0 && v214:0:0 > -1 && sum~cons_1~sum~v253:0:0~v214:0:0 = 1 + (v253:0:0 + v214:0:0) && -1 + -4 * sum~cons_1~sum~v253:0:0~v214:0:0 >= 0 f_310(sum~cons_1~sum~x2:0~x3:0, x1:0) -> f_310(x2:0, x2:0) :|: x1:0 > 0 && x3:0 > 0 && sum~cons_1~sum~x2:0~x3:0 = 1 + (x2:0 + x3:0) && -1 + -4 * sum~cons_1~sum~x2:0~x3:0 >= 0 ---------------------------------------- (14) TerminationGraphProcessor (EQUIVALENT) Constructed the termination graph and obtained no non-trivial SCC(s). ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Rules: f_310(sum~cons_1~sum~v253:0:0~v214:0:0, v185:0:0) -> f_310(v253:0:0, v253:0:0) :|: v185:0:0 > 0 && v214:0:0 > -1 && sum~cons_1~sum~v253:0:0~v214:0:0 = 1 + (v253:0:0 + v214:0:0) && -1 + -4 * sum~cons_1~sum~v253:0:0~v214:0:0 < 0 f_310(sum~cons_1~sum~x2:0~x3:0, x1:0) -> f_310(x2:0, x2:0) :|: x1:0 > 0 && x3:0 > 0 && sum~cons_1~sum~x2:0~x3:0 = 1 + (x2:0 + x3:0) && -1 + -4 * sum~cons_1~sum~x2:0~x3:0 < 0 ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f_310(sum~cons_1~sum~v253:0:0:0~v214:0:0:0, v185:0:0:0) -> f_310(v253:0:0:0, v253:0:0:0) :|: v185:0:0:0 > 0 && v214:0:0:0 > -1 && 1 > -4 * (1 + (v253:0:0:0 + v214:0:0:0)) && sum~cons_1~sum~v253:0:0:0~v214:0:0:0 = 1 + (v253:0:0:0 + v214:0:0:0) f_310(sum~cons_1~sum~x2:0:0~x3:0:0, x1:0:0) -> f_310(x2:0:0, x2:0:0) :|: x1:0:0 > 0 && x3:0:0 > 0 && 1 > -4 * (1 + (x2:0:0 + x3:0:0)) && sum~cons_1~sum~x2:0:0~x3:0:0 = 1 + (x2:0:0 + x3:0:0) ---------------------------------------- (19) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_310 ] = f_310_1 The following rules are decreasing: f_310(sum~cons_1~sum~v253:0:0:0~v214:0:0:0, v185:0:0:0) -> f_310(v253:0:0:0, v253:0:0:0) :|: v185:0:0:0 > 0 && v214:0:0:0 > -1 && 1 > -4 * (1 + (v253:0:0:0 + v214:0:0:0)) && sum~cons_1~sum~v253:0:0:0~v214:0:0:0 = 1 + (v253:0:0:0 + v214:0:0:0) f_310(sum~cons_1~sum~x2:0:0~x3:0:0, x1:0:0) -> f_310(x2:0:0, x2:0:0) :|: x1:0:0 > 0 && x3:0:0 > 0 && 1 > -4 * (1 + (x2:0:0 + x3:0:0)) && sum~cons_1~sum~x2:0:0~x3:0:0 = 1 + (x2:0:0 + x3:0:0) The following rules are bounded: f_310(sum~cons_1~sum~v253:0:0:0~v214:0:0:0, v185:0:0:0) -> f_310(v253:0:0:0, v253:0:0:0) :|: v185:0:0:0 > 0 && v214:0:0:0 > -1 && 1 > -4 * (1 + (v253:0:0:0 + v214:0:0:0)) && sum~cons_1~sum~v253:0:0:0~v214:0:0:0 = 1 + (v253:0:0:0 + v214:0:0:0) f_310(sum~cons_1~sum~x2:0:0~x3:0:0, x1:0:0) -> f_310(x2:0:0, x2:0:0) :|: x1:0:0 > 0 && x3:0:0 > 0 && 1 > -4 * (1 + (x2:0:0 + x3:0:0)) && sum~cons_1~sum~x2:0:0~x3:0:0 = 1 + (x2:0:0 + x3:0:0) ---------------------------------------- (20) YES