13.08/4.61 MAYBE 13.08/4.62 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 13.08/4.62 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.08/4.62 13.08/4.62 13.08/4.62 Termination of the given C Problem could not be shown: 13.08/4.62 13.08/4.62 (0) C Problem 13.08/4.62 (1) CToLLVMProof [EQUIVALENT, 169 ms] 13.08/4.62 (2) LLVM problem 13.08/4.62 (3) LLVMToTerminationGraphProof [EQUIVALENT, 761 ms] 13.08/4.62 (4) LLVM Symbolic Execution Graph 13.08/4.62 (5) SymbolicExecutionGraphToLassoProof [EQUIVALENT, 0 ms] 13.08/4.62 (6) LLVM Symbolic Execution Lasso 13.08/4.62 (7) Lasso2IRS [SOUND, 63 ms] 13.08/4.62 (8) IntTRS 13.08/4.62 (9) IRS2T2 [EQUIVALENT, 0 ms] 13.08/4.62 (10) T2IntSys 13.08/4.62 (11) T2 [COMPLETE, 1321 ms] 13.08/4.62 (12) NO 13.08/4.62 (13) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 13.08/4.62 (14) LLVM Symbolic Execution SCC 13.08/4.62 (15) SCC2IRS [SOUND, 48 ms] 13.08/4.62 (16) IntTRS 13.08/4.62 (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] 13.08/4.62 (18) IntTRS 13.08/4.62 (19) IntTRSPeriodicNontermProof [COMPLETE, 10 ms] 13.08/4.62 (20) NO 13.08/4.62 (21) SCC2IRS [SOUND, 0 ms] 13.08/4.62 (22) IntTRS 13.08/4.62 (23) IntTRSCompressionProof [EQUIVALENT, 0 ms] 13.08/4.62 (24) IntTRS 13.08/4.62 (25) IntTRSPeriodicNontermProof [COMPLETE, 16 ms] 13.08/4.62 (26) NO 13.08/4.62 (27) SEGraph to IRS [SOUND, 50 ms] 13.08/4.62 (28) IntTRS 13.08/4.62 (29) IRS2T2 [EQUIVALENT, 0 ms] 13.08/4.62 (30) T2IntSys 13.08/4.62 (31) T2 [COMPLETE, 1564 ms] 13.08/4.62 (32) NO 13.08/4.62 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (0) 13.08/4.62 Obligation: 13.08/4.62 c file /export/starexec/sandbox/benchmark/theBenchmark.c 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (1) CToLLVMProof (EQUIVALENT) 13.08/4.62 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (2) 13.08/4.62 Obligation: 13.08/4.62 LLVM Problem 13.08/4.62 13.08/4.62 Aliases: 13.08/4.62 13.08/4.62 Data layout: 13.08/4.62 13.08/4.62 "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" 13.08/4.62 13.08/4.62 Machine: 13.08/4.62 13.08/4.62 "x86_64-pc-linux-gnu" 13.08/4.62 13.08/4.62 Type definitions: 13.08/4.62 13.08/4.62 Global variables: 13.08/4.62 13.08/4.62 Function declarations and definitions: 13.08/4.62 13.08/4.62 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc 13.08/4.62 *BasicFunctionTypename: "g" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 13.08/4.62 0: 13.08/4.62 %1 = alloca i32, align 4 13.08/4.62 %2 = alloca i32, align 4 13.08/4.62 store %x, %2 13.08/4.62 %3 = load %2 13.08/4.62 %4 = icmp eq %3 0 13.08/4.62 br %4, %5, %6 13.08/4.62 5: 13.08/4.62 store 1, %1 13.08/4.62 br %12 13.08/4.62 6: 13.08/4.62 %7 = load %2 13.08/4.62 %8 = sub %7 1 13.08/4.62 %9 = call i32 @g(i32 %8) 13.08/4.62 %10 = add %9 1 13.08/4.62 %11 = call i32 @g(i32 %10) 13.08/4.62 store %11, %1 13.08/4.62 br %12 13.08/4.62 12: 13.08/4.62 %13 = load %1 13.08/4.62 ret %13 13.08/4.62 13.08/4.62 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 13.08/4.62 0: 13.08/4.62 %1 = alloca i32, align 4 13.08/4.62 %x = alloca i32, align 4 13.08/4.62 store 0, %1 13.08/4.62 %2 = call i32 (...)* @__VERIFIER_nondet_int() 13.08/4.62 store %2, %x 13.08/4.62 %3 = load %x 13.08/4.62 %4 = icmp slt %3 0 13.08/4.62 br %4, %5, %6 13.08/4.62 5: 13.08/4.62 store 0, %1 13.08/4.62 br %9 13.08/4.62 6: 13.08/4.62 %7 = load %x 13.08/4.62 %8 = call i32 @g(i32 %7) 13.08/4.62 br %9 13.08/4.62 9: 13.08/4.62 %10 = load %1 13.08/4.62 ret %10 13.08/4.62 13.08/4.62 13.08/4.62 Analyze Termination of all function calls matching the pattern: 13.08/4.62 main() 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (3) LLVMToTerminationGraphProof (EQUIVALENT) 13.08/4.62 Constructed symbolic execution graph for LLVM program and proved memory safety. 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (4) 13.08/4.62 Obligation: 13.08/4.62 SE Graph 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (5) SymbolicExecutionGraphToLassoProof (EQUIVALENT) 13.08/4.62 Converted SEGraph to 1 independent lasso. 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (6) 13.08/4.62 Obligation: 13.08/4.62 Lasso 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (7) Lasso2IRS (SOUND) 13.08/4.62 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 13.08/4.62 Generated rules. Obtained 33 rulesP rules: 13.08/4.62 f_190(v81, v88, v82, v83, v84, v85, v89, 0, v87, 3, 1, 4) -> f_191(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: 1 <= v90 && v91 = 3 + v90 && 4 <= v91 13.08/4.62 f_191(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_192(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_192(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_193(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_193(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_195(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: v81 != 0 13.08/4.62 f_195(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_197(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_197(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_199(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_199(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_201(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_201(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_203(v81, v88, v90, 0, v93, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 1 + v93 = v81 && 0 <= v93 13.08/4.62 f_203(v81, v88, v90, 0, v93, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_207(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) :|: TRUE 13.08/4.62 f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_210(0, 1, v82, v83, v84, v85, v88, v89, v90, v91, v87, 3, 4) :|: TRUE 13.08/4.62 f_207(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_189(v93, v82, v83, v84, v85, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_189(v81, v82, v83, v84, v85, 0, v87, 3, 1, 4) -> f_190(v81, v88, v82, v83, v84, v85, v89, 0, v87, 3, 1, 4) :|: 1 <= v88 && v89 = 3 + v88 && 4 <= v89 13.08/4.62 f_210(0, 1, v82, v83, v84, v85, v88, v89, v90, v91, v87, 3, 4) -> f_212(1, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_212(1, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_213(1, v88, v90, 0, 2, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_213(1, v88, v90, 0, 2, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_214(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) :|: 0 = 0 13.08/4.62 f_214(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) -> f_215(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) :|: TRUE 13.08/4.62 f_215(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) -> f_189(2, v82, v83, v84, v85, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_100 -> f_101(v1, v2, 3, 1, 4) :|: 1 <= v1 && v2 = 3 + v1 && 4 <= v2 13.08/4.62 f_101(v1, v2, 3, 1, 4) -> f_102(v1, v3, v2, v4, 3, 1, 4) :|: 1 <= v3 && v4 = 3 + v3 && 4 <= v4 13.08/4.62 f_102(v1, v3, v2, v4, 3, 1, 4) -> f_103(v1, v3, v2, v4, 0, 3, 1, 4) :|: TRUE 13.08/4.62 f_103(v1, v3, v2, v4, 0, 3, 1, 4) -> f_104(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: TRUE 13.08/4.62 f_104(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_105(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: TRUE 13.08/4.62 f_105(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_106(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_106(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_108(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: 0 <= v5 13.08/4.62 f_108(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_110(v1, v3, v5, 0, v2, v4, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_110(v1, v3, v5, 0, v2, v4, 3, 1, 4) -> f_112(v1, v3, v5, 0, v2, v4, 3, 1, 4) :|: TRUE 13.08/4.62 f_112(v1, v3, v5, 0, v2, v4, 3, 1, 4) -> f_114(v1, v3, v5, 0, v2, v4, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_114(v1, v3, v5, 0, v2, v4, 3, 1, 4) -> f_116(v5, v1, v2, v3, v4, 0, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_116(v5, v1, v2, v3, v4, 0, 3, 1, 4) -> f_118(v5, v1, v2, v3, v4, 0, 3, 1, 4) :|: TRUE 13.08/4.62 f_118(v5, v1, v2, v3, v4, 0, 3, 1, 4) -> f_138(v5, v1, v2, v3, v4, 0, v5, 3, 1, 4) :|: TRUE 13.08/4.62 f_138(v21, v22, v23, v24, v25, 0, v27, 3, 1, 4) -> f_160(v21, v22, v23, v24, v25, 0, v27, 3, 1, 4) :|: TRUE 13.08/4.62 f_160(v43, v44, v45, v46, v47, 0, v49, 3, 1, 4) -> f_189(v43, v44, v45, v46, v47, 0, v49, 3, 1, 4) :|: TRUE 13.08/4.62 Combined rules. Obtained 3 rulesP rules: 13.08/4.62 f_100 -> f_190(v5:0, v88:0, v1:0, 3 + v1:0, v3:0, 3 + v3:0, 3 + v88:0, 0, v5:0, 3, 1, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > -1 && v88:0 > 0 13.08/4.62 f_190(1 + v93:0, v88:0, v82:0, v83:0, v84:0, v85:0, v89:0, 0, v87:0, 3, 1, 4) -> f_190(v93:0, v88:1, v82:0, v83:0, v84:0, v85:0, 3 + v88:1, 0, v87:0, 3, 1, 4) :|: v90:0 > 0 && v93:0 > -1 && v88:1 > 0 13.08/4.62 f_190(1 + v93:0, v88:0, v82:0, v83:0, v84:0, v85:0, v89:0, 0, v87:0, 3, 1, 4) -> f_190(2, v88:1, v82:0, v83:0, v84:0, v85:0, 3 + v88:1, 0, v87:0, 3, 1, 4) :|: v90:0 > 0 && v93:0 > -1 && v88:1 > 0 13.08/4.62 Filtered unneeded arguments: 13.08/4.62 f_190(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12) -> f_190(x1) 13.08/4.62 Removed division, modulo operations, cleaned up constraints. Obtained 3 rules.P rules: 13.08/4.62 f_100 -> f_190(v5:0) :|: v5:0 > -1 13.08/4.62 f_190(sum~cons_1~v93:0) -> f_190(v93:0) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 f_190(sum~cons_1~v93:0) -> f_190(2) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (8) 13.08/4.62 Obligation: 13.08/4.62 Rules: 13.08/4.62 f_100 -> f_190(v5:0) :|: v5:0 > -1 13.08/4.62 f_190(sum~cons_1~v93:0) -> f_190(v93:0) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 f_190(x) -> f_190(2) :|: x1 > -1 && x = 1 + x1 13.08/4.62 Start term: f_100 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (9) IRS2T2 (EQUIVALENT) 13.08/4.62 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 13.08/4.62 13.08/4.62 (f_100_1,1) 13.08/4.62 (f_190_1,2) 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (10) 13.08/4.62 Obligation: 13.08/4.62 START: 1; 13.08/4.62 13.08/4.62 FROM: 1; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := nondet(); 13.08/4.62 assume(oldX1 > -1); 13.08/4.62 x0 := oldX1; 13.08/4.62 TO: 2; 13.08/4.62 13.08/4.62 FROM: 2; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := oldX0 - 1; 13.08/4.62 assume(oldX1 > -1 && oldX0 = 1 + oldX1); 13.08/4.62 x0 := oldX0 - 1; 13.08/4.62 TO: 2; 13.08/4.62 13.08/4.62 FROM: 2; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := oldX0 - 1; 13.08/4.62 assume(oldX1 > -1 && oldX0 = 1 + oldX1); 13.08/4.62 x0 := 2; 13.08/4.62 TO: 2; 13.08/4.62 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (11) T2 (COMPLETE) 13.08/4.62 Found this recurrent set for cutpoint 5: 0 <= oldX1 and 0 <= x0 and 0 <= oldX1+x0 and -x0+1 <= 0 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (12) 13.08/4.62 NO 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (13) SymbolicExecutionGraphToSCCProof (SOUND) 13.08/4.62 Splitted symbolic execution graph to 1 SCC. 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (14) 13.08/4.62 Obligation: 13.08/4.62 SCC 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (15) SCC2IRS (SOUND) 13.08/4.62 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 13.08/4.62 Generated rules. Obtained 18 rulesP rules: 13.08/4.62 f_190(v81, v88, v82, v83, v84, v85, v89, 0, v87, 3, 1, 4) -> f_191(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: 1 <= v90 && v91 = 3 + v90 && 4 <= v91 13.08/4.62 f_191(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_192(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_192(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_193(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_193(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_195(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: v81 != 0 13.08/4.62 f_195(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_197(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_197(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_199(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_199(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_201(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_201(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_203(v81, v88, v90, 0, v93, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 1 + v93 = v81 && 0 <= v93 13.08/4.62 f_203(v81, v88, v90, 0, v93, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_207(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) :|: TRUE 13.08/4.62 f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_210(0, 1, v82, v83, v84, v85, v88, v89, v90, v91, v87, 3, 4) :|: TRUE 13.08/4.62 f_207(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_189(v93, v82, v83, v84, v85, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_189(v81, v82, v83, v84, v85, 0, v87, 3, 1, 4) -> f_190(v81, v88, v82, v83, v84, v85, v89, 0, v87, 3, 1, 4) :|: 1 <= v88 && v89 = 3 + v88 && 4 <= v89 13.08/4.62 f_210(0, 1, v82, v83, v84, v85, v88, v89, v90, v91, v87, 3, 4) -> f_212(1, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_212(1, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_213(1, v88, v90, 0, 2, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_213(1, v88, v90, 0, 2, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_214(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) :|: 0 = 0 13.08/4.62 f_214(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) -> f_215(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) :|: TRUE 13.08/4.62 f_215(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) -> f_189(2, v82, v83, v84, v85, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 Combined rules. Obtained 2 rulesP rules: 13.08/4.62 f_190(1 + v93:0, v88:0, v82:0, v83:0, v84:0, v85:0, v89:0, 0, v87:0, 3, 1, 4) -> f_190(v93:0, v88:1, v82:0, v83:0, v84:0, v85:0, 3 + v88:1, 0, v87:0, 3, 1, 4) :|: v90:0 > 0 && v93:0 > -1 && v88:1 > 0 13.08/4.62 f_190(1 + v93:0, v88:0, v82:0, v83:0, v84:0, v85:0, v89:0, 0, v87:0, 3, 1, 4) -> f_190(2, v88:1, v82:0, v83:0, v84:0, v85:0, 3 + v88:1, 0, v87:0, 3, 1, 4) :|: v90:0 > 0 && v93:0 > -1 && v88:1 > 0 13.08/4.62 Filtered unneeded arguments: 13.08/4.62 f_190(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12) -> f_190(x1) 13.08/4.62 Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: 13.08/4.62 f_190(sum~cons_1~v93:0) -> f_190(v93:0) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 f_190(sum~cons_1~v93:0) -> f_190(2) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (16) 13.08/4.62 Obligation: 13.08/4.62 Rules: 13.08/4.62 f_190(sum~cons_1~v93:0) -> f_190(v93:0) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 f_190(x) -> f_190(2) :|: x1 > -1 && x = 1 + x1 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (17) IntTRSCompressionProof (EQUIVALENT) 13.08/4.62 Compressed rules. 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (18) 13.08/4.62 Obligation: 13.08/4.62 Rules: 13.08/4.62 f_190(sum~cons_1~v93:0:0) -> f_190(v93:0:0) :|: v93:0:0 > -1 && sum~cons_1~v93:0:0 = 1 + v93:0:0 13.08/4.62 f_190(sum~cons_1~x1:0) -> f_190(2) :|: x1:0 > -1 && sum~cons_1~x1:0 = 1 + x1:0 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (19) IntTRSPeriodicNontermProof (COMPLETE) 13.08/4.62 Normalized system to the following form: 13.08/4.62 f(pc, sum~cons_1~v93:0:0) -> f(1, v93:0:0) :|: pc = 1 && (v93:0:0 > -1 && sum~cons_1~v93:0:0 = 1 + v93:0:0) 13.08/4.62 f(pc, sum~cons_1~x1:0) -> f(1, 2) :|: pc = 1 && (x1:0 > -1 && sum~cons_1~x1:0 = 1 + x1:0) 13.08/4.62 Witness term starting non-terminating reduction: f(1, 1) 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (20) 13.08/4.62 NO 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (21) SCC2IRS (SOUND) 13.08/4.62 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 13.08/4.62 Generated rules. Obtained 18 rulesP rules: 13.08/4.62 f_190(v81, v88, v82, v83, v84, v85, v89, 0, v87, 3, 1, 4) -> f_191(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: 1 <= v90 && v91 = 3 + v90 && 4 <= v91 13.08/4.62 f_191(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_192(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_192(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_193(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_193(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_195(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: v81 != 0 13.08/4.62 f_195(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_197(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_197(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_199(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_199(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_201(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_201(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_203(v81, v88, v90, 0, v93, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 1 + v93 = v81 && 0 <= v93 13.08/4.62 f_203(v81, v88, v90, 0, v93, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_207(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) :|: TRUE 13.08/4.62 f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_210(0, 1, v82, v83, v84, v85, v88, v89, v90, v91, v87, 3, 4) :|: TRUE 13.08/4.62 f_207(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_189(v93, v82, v83, v84, v85, 0, v87, 3, 1, 4) :|: 0 <= v93 && 1 <= v82 && 4 <= v83 && 1 <= v84 && 4 <= v85 && 0 <= v87 && v82 <= v83 && v84 <= v85 13.08/4.62 f_189(v81, v82, v83, v84, v85, 0, v87, 3, 1, 4) -> f_190(v81, v88, v82, v83, v84, v85, v89, 0, v87, 3, 1, 4) :|: 1 <= v88 && v89 = 3 + v88 && 4 <= v89 13.08/4.62 f_210(0, 1, v82, v83, v84, v85, v88, v89, v90, v91, v87, 3, 4) -> f_212(1, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_212(1, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_213(1, v88, v90, 0, 2, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_213(1, v88, v90, 0, 2, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_214(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) :|: 0 = 0 13.08/4.62 f_214(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) -> f_215(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) :|: TRUE 13.08/4.62 f_215(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) -> f_189(2, v82, v83, v84, v85, 0, v87, 3, 1, 4) :|: 0 <= 2 && 1 <= v82 && 4 <= v83 && 1 <= v84 && 4 <= v85 && 0 <= v87 && v82 <= v83 && v84 <= v85 13.08/4.62 Combined rules. Obtained 2 rulesP rules: 13.08/4.62 f_190(1 + v93:0, v88:0, v82:0, v83:0, v84:0, v85:0, v89:0, 0, v87:0, 3, 1, 4) -> f_190(2, v88:1, v82:0, v83:0, v84:0, v85:0, 3 + v88:1, 0, v87:0, 3, 1, 4) :|: v90:0 > 0 && v93:0 > -1 && v82:0 > 0 && v83:0 > 3 && v84:0 > 0 && v85:0 > 3 && v87:0 > -1 && v88:1 > 0 && v83:0 >= v82:0 && v85:0 >= v84:0 13.08/4.62 f_190(1 + v93:0, v88:0, v82:0, v83:0, v84:0, v85:0, v89:0, 0, v87:0, 3, 1, 4) -> f_190(v93:0, v88:1, v82:0, v83:0, v84:0, v85:0, 3 + v88:1, 0, v87:0, 3, 1, 4) :|: v90:0 > 0 && v82:0 > 0 && v93:0 > -1 && v83:0 > 3 && v84:0 > 0 && v85:0 > 3 && v87:0 > -1 && v83:0 >= v82:0 && v88:1 > 0 && v85:0 >= v84:0 13.08/4.62 Filtered unneeded arguments: 13.08/4.62 f_190(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12) -> f_190(x1, x3, x4, x5, x6, x9) 13.08/4.62 Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: 13.08/4.62 f_190(sum~cons_1~v93:0, v82:0, v83:0, v84:0, v85:0, v87:0) -> f_190(2, v82:0, v83:0, v84:0, v85:0, v87:0) :|: v82:0 > 0 && v93:0 > -1 && v83:0 > 3 && v84:0 > 0 && v85:0 > 3 && v87:0 > -1 && v85:0 >= v84:0 && v83:0 >= v82:0 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 f_190(sum~cons_1~v93:0, v82:0, v83:0, v84:0, v85:0, v87:0) -> f_190(v93:0, v82:0, v83:0, v84:0, v85:0, v87:0) :|: v93:0 > -1 && v82:0 > 0 && v83:0 > 3 && v84:0 > 0 && v85:0 > 3 && v87:0 > -1 && v85:0 >= v84:0 && v83:0 >= v82:0 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (22) 13.08/4.62 Obligation: 13.08/4.62 Rules: 13.08/4.62 f_190(sum~cons_1~v93:0, v82:0, v83:0, v84:0, v85:0, v87:0) -> f_190(2, v82:0, v83:0, v84:0, v85:0, v87:0) :|: v82:0 > 0 && v93:0 > -1 && v83:0 > 3 && v84:0 > 0 && v85:0 > 3 && v87:0 > -1 && v85:0 >= v84:0 && v83:0 >= v82:0 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 f_190(x, x1, x2, x3, x4, x5) -> f_190(x6, x1, x2, x3, x4, x5) :|: x6 > -1 && x1 > 0 && x2 > 3 && x3 > 0 && x4 > 3 && x5 > -1 && x4 >= x3 && x2 >= x1 && x = 1 + x6 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (23) IntTRSCompressionProof (EQUIVALENT) 13.08/4.62 Compressed rules. 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (24) 13.08/4.62 Obligation: 13.08/4.62 Rules: 13.08/4.62 f_190(sum~cons_1~v93:0:0, v82:0:0, v83:0:0, v84:0:0, v85:0:0, v87:0:0) -> f_190(2, v82:0:0, v83:0:0, v84:0:0, v85:0:0, v87:0:0) :|: v85:0:0 >= v84:0:0 && v83:0:0 >= v82:0:0 && v87:0:0 > -1 && v85:0:0 > 3 && v84:0:0 > 0 && v83:0:0 > 3 && v93:0:0 > -1 && v82:0:0 > 0 && sum~cons_1~v93:0:0 = 1 + v93:0:0 13.08/4.62 f_190(sum~cons_1~x6:0, x1:0, x2:0, x3:0, x4:0, x5:0) -> f_190(x6:0, x1:0, x2:0, x3:0, x4:0, x5:0) :|: x4:0 >= x3:0 && x2:0 >= x1:0 && x5:0 > -1 && x4:0 > 3 && x3:0 > 0 && x2:0 > 3 && x1:0 > 0 && x6:0 > -1 && sum~cons_1~x6:0 = 1 + x6:0 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (25) IntTRSPeriodicNontermProof (COMPLETE) 13.08/4.62 Normalized system to the following form: 13.08/4.62 f(pc, sum~cons_1~v93:0:0, v82:0:0, v83:0:0, v84:0:0, v85:0:0, v87:0:0) -> f(1, 2, v82:0:0, v83:0:0, v84:0:0, v85:0:0, v87:0:0) :|: pc = 1 && (v85:0:0 >= v84:0:0 && v83:0:0 >= v82:0:0 && v87:0:0 > -1 && v85:0:0 > 3 && v84:0:0 > 0 && v83:0:0 > 3 && v93:0:0 > -1 && v82:0:0 > 0 && sum~cons_1~v93:0:0 = 1 + v93:0:0) 13.08/4.62 f(pc, sum~cons_1~x6:0, x1:0, x2:0, x3:0, x4:0, x5:0) -> f(1, x6:0, x1:0, x2:0, x3:0, x4:0, x5:0) :|: pc = 1 && (x4:0 >= x3:0 && x2:0 >= x1:0 && x5:0 > -1 && x4:0 > 3 && x3:0 > 0 && x2:0 > 3 && x1:0 > 0 && x6:0 > -1 && sum~cons_1~x6:0 = 1 + x6:0) 13.08/4.62 Witness term starting non-terminating reduction: f(1, 2, 4, 6, 1, 5, 3) 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (26) 13.08/4.62 NO 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (27) SEGraph to IRS (SOUND) 13.08/4.62 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 13.08/4.62 Generated rules. Obtained 50 rulesP rules: 13.08/4.62 f_100 -> f_101(v1, v2, 3, 1, 4) :|: 1 <= v1 && v2 = 3 + v1 && 4 <= v2 13.08/4.62 f_101(v1, v2, 3, 1, 4) -> f_102(v1, v3, v2, v4, 3, 1, 4) :|: 1 <= v3 && v4 = 3 + v3 && 4 <= v4 13.08/4.62 f_102(v1, v3, v2, v4, 3, 1, 4) -> f_103(v1, v3, v2, v4, 0, 3, 1, 4) :|: TRUE 13.08/4.62 f_103(v1, v3, v2, v4, 0, 3, 1, 4) -> f_104(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: TRUE 13.08/4.62 f_104(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_105(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: TRUE 13.08/4.62 f_105(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_106(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_106(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_107(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: v5 < 0 13.08/4.62 f_106(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_108(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: 0 <= v5 13.08/4.62 f_107(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_109(v1, v3, v5, 1, v2, v4, 0, 3, 4) :|: 0 = 0 13.08/4.62 f_108(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_110(v1, v3, v5, 0, v2, v4, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_109(v1, v3, v5, 1, v2, v4, 0, 3, 4) -> f_111(v1, v3, v5, 1, v2, v4, 0, 3, 4) :|: TRUE 13.08/4.62 f_110(v1, v3, v5, 0, v2, v4, 3, 1, 4) -> f_112(v1, v3, v5, 0, v2, v4, 3, 1, 4) :|: TRUE 13.08/4.62 f_111(v1, v3, v5, 1, v2, v4, 0, 3, 4) -> f_113(v1, v3, v5, 1, v2, v4, 0, 3, 4) :|: TRUE 13.08/4.62 f_112(v1, v3, v5, 0, v2, v4, 3, 1, 4) -> f_114(v1, v3, v5, 0, v2, v4, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_113(v1, v3, v5, 1, v2, v4, 0, 3, 4) -> f_115(v1, v3, v5, 1, v2, v4, 0, 3, 4) :|: TRUE 13.08/4.62 f_114(v1, v3, v5, 0, v2, v4, 3, 1, 4) -> f_116(v5, v1, v2, v3, v4, 0, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_115(v1, v3, v5, 1, v2, v4, 0, 3, 4) -> f_117(v1, v3, v5, 1, 0, v2, v4, 3, 4) :|: 0 = 0 13.08/4.62 f_116(v5, v1, v2, v3, v4, 0, 3, 1, 4) -> f_118(v5, v1, v2, v3, v4, 0, 3, 1, 4) :|: TRUE 13.08/4.62 f_116(v5, v1, v2, v3, v4, 0, 3, 1, 4) -> f_206(0, 1, v1, v2, v3, v4, 3, 4) :|: TRUE 13.08/4.62 f_118(v5, v1, v2, v3, v4, 0, 3, 1, 4) -> f_138(v5, v1, v2, v3, v4, 0, v5, 3, 1, 4) :|: TRUE 13.08/4.62 f_138(v21, v22, v23, v24, v25, 0, v27, 3, 1, 4) -> f_160(v21, v22, v23, v24, v25, 0, v27, 3, 1, 4) :|: TRUE 13.08/4.62 f_160(v43, v44, v45, v46, v47, 0, v49, 3, 1, 4) -> f_189(v43, v44, v45, v46, v47, 0, v49, 3, 1, 4) :|: TRUE 13.08/4.62 f_189(v81, v82, v83, v84, v85, 0, v87, 3, 1, 4) -> f_190(v81, v88, v82, v83, v84, v85, v89, 0, v87, 3, 1, 4) :|: 1 <= v88 && v89 = 3 + v88 && 4 <= v89 13.08/4.62 f_190(v81, v88, v82, v83, v84, v85, v89, 0, v87, 3, 1, 4) -> f_191(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: 1 <= v90 && v91 = 3 + v90 && 4 <= v91 13.08/4.62 f_191(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_192(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_192(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_193(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_193(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_194(0, v88, v90, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: v81 = 0 13.08/4.62 f_193(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_195(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) :|: v81 != 0 13.08/4.62 f_194(0, v88, v90, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_196(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_195(v81, v88, v90, v82, v83, v84, v85, v89, v91, 0, v87, 3, 1, 4) -> f_197(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_196(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_198(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: TRUE 13.08/4.62 f_197(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_199(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_198(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_200(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: TRUE 13.08/4.62 f_199(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_201(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_200(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_202(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: TRUE 13.08/4.62 f_201(v81, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_203(v81, v88, v90, 0, v93, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) :|: 1 + v93 = v81 && 0 <= v93 13.08/4.62 f_202(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_204(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_203(v81, v88, v90, 0, v93, v82, v83, v84, v85, v89, v91, v87, 3, 1, 4) -> f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) :|: 0 = 0 13.08/4.62 f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_207(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) :|: TRUE 13.08/4.62 f_205(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_210(0, 1, v82, v83, v84, v85, v88, v89, v90, v91, v87, 3, 4) :|: TRUE 13.08/4.62 f_206(0, 1, v1, v2, v3, v4, 3, 4) -> f_208(v1, v3, 0, 1, v2, v4, 3, 4) :|: 0 = 0 13.08/4.62 f_207(v93, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, v81, 3, 1, 4) -> f_189(v93, v82, v83, v84, v85, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 f_208(v1, v3, 0, 1, v2, v4, 3, 4) -> f_209(v1, v3, 0, 1, v2, v4, 3, 4) :|: TRUE 13.08/4.62 f_209(v1, v3, 0, 1, v2, v4, 3, 4) -> f_211(v1, v3, 0, 1, v2, v4, 3, 4) :|: 0 = 0 13.08/4.62 f_210(0, 1, v82, v83, v84, v85, v88, v89, v90, v91, v87, 3, 4) -> f_212(1, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_212(1, v88, v90, 0, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_213(1, v88, v90, 0, 2, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: 0 = 0 13.08/4.62 f_213(1, v88, v90, 0, 2, v82, v83, v84, v85, v89, v91, v87, 3, 4) -> f_214(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) :|: 0 = 0 13.08/4.62 f_214(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) -> f_215(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) :|: TRUE 13.08/4.62 f_214(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) -> f_216(0, v88, v90, 1, v82, v83, v84, v85, v89, v91, v87, 3, 4) :|: TRUE 13.08/4.62 f_215(2, v82, v83, v84, v85, v88, v89, v90, v91, 0, v87, 1, 3, 4) -> f_189(2, v82, v83, v84, v85, 0, v87, 3, 1, 4) :|: TRUE 13.08/4.62 Combined rules. Obtained 7 rulesP rules: 13.08/4.62 f_193(0, v88:0, v90:0, v82:0, v83:0, v84:0, v85:0, v89:0, v91:0, 0, v87:0, 3, 1, 4) -> f_204(0, v88:0, v90:0, 1, v82:0, v83:0, v84:0, v85:0, v89:0, v91:0, v87:0, 3, 4) :|: TRUE 13.08/4.62 f_100 -> f_117(v1:0, v3:0, v5:0, 1, 0, 3 + v1:0, 3 + v3:0, 3, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 < 0 13.08/4.62 f_100 -> f_211(v1:0, v3:0, 0, 1, 3 + v1:0, 3 + v3:0, 3, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > -1 13.08/4.62 f_193(1 + v93:0, v88:0, v90:0, v82:0, v83:0, v84:0, v85:0, v89:0, v91:0, 0, v87:0, 3, 1, 4) -> f_216(0, v88:0, v90:0, 1, v82:0, v83:0, v84:0, v85:0, v89:0, v91:0, v87:0, 3, 4) :|: v93:0 > -1 13.08/4.62 f_193(1 + v93:0, v88:0, v90:0, v82:0, v83:0, v84:0, v85:0, v89:0, v91:0, 0, v87:0, 3, 1, 4) -> f_193(2, v88:1, v90:1, v82:0, v83:0, v84:0, v85:0, 3 + v88:1, 3 + v90:1, 0, v87:0, 3, 1, 4) :|: v93:0 > -1 && v88:1 > 0 && v90:1 > 0 13.08/4.62 f_100 -> f_193(v5:0, v88:0, v90:0, v1:0, 3 + v1:0, v3:0, 3 + v3:0, 3 + v88:0, 3 + v90:0, 0, v5:0, 3, 1, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > -1 && v88:0 > 0 && v90:0 > 0 13.08/4.62 f_193(1 + v93:0, v88:0, v90:0, v82:0, v83:0, v84:0, v85:0, v89:0, v91:0, 0, v87:0, 3, 1, 4) -> f_193(v93:0, v88:1, v90:1, v82:0, v83:0, v84:0, v85:0, 3 + v88:1, 3 + v90:1, 0, v87:0, 3, 1, 4) :|: v88:1 > 0 && v93:0 > -1 && v90:1 > 0 13.08/4.62 Filtered unneeded arguments: 13.08/4.62 f_193(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_193(x1) 13.08/4.62 Removed division, modulo operations, cleaned up constraints. Obtained 7 rules.P rules: 13.08/4.62 f_193(cons_0) -> f_204(0, v88:0, v90:0, 1, v82:0, v83:0, v84:0, v85:0, v89:0, v91:0, v87:0, 3, 4) :|: TRUE && cons_0 = 0 13.08/4.62 f_100 -> f_117(v1:0, v3:0, v5:0, 1, 0, 3 + v1:0, 3 + v3:0, 3, 4) :|: v1:0 > 0 && v5:0 < 0 && v3:0 > 0 13.08/4.62 f_100 -> f_211(v1:0, v3:0, 0, 1, 3 + v1:0, 3 + v3:0, 3, 4) :|: v3:0 > 0 && v1:0 > 0 13.08/4.62 f_193(sum~cons_1~v93:0) -> f_216(0, v88:0, v90:0, 1, v82:0, v83:0, v84:0, v85:0, v89:0, v91:0, v87:0, 3, 4) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 f_193(sum~cons_1~v93:0) -> f_193(2) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 f_100 -> f_193(v5:0) :|: v5:0 > -1 13.08/4.62 f_193(sum~cons_1~v93:0) -> f_193(v93:0) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (28) 13.08/4.62 Obligation: 13.08/4.62 Rules: 13.08/4.62 f_193(cons_0) -> f_204(0, v88:0, v90:0, 1, v82:0, v83:0, v84:0, v85:0, v89:0, v91:0, v87:0, 3, 4) :|: TRUE && cons_0 = 0 13.08/4.62 f_100 -> f_117(v1:0, v3:0, v5:0, 1, 0, 3 + v1:0, 3 + v3:0, 3, 4) :|: v1:0 > 0 && v5:0 < 0 && v3:0 > 0 13.08/4.62 f_100 -> f_211(x, x1, 0, 1, 3 + x, 3 + x1, 3, 4) :|: x1 > 0 && x > 0 13.08/4.62 f_193(x2) -> f_216(0, x3, x4, 1, x5, x6, x7, x8, x9, x10, x11, 3, 4) :|: x12 > -1 && x2 = 1 + x12 13.08/4.62 f_193(sum~cons_1~v93:0) -> f_193(2) :|: v93:0 > -1 && sum~cons_1~v93:0 = 1 + v93:0 13.08/4.62 f_100 -> f_193(x13) :|: x13 > -1 13.08/4.62 f_193(x14) -> f_193(x15) :|: x15 > -1 && x14 = 1 + x15 13.08/4.62 Start term: f_100 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (29) IRS2T2 (EQUIVALENT) 13.08/4.62 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 13.08/4.62 13.08/4.62 (f_193_13,1) 13.08/4.62 (f_204_13,2) 13.08/4.62 (f_100_13,3) 13.08/4.62 (f_117_13,4) 13.08/4.62 (f_211_13,5) 13.08/4.62 (f_216_13,6) 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (30) 13.08/4.62 Obligation: 13.08/4.62 START: 3; 13.08/4.62 13.08/4.62 FROM: 1; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := x1; 13.08/4.62 oldX2 := x2; 13.08/4.62 oldX3 := x3; 13.08/4.62 oldX4 := x4; 13.08/4.62 oldX5 := x5; 13.08/4.62 oldX6 := x6; 13.08/4.62 oldX7 := x7; 13.08/4.62 oldX8 := x8; 13.08/4.62 oldX9 := x9; 13.08/4.62 oldX10 := x10; 13.08/4.62 oldX11 := x11; 13.08/4.62 oldX12 := x12; 13.08/4.62 oldX13 := nondet(); 13.08/4.62 oldX14 := nondet(); 13.08/4.62 oldX15 := nondet(); 13.08/4.62 oldX16 := nondet(); 13.08/4.62 oldX17 := nondet(); 13.08/4.62 oldX18 := nondet(); 13.08/4.62 oldX19 := nondet(); 13.08/4.62 oldX20 := nondet(); 13.08/4.62 oldX21 := nondet(); 13.08/4.62 assume(0 = 0 && oldX0 = 0); 13.08/4.62 x0 := 0; 13.08/4.62 x1 := oldX13; 13.08/4.62 x2 := oldX14; 13.08/4.62 x3 := 1; 13.08/4.62 x4 := oldX15; 13.08/4.62 x5 := oldX16; 13.08/4.62 x6 := oldX17; 13.08/4.62 x7 := oldX18; 13.08/4.62 x8 := oldX19; 13.08/4.62 x9 := oldX20; 13.08/4.62 x10 := oldX21; 13.08/4.62 x11 := 3; 13.08/4.62 x12 := 4; 13.08/4.62 TO: 2; 13.08/4.62 13.08/4.62 FROM: 3; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := x1; 13.08/4.62 oldX2 := x2; 13.08/4.62 oldX3 := x3; 13.08/4.62 oldX4 := x4; 13.08/4.62 oldX5 := x5; 13.08/4.62 oldX6 := x6; 13.08/4.62 oldX7 := x7; 13.08/4.62 oldX8 := x8; 13.08/4.62 oldX9 := x9; 13.08/4.62 oldX10 := x10; 13.08/4.62 oldX11 := x11; 13.08/4.62 oldX12 := x12; 13.08/4.62 oldX13 := nondet(); 13.08/4.62 oldX14 := nondet(); 13.08/4.62 oldX15 := nondet(); 13.08/4.62 oldX16 := nondet(); 13.08/4.62 oldX17 := nondet(); 13.08/4.62 oldX18 := nondet(); 13.08/4.62 oldX19 := nondet(); 13.08/4.62 assume(oldX13 > 0 && oldX15 < 0 && oldX14 > 0); 13.08/4.62 x0 := oldX13; 13.08/4.62 x1 := oldX14; 13.08/4.62 x2 := oldX15; 13.08/4.62 x3 := 1; 13.08/4.62 x4 := 0; 13.08/4.62 x5 := 3 + oldX13; 13.08/4.62 x6 := 3 + oldX14; 13.08/4.62 x7 := 3; 13.08/4.62 x8 := 4; 13.08/4.62 x9 := oldX16; 13.08/4.62 x10 := oldX17; 13.08/4.62 x11 := oldX18; 13.08/4.62 x12 := oldX19; 13.08/4.62 TO: 4; 13.08/4.62 13.08/4.62 FROM: 3; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := x1; 13.08/4.62 oldX2 := x2; 13.08/4.62 oldX3 := x3; 13.08/4.62 oldX4 := x4; 13.08/4.62 oldX5 := x5; 13.08/4.62 oldX6 := x6; 13.08/4.62 oldX7 := x7; 13.08/4.62 oldX8 := x8; 13.08/4.62 oldX9 := x9; 13.08/4.62 oldX10 := x10; 13.08/4.62 oldX11 := x11; 13.08/4.62 oldX12 := x12; 13.08/4.62 oldX13 := nondet(); 13.08/4.62 oldX14 := nondet(); 13.08/4.62 oldX15 := nondet(); 13.08/4.62 oldX16 := nondet(); 13.08/4.62 oldX17 := nondet(); 13.08/4.62 oldX18 := nondet(); 13.08/4.62 oldX19 := nondet(); 13.08/4.62 assume(oldX14 > 0 && oldX13 > 0); 13.08/4.62 x0 := oldX13; 13.08/4.62 x1 := oldX14; 13.08/4.62 x2 := 0; 13.08/4.62 x3 := 1; 13.08/4.62 x4 := 3 + oldX13; 13.08/4.62 x5 := 3 + oldX14; 13.08/4.62 x6 := 3; 13.08/4.62 x7 := 4; 13.08/4.62 x8 := oldX15; 13.08/4.62 x9 := oldX16; 13.08/4.62 x10 := oldX17; 13.08/4.62 x11 := oldX18; 13.08/4.62 x12 := oldX19; 13.08/4.62 TO: 5; 13.08/4.62 13.08/4.62 FROM: 1; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := x1; 13.08/4.62 oldX2 := x2; 13.08/4.62 oldX3 := x3; 13.08/4.62 oldX4 := x4; 13.08/4.62 oldX5 := x5; 13.08/4.62 oldX6 := x6; 13.08/4.62 oldX7 := x7; 13.08/4.62 oldX8 := x8; 13.08/4.62 oldX9 := x9; 13.08/4.62 oldX10 := x10; 13.08/4.62 oldX11 := x11; 13.08/4.62 oldX12 := x12; 13.08/4.62 oldX22 := oldX0 - 1; 13.08/4.62 oldX13 := nondet(); 13.08/4.62 oldX14 := nondet(); 13.08/4.62 oldX15 := nondet(); 13.08/4.62 oldX16 := nondet(); 13.08/4.62 oldX17 := nondet(); 13.08/4.62 oldX18 := nondet(); 13.08/4.62 oldX19 := nondet(); 13.08/4.62 oldX20 := nondet(); 13.08/4.62 oldX21 := nondet(); 13.08/4.62 assume(oldX22 > -1 && oldX0 = 1 + oldX22); 13.08/4.62 x0 := 0; 13.08/4.62 x1 := oldX13; 13.08/4.62 x2 := oldX14; 13.08/4.62 x3 := 1; 13.08/4.62 x4 := oldX15; 13.08/4.62 x5 := oldX16; 13.08/4.62 x6 := oldX17; 13.08/4.62 x7 := oldX18; 13.08/4.62 x8 := oldX19; 13.08/4.62 x9 := oldX20; 13.08/4.62 x10 := oldX21; 13.08/4.62 x11 := 3; 13.08/4.62 x12 := 4; 13.08/4.62 TO: 6; 13.08/4.62 13.08/4.62 FROM: 1; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := x1; 13.08/4.62 oldX2 := x2; 13.08/4.62 oldX3 := x3; 13.08/4.62 oldX4 := x4; 13.08/4.62 oldX5 := x5; 13.08/4.62 oldX6 := x6; 13.08/4.62 oldX7 := x7; 13.08/4.62 oldX8 := x8; 13.08/4.62 oldX9 := x9; 13.08/4.62 oldX10 := x10; 13.08/4.62 oldX11 := x11; 13.08/4.62 oldX12 := x12; 13.08/4.62 oldX25 := oldX0 - 1; 13.08/4.62 oldX13 := nondet(); 13.08/4.62 oldX14 := nondet(); 13.08/4.62 oldX15 := nondet(); 13.08/4.62 oldX16 := nondet(); 13.08/4.62 oldX17 := nondet(); 13.08/4.62 oldX18 := nondet(); 13.08/4.62 oldX19 := nondet(); 13.08/4.62 oldX20 := nondet(); 13.08/4.62 oldX21 := nondet(); 13.08/4.62 oldX22 := nondet(); 13.08/4.62 oldX23 := nondet(); 13.08/4.62 oldX24 := nondet(); 13.08/4.62 assume(oldX25 > -1 && oldX0 = 1 + oldX25); 13.08/4.62 x0 := 2; 13.08/4.62 x1 := oldX13; 13.08/4.62 x2 := oldX14; 13.08/4.62 x3 := oldX15; 13.08/4.62 x4 := oldX16; 13.08/4.62 x5 := oldX17; 13.08/4.62 x6 := oldX18; 13.08/4.62 x7 := oldX19; 13.08/4.62 x8 := oldX20; 13.08/4.62 x9 := oldX21; 13.08/4.62 x10 := oldX22; 13.08/4.62 x11 := oldX23; 13.08/4.62 x12 := oldX24; 13.08/4.62 TO: 1; 13.08/4.62 13.08/4.62 FROM: 3; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := x1; 13.08/4.62 oldX2 := x2; 13.08/4.62 oldX3 := x3; 13.08/4.62 oldX4 := x4; 13.08/4.62 oldX5 := x5; 13.08/4.62 oldX6 := x6; 13.08/4.62 oldX7 := x7; 13.08/4.62 oldX8 := x8; 13.08/4.62 oldX9 := x9; 13.08/4.62 oldX10 := x10; 13.08/4.62 oldX11 := x11; 13.08/4.62 oldX12 := x12; 13.08/4.62 oldX13 := nondet(); 13.08/4.62 oldX14 := nondet(); 13.08/4.62 oldX15 := nondet(); 13.08/4.62 oldX16 := nondet(); 13.08/4.62 oldX17 := nondet(); 13.08/4.62 oldX18 := nondet(); 13.08/4.62 oldX19 := nondet(); 13.08/4.62 oldX20 := nondet(); 13.08/4.62 oldX21 := nondet(); 13.08/4.62 oldX22 := nondet(); 13.08/4.62 oldX23 := nondet(); 13.08/4.62 oldX24 := nondet(); 13.08/4.62 oldX25 := nondet(); 13.08/4.62 assume(oldX13 > -1); 13.08/4.62 x0 := oldX13; 13.08/4.62 x1 := oldX14; 13.08/4.62 x2 := oldX15; 13.08/4.62 x3 := oldX16; 13.08/4.62 x4 := oldX17; 13.08/4.62 x5 := oldX18; 13.08/4.62 x6 := oldX19; 13.08/4.62 x7 := oldX20; 13.08/4.62 x8 := oldX21; 13.08/4.62 x9 := oldX22; 13.08/4.62 x10 := oldX23; 13.08/4.62 x11 := oldX24; 13.08/4.62 x12 := oldX25; 13.08/4.62 TO: 1; 13.08/4.62 13.08/4.62 FROM: 1; 13.08/4.62 oldX0 := x0; 13.08/4.62 oldX1 := x1; 13.08/4.62 oldX2 := x2; 13.08/4.62 oldX3 := x3; 13.08/4.62 oldX4 := x4; 13.08/4.62 oldX5 := x5; 13.08/4.62 oldX6 := x6; 13.08/4.62 oldX7 := x7; 13.08/4.62 oldX8 := x8; 13.08/4.62 oldX9 := x9; 13.08/4.62 oldX10 := x10; 13.08/4.62 oldX11 := x11; 13.08/4.62 oldX12 := x12; 13.08/4.62 oldX13 := oldX0 - 1; 13.08/4.62 oldX14 := nondet(); 13.08/4.62 oldX15 := nondet(); 13.08/4.62 oldX16 := nondet(); 13.08/4.62 oldX17 := nondet(); 13.08/4.62 oldX18 := nondet(); 13.08/4.62 oldX19 := nondet(); 13.08/4.62 oldX20 := nondet(); 13.08/4.62 oldX21 := nondet(); 13.08/4.62 oldX22 := nondet(); 13.08/4.62 oldX23 := nondet(); 13.08/4.62 oldX24 := nondet(); 13.08/4.62 oldX25 := nondet(); 13.08/4.62 assume(oldX13 > -1 && oldX0 = 1 + oldX13); 13.08/4.62 x0 := oldX0 - 1; 13.08/4.62 x1 := oldX14; 13.08/4.62 x2 := oldX15; 13.08/4.62 x3 := oldX16; 13.08/4.62 x4 := oldX17; 13.08/4.62 x5 := oldX18; 13.08/4.62 x6 := oldX19; 13.08/4.62 x7 := oldX20; 13.08/4.62 x8 := oldX21; 13.08/4.62 x9 := oldX22; 13.08/4.62 x10 := oldX23; 13.08/4.62 x11 := oldX24; 13.08/4.62 x12 := oldX25; 13.08/4.62 TO: 1; 13.08/4.62 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (31) T2 (COMPLETE) 13.08/4.62 Found this recurrent set for cutpoint 9: oldX13 == 2 and x0 == 2 13.08/4.62 13.08/4.62 ---------------------------------------- 13.08/4.62 13.08/4.62 (32) 13.08/4.62 NO 13.17/4.66 EOF