/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination of the given C Problem could be proven: (0) C Problem (1) CToIRSProof [EQUIVALENT, 0 ms] (2) IntTRS (3) TerminationGraphProcessor [SOUND, 46 ms] (4) IntTRS (5) IntTRSCompressionProof [EQUIVALENT, 42 ms] (6) IntTRS (7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (8) IntTRS (9) TerminationGraphProcessor [EQUIVALENT, 10 ms] (10) IntTRS (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IntTRS (13) RankingReductionPairProof [EQUIVALENT, 0 ms] (14) IntTRS (15) CaseAnalysis [EQUIVALENT, 19 ms] (16) AND (17) IntTRS (18) TerminationGraphProcessor [EQUIVALENT, 7 ms] (19) IntTRS (20) IntTRSCompressionProof [EQUIVALENT, 0 ms] (21) IntTRS (22) RankingReductionPairProof [EQUIVALENT, 3 ms] (23) YES (24) IntTRS (25) IntTRSCompressionProof [EQUIVALENT, 0 ms] (26) IntTRS (27) RankingReductionPairProof [EQUIVALENT, 0 ms] (28) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox/benchmark/theBenchmark.c ---------------------------------------- (1) CToIRSProof (EQUIVALENT) Parsed C Integer Program as IRS. ---------------------------------------- (2) Obligation: Rules: f1(x, y, oldx) -> f2(x_1, y, oldx) :|: TRUE f2(x1, x2, x3) -> f3(x1, x4, x3) :|: TRUE f4(x5, x6, x7) -> f5(x5, x6, x5) :|: TRUE f5(x8, x9, x10) -> f6(arith, x9, x10) :|: TRUE && arith = x9 - 1 f6(x23, x24, x25) -> f7(x23, x26, x25) :|: TRUE && x26 = x25 - 1 f3(x14, x15, x16) -> f4(x14, x15, x16) :|: x14 >= 0 f3(x27, x28, x29) -> f4(x27, x28, x29) :|: x28 >= 0 f7(x17, x18, x19) -> f3(x17, x18, x19) :|: TRUE f3(x20, x21, x22) -> f8(x20, x21, x22) :|: x20 < 0 && x21 < 0 Start term: f1(x, y, oldx) ---------------------------------------- (3) TerminationGraphProcessor (SOUND) Constructed the termination graph and obtained one non-trivial SCC. ---------------------------------------- (4) Obligation: Rules: f3(x14, x15, x16) -> f4(x14, x15, x16) :|: x14 >= 0 f7(x17, x18, x19) -> f3(x17, x18, x19) :|: TRUE f6(x23, x24, x25) -> f7(x23, x26, x25) :|: TRUE && x26 = x25 - 1 f5(x8, x9, x10) -> f6(arith, x9, x10) :|: TRUE && arith = x9 - 1 f4(x5, x6, x7) -> f5(x5, x6, x5) :|: TRUE f3(x27, x28, x29) -> f4(x27, x28, x29) :|: x28 >= 0 ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f5(x8:0, x9:0, x10:0) -> f5(x9:0 - 1, x10:0 - 1, x9:0 - 1) :|: x10:0 > 0 f5(x, x1, x2) -> f5(x1 - 1, x2 - 1, x1 - 1) :|: x1 > 0 ---------------------------------------- (7) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f5(x1, x2, x3) -> f5(x2, x3) ---------------------------------------- (8) Obligation: Rules: f5(x9:0, x10:0) -> f5(x10:0 - 1, x9:0 - 1) :|: x10:0 > 0 f5(x1, x2) -> f5(x2 - 1, x1 - 1) :|: x1 > 0 ---------------------------------------- (9) TerminationGraphProcessor (EQUIVALENT) Constructed the termination graph and obtained one non-trivial SCC. f5(x9:0, x10:0) -> f5(x10:0 - 1, x9:0 - 1) :|: x10:0 > 0 and f5(x9:0, x10:0) -> f5(x10:0 - 1, x9:0 - 1) :|: x10:0 > 0 have been merged into the new rule f5(x10, x11) -> f5(x10 - 1 - 1, x11 - 1 - 1) :|: x11 > 0 && x10 - 1 > 0 f5(x9:0, x10:0) -> f5(x10:0 - 1, x9:0 - 1) :|: x10:0 > 0 and f5(x1, x2) -> f5(x2 - 1, x1 - 1) :|: x1 > 0 have been merged into the new rule f5(x18, x19) -> f5(x18 - 1 - 1, x19 - 1 - 1) :|: x19 > 0 && x19 - 1 > 0 ---------------------------------------- (10) Obligation: Rules: f5(x12, x13) -> f5(x12 + -2, x13 + -2) :|: TRUE && x13 >= 1 && x12 >= 2 f5(x20, x21) -> f5(x20 + -2, x21 + -2) :|: TRUE && x21 >= 2 f5(x1, x2) -> f5(x2 + -1, x1 + -1) :|: TRUE && x1 >= 1 ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f5(x1:0, x2:0) -> f5(x2:0 - 1, x1:0 - 1) :|: x1:0 > 0 f5(x20:0, x21:0) -> f5(x20:0 - 2, x21:0 - 2) :|: x21:0 > 1 f5(x12:0, x13:0) -> f5(x12:0 - 2, x13:0 - 2) :|: x12:0 > 1 && x13:0 > 0 ---------------------------------------- (13) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f5 ] = 1/2*f5_1 + 1/2*f5_2 The following rules are decreasing: f5(x1:0, x2:0) -> f5(x2:0 - 1, x1:0 - 1) :|: x1:0 > 0 f5(x20:0, x21:0) -> f5(x20:0 - 2, x21:0 - 2) :|: x21:0 > 1 f5(x12:0, x13:0) -> f5(x12:0 - 2, x13:0 - 2) :|: x12:0 > 1 && x13:0 > 0 The following rules are bounded: f5(x12:0, x13:0) -> f5(x12:0 - 2, x13:0 - 2) :|: x12:0 > 1 && x13:0 > 0 ---------------------------------------- (14) Obligation: Rules: f5(x1:0, x2:0) -> f5(x2:0 - 1, x1:0 - 1) :|: x1:0 > 0 f5(x20:0, x21:0) -> f5(x20:0 - 2, x21:0 - 2) :|: x21:0 > 1 ---------------------------------------- (15) CaseAnalysis (EQUIVALENT) Found the following inductive condition: f5(x, x1): -1 - 3*x - 3*x1>=0 ---------------------------------------- (16) Complex Obligation (AND) ---------------------------------------- (17) Obligation: Rules: f5(x1:0, x2:0) -> f5(x2:0 - 1, x1:0 - 1) :|: x1:0 > 0 && -1 + -3 * x1:0 + -3 * x2:0 >= 0 f5(x20:0, x21:0) -> f5(x20:0 - 2, x21:0 - 2) :|: x21:0 > 1 && -1 + -3 * x20:0 + -3 * x21:0 >= 0 ---------------------------------------- (18) TerminationGraphProcessor (EQUIVALENT) Constructed the termination graph and obtained one non-trivial SCC. ---------------------------------------- (19) Obligation: Rules: f5(x20:0, x21:0) -> f5(x20:0 - 2, x21:0 - 2) :|: x21:0 > 1 && -1 + -3 * x20:0 + -3 * x21:0 >= 0 ---------------------------------------- (20) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (21) Obligation: Rules: f5(x20:0:0, x21:0:0) -> f5(x20:0:0 - 2, x21:0:0 - 2) :|: x21:0:0 > 1 && 0 <= -1 + -3 * x20:0:0 + -3 * x21:0:0 ---------------------------------------- (22) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f5 ] = 1/2*f5_2 The following rules are decreasing: f5(x20:0:0, x21:0:0) -> f5(x20:0:0 - 2, x21:0:0 - 2) :|: x21:0:0 > 1 && 0 <= -1 + -3 * x20:0:0 + -3 * x21:0:0 The following rules are bounded: f5(x20:0:0, x21:0:0) -> f5(x20:0:0 - 2, x21:0:0 - 2) :|: x21:0:0 > 1 && 0 <= -1 + -3 * x20:0:0 + -3 * x21:0:0 ---------------------------------------- (23) YES ---------------------------------------- (24) Obligation: Rules: f5(x1:0, x2:0) -> f5(x2:0 - 1, x1:0 - 1) :|: x1:0 > 0 && -1 + -3 * x1:0 + -3 * x2:0 < 0 f5(x20:0, x21:0) -> f5(x20:0 - 2, x21:0 - 2) :|: x21:0 > 1 && -1 + -3 * x20:0 + -3 * x21:0 < 0 ---------------------------------------- (25) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (26) Obligation: Rules: f5(x20:0:0, x21:0:0) -> f5(x20:0:0 - 2, x21:0:0 - 2) :|: x21:0:0 > 1 && 0 > -1 + -3 * x20:0:0 + -3 * x21:0:0 f5(x1:0:0, x2:0:0) -> f5(x2:0:0 - 1, x1:0:0 - 1) :|: x1:0:0 > 0 && 0 > -1 + -3 * x1:0:0 + -3 * x2:0:0 ---------------------------------------- (27) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f5 ] = 1/2*f5_2 + 1/2*f5_1 The following rules are decreasing: f5(x20:0:0, x21:0:0) -> f5(x20:0:0 - 2, x21:0:0 - 2) :|: x21:0:0 > 1 && 0 > -1 + -3 * x20:0:0 + -3 * x21:0:0 f5(x1:0:0, x2:0:0) -> f5(x2:0:0 - 1, x1:0:0 - 1) :|: x1:0:0 > 0 && 0 > -1 + -3 * x1:0:0 + -3 * x2:0:0 The following rules are bounded: f5(x20:0:0, x21:0:0) -> f5(x20:0:0 - 2, x21:0:0 - 2) :|: x21:0:0 > 1 && 0 > -1 + -3 * x20:0:0 + -3 * x21:0:0 f5(x1:0:0, x2:0:0) -> f5(x2:0:0 - 1, x1:0:0 - 1) :|: x1:0:0 > 0 && 0 > -1 + -3 * x1:0:0 + -3 * x2:0:0 ---------------------------------------- (28) YES