8.57/2.96 YES 8.57/2.98 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 8.57/2.98 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.57/2.98 8.57/2.98 8.57/2.98 Termination of the given C Problem could be proven: 8.57/2.98 8.57/2.98 (0) C Problem 8.57/2.98 (1) CToIRSProof [EQUIVALENT, 0 ms] 8.57/2.98 (2) IntTRS 8.57/2.98 (3) TerminationGraphProcessor [SOUND, 55 ms] 8.57/2.98 (4) IntTRS 8.57/2.98 (5) IntTRSCompressionProof [EQUIVALENT, 31 ms] 8.57/2.98 (6) IntTRS 8.57/2.98 (7) CaseAnalysis [EQUIVALENT, 14 ms] 8.57/2.98 (8) AND 8.57/2.98 (9) IntTRS 8.57/2.98 (10) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.57/2.98 (11) IntTRS 8.57/2.98 (12) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 8.57/2.98 (13) YES 8.57/2.98 (14) IntTRS 8.57/2.98 (15) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.57/2.98 (16) IntTRS 8.57/2.98 (17) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 8.57/2.98 (18) YES 8.57/2.98 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (0) 8.57/2.98 Obligation: 8.57/2.98 c file /export/starexec/sandbox/benchmark/theBenchmark.c 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (1) CToIRSProof (EQUIVALENT) 8.57/2.98 Parsed C Integer Program as IRS. 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (2) 8.57/2.98 Obligation: 8.57/2.98 Rules: 8.57/2.98 f1(c, x) -> f2(c, x_1) :|: TRUE 8.57/2.98 f2(x1, x2) -> f3(x3, x2) :|: TRUE 8.57/2.98 f7(x4, x5) -> f8(x4, arith) :|: TRUE && arith = x5 - x4 8.57/2.98 f8(x22, x23) -> f9(x24, x23) :|: TRUE && x24 = x22 + 1 8.57/2.98 f4(x8, x9) -> f7(x8, x9) :|: x9 + x8 >= 0 8.57/2.98 f9(x10, x11) -> f4(x10, x11) :|: TRUE 8.57/2.98 f4(x12, x13) -> f10(x12, x13) :|: x13 + x12 < 0 8.57/2.98 f3(x14, x15) -> f4(x14, x15) :|: x14 >= 2 8.57/2.98 f3(x16, x17) -> f5(x16, x17) :|: x16 < 2 8.57/2.98 f10(x18, x19) -> f6(x18, x19) :|: TRUE 8.57/2.98 f5(x20, x21) -> f6(x20, x21) :|: TRUE 8.57/2.98 Start term: f1(c, x) 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (3) TerminationGraphProcessor (SOUND) 8.57/2.98 Constructed the termination graph and obtained one non-trivial SCC. 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (4) 8.57/2.98 Obligation: 8.57/2.98 Rules: 8.57/2.98 f4(x8, x9) -> f7(x8, x9) :|: x9 + x8 >= 0 8.57/2.98 f9(x10, x11) -> f4(x10, x11) :|: TRUE 8.57/2.98 f8(x22, x23) -> f9(x24, x23) :|: TRUE && x24 = x22 + 1 8.57/2.98 f7(x4, x5) -> f8(x4, arith) :|: TRUE && arith = x5 - x4 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (5) IntTRSCompressionProof (EQUIVALENT) 8.57/2.98 Compressed rules. 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (6) 8.57/2.98 Obligation: 8.57/2.98 Rules: 8.57/2.98 f8(x22:0, x23:0) -> f8(x22:0 + 1, x23:0 - (x22:0 + 1)) :|: x23:0 + (x22:0 + 1) >= 0 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (7) CaseAnalysis (EQUIVALENT) 8.57/2.98 Found the following inductive condition: 8.57/2.98 f8(x0, x1): -1 + x0>=0 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (8) 8.57/2.98 Complex Obligation (AND) 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (9) 8.57/2.98 Obligation: 8.57/2.98 Rules: 8.57/2.98 f8(x22:0, x23:0) -> f8(x22:0 + 1, x23:0 - (x22:0 + 1)) :|: x23:0 + (x22:0 + 1) >= 0 && x22:0 + -1 >= 0 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (10) IntTRSCompressionProof (EQUIVALENT) 8.57/2.98 Compressed rules. 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (11) 8.57/2.98 Obligation: 8.57/2.98 Rules: 8.57/2.98 f8(x22:0:0, x23:0:0) -> f8(x22:0:0 + 1, x23:0:0 - (x22:0:0 + 1)) :|: x23:0:0 + (x22:0:0 + 1) >= 0 && x22:0:0 > 0 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (12) PolynomialOrderProcessor (EQUIVALENT) 8.57/2.98 Found the following polynomial interpretation: 8.57/2.98 [f8(x, x1)] = 1 + x + x1 8.57/2.98 8.57/2.98 The following rules are decreasing: 8.57/2.98 f8(x22:0:0, x23:0:0) -> f8(x22:0:0 + 1, x23:0:0 - (x22:0:0 + 1)) :|: x23:0:0 + (x22:0:0 + 1) >= 0 && x22:0:0 > 0 8.57/2.98 The following rules are bounded: 8.57/2.98 f8(x22:0:0, x23:0:0) -> f8(x22:0:0 + 1, x23:0:0 - (x22:0:0 + 1)) :|: x23:0:0 + (x22:0:0 + 1) >= 0 && x22:0:0 > 0 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (13) 8.57/2.98 YES 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (14) 8.57/2.98 Obligation: 8.57/2.98 Rules: 8.57/2.98 f8(x22:0, x23:0) -> f8(x22:0 + 1, x23:0 - (x22:0 + 1)) :|: x23:0 + (x22:0 + 1) >= 0 && x22:0 + -1 < 0 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (15) IntTRSCompressionProof (EQUIVALENT) 8.57/2.98 Compressed rules. 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (16) 8.57/2.98 Obligation: 8.57/2.98 Rules: 8.57/2.98 f8(x22:0:0, x23:0:0) -> f8(x22:0:0 + 1, x23:0:0 - (x22:0:0 + 1)) :|: x23:0:0 + (x22:0:0 + 1) >= 0 && x22:0:0 < 1 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (17) PolynomialOrderProcessor (EQUIVALENT) 8.57/2.98 Found the following polynomial interpretation: 8.57/2.98 [f8(x, x1)] = -x 8.57/2.98 8.57/2.98 The following rules are decreasing: 8.57/2.98 f8(x22:0:0, x23:0:0) -> f8(x22:0:0 + 1, x23:0:0 - (x22:0:0 + 1)) :|: x23:0:0 + (x22:0:0 + 1) >= 0 && x22:0:0 < 1 8.57/2.98 The following rules are bounded: 8.57/2.98 f8(x22:0:0, x23:0:0) -> f8(x22:0:0 + 1, x23:0:0 - (x22:0:0 + 1)) :|: x23:0:0 + (x22:0:0 + 1) >= 0 && x22:0:0 < 1 8.57/2.98 8.57/2.98 ---------------------------------------- 8.57/2.98 8.57/2.98 (18) 8.57/2.98 YES 8.93/3.01 EOF