/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) CToIRSProof [EQUIVALENT, 0 ms] (2) IntTRS (3) TerminationGraphProcessor [SOUND, 53 ms] (4) IntTRS (5) IntTRSCompressionProof [EQUIVALENT, 25 ms] (6) IntTRS (7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (8) IntTRS (9) TerminationGraphProcessor [EQUIVALENT, 2 ms] (10) IntTRS (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IntTRS (13) TerminationGraphProcessor [EQUIVALENT, 6 ms] (14) IntTRS (15) IntTRSCompressionProof [EQUIVALENT, 0 ms] (16) IntTRS (17) RankingReductionPairProof [EQUIVALENT, 12 ms] (18) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox/benchmark/theBenchmark.c ---------------------------------------- (1) CToIRSProof (EQUIVALENT) Parsed C Integer Program as IRS. ---------------------------------------- (2) Obligation: Rules: f1(a, b, q, olda) -> f2(a, b, x_1, olda) :|: TRUE f2(x, x1, x2, x3) -> f3(x4, x1, x2, x3) :|: TRUE f3(x5, x6, x7, x8) -> f4(x5, x9, x7, x8) :|: TRUE f5(x10, x11, x12, x13) -> f6(x10, x11, arith, x13) :|: TRUE && arith = x12 + x10 - 1 f6(x14, x15, x16, x17) -> f7(x14, x15, x16, x14) :|: TRUE f7(x38, x39, x40, x41) -> f8(x42, x39, x40, x41) :|: TRUE && x42 = 3 * x41 - 4 * x39 f8(x43, x44, x45, x46) -> f9(x43, x47, x45, x46) :|: TRUE && x47 = 4 * x46 + 3 * x44 f4(x26, x27, x28, x29) -> f5(x26, x27, x28, x29) :|: x28 > 0 f9(x30, x31, x32, x33) -> f4(x30, x31, x32, x33) :|: TRUE f4(x34, x35, x36, x37) -> f10(x34, x35, x36, x37) :|: x36 <= 0 Start term: f1(a, b, q, olda) ---------------------------------------- (3) TerminationGraphProcessor (SOUND) Constructed the termination graph and obtained one non-trivial SCC. ---------------------------------------- (4) Obligation: Rules: f4(x26, x27, x28, x29) -> f5(x26, x27, x28, x29) :|: x28 > 0 f9(x30, x31, x32, x33) -> f4(x30, x31, x32, x33) :|: TRUE f8(x43, x44, x45, x46) -> f9(x43, x47, x45, x46) :|: TRUE && x47 = 4 * x46 + 3 * x44 f7(x38, x39, x40, x41) -> f8(x42, x39, x40, x41) :|: TRUE && x42 = 3 * x41 - 4 * x39 f6(x14, x15, x16, x17) -> f7(x14, x15, x16, x14) :|: TRUE f5(x10, x11, x12, x13) -> f6(x10, x11, arith, x13) :|: TRUE && arith = x12 + x10 - 1 ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f6(x14:0, x15:0, x16:0, x17:0) -> f6(3 * x14:0 - 4 * x15:0, 4 * x14:0 + 3 * x15:0, x16:0 + (3 * x14:0 - 4 * x15:0) - 1, x14:0) :|: x16:0 > 0 ---------------------------------------- (7) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f6(x1, x2, x3, x4) -> f6(x1, x2, x3) ---------------------------------------- (8) Obligation: Rules: f6(x14:0, x15:0, x16:0) -> f6(3 * x14:0 - 4 * x15:0, 4 * x14:0 + 3 * x15:0, x16:0 + (3 * x14:0 - 4 * x15:0) - 1) :|: x16:0 > 0 ---------------------------------------- (9) TerminationGraphProcessor (EQUIVALENT) Constructed the termination graph and obtained one non-trivial SCC. f6(x14:0, x15:0, x16:0) -> f6(3 * x14:0 - 4 * x15:0, 4 * x14:0 + 3 * x15:0, x16:0 + (3 * x14:0 - 4 * x15:0) - 1) :|: x16:0 > 0 has been transformed into f6(x14:0, x15:0, x16:0) -> f6(3 * x14:0 - 4 * x15:0, 4 * x14:0 + 3 * x15:0, x16:0 + (3 * x14:0 - 4 * x15:0) - 1) :|: x16:0 > 0 && x8 > 0. f6(x14:0, x15:0, x16:0) -> f6(3 * x14:0 - 4 * x15:0, 4 * x14:0 + 3 * x15:0, x16:0 + (3 * x14:0 - 4 * x15:0) - 1) :|: x16:0 > 0 && x8 > 0 and f6(x14:0, x15:0, x16:0) -> f6(3 * x14:0 - 4 * x15:0, 4 * x14:0 + 3 * x15:0, x16:0 + (3 * x14:0 - 4 * x15:0) - 1) :|: x16:0 > 0 && x8 > 0 have been merged into the new rule f6(x17, x18, x19) -> f6(3 * (3 * x17 - 4 * x18) - 4 * (4 * x17 + 3 * x18), 4 * (3 * x17 - 4 * x18) + 3 * (4 * x17 + 3 * x18), x19 + (3 * x17 - 4 * x18) - 1 + (3 * (3 * x17 - 4 * x18) - 4 * (4 * x17 + 3 * x18)) - 1) :|: x19 > 0 && x20 > 0 && (x19 + (3 * x17 - 4 * x18) - 1 > 0 && x21 > 0) ---------------------------------------- (10) Obligation: Rules: f6(x22, x23, x24) -> f6(-7 * x22 + -24 * x23, 24 * x22 + -7 * x23, x24 + -4 * x22 + -28 * x23 + -2) :|: TRUE && x24 >= 1 && x25 >= 1 && x24 + 3 * x22 + -4 * x23 >= 2 && x26 >= 1 ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f6(x22:0, x23:0, x24:0) -> f6(-7 * x22:0 + -24 * x23:0, 24 * x22:0 + -7 * x23:0, x24:0 + -4 * x22:0 + -28 * x23:0 - 2) :|: x24:0 + 3 * x22:0 + -4 * x23:0 >= 2 && x26:0 > 0 && x24:0 > 0 && x25:0 > 0 ---------------------------------------- (13) TerminationGraphProcessor (EQUIVALENT) Constructed the termination graph and obtained one non-trivial SCC. f6(x22:0, x23:0, x24:0) -> f6(-7 * x22:0 + -24 * x23:0, 24 * x22:0 + -7 * x23:0, x24:0 + -4 * x22:0 + -28 * x23:0 - 2) :|: x24:0 + 3 * x22:0 + -4 * x23:0 >= 2 && x26:0 > 0 && x24:0 > 0 && x25:0 > 0 has been transformed into f6(x22:0, x23:0, x24:0) -> f6(-7 * x22:0 + -24 * x23:0, 24 * x22:0 + -7 * x23:0, x24:0 + -4 * x22:0 + -28 * x23:0 - 2) :|: x24:0 = x12 + -4 * x10 + -28 * x11 - 2 && (x23:0 = 24 * x10 + -7 * x11 && (x22:0 = -7 * x10 + -24 * x11 && (x24:0 + 3 * x22:0 + -4 * x23:0 >= 2 && x26:0 > 0 && x24:0 > 0 && x25:0 > 0))) && x12 + 3 * x10 + -4 * x11 >= 2 && x12 > 0. f6(x22:0, x23:0, x24:0) -> f6(-7 * x22:0 + -24 * x23:0, 24 * x22:0 + -7 * x23:0, x24:0 + -4 * x22:0 + -28 * x23:0 - 2) :|: x24:0 = x12 + -4 * x10 + -28 * x11 - 2 && (x23:0 = 24 * x10 + -7 * x11 && (x22:0 = -7 * x10 + -24 * x11 && (x24:0 + 3 * x22:0 + -4 * x23:0 >= 2 && x26:0 > 0 && x24:0 > 0 && x25:0 > 0))) && x12 + 3 * x10 + -4 * x11 >= 2 && x12 > 0 and f6(x22:0, x23:0, x24:0) -> f6(-7 * x22:0 + -24 * x23:0, 24 * x22:0 + -7 * x23:0, x24:0 + -4 * x22:0 + -28 * x23:0 - 2) :|: x24:0 = x12 + -4 * x10 + -28 * x11 - 2 && (x23:0 = 24 * x10 + -7 * x11 && (x22:0 = -7 * x10 + -24 * x11 && (x24:0 + 3 * x22:0 + -4 * x23:0 >= 2 && x26:0 > 0 && x24:0 > 0 && x25:0 > 0))) && x12 + 3 * x10 + -4 * x11 >= 2 && x12 > 0 have been merged into the new rule f6(x31, x32, x33) -> f6(-7 * (-7 * x31 + -24 * x32) + -24 * (24 * x31 + -7 * x32), 24 * (-7 * x31 + -24 * x32) + -7 * (24 * x31 + -7 * x32), x33 + -4 * x31 + -28 * x32 - 2 + -4 * (-7 * x31 + -24 * x32) + -28 * (24 * x31 + -7 * x32) - 2) :|: x33 = x34 + -4 * x35 + -28 * x36 - 2 && (x32 = 24 * x35 + -7 * x36 && (x31 = -7 * x35 + -24 * x36 && (x33 + 3 * x31 + -4 * x32 >= 2 && x37 > 0 && x33 > 0 && x38 > 0))) && x34 + 3 * x35 + -4 * x36 >= 2 && x34 > 0 && (x33 + -4 * x31 + -28 * x32 - 2 = x39 + -4 * x40 + -28 * x41 - 2 && (24 * x31 + -7 * x32 = 24 * x40 + -7 * x41 && (-7 * x31 + -24 * x32 = -7 * x40 + -24 * x41 && (x33 + -4 * x31 + -28 * x32 - 2 + 3 * (-7 * x31 + -24 * x32) + -4 * (24 * x31 + -7 * x32) >= 2 && x42 > 0 && x33 + -4 * x31 + -28 * x32 - 2 > 0 && x43 > 0))) && x39 + 3 * x40 + -4 * x41 >= 2 && x39 > 0) ---------------------------------------- (14) Obligation: Rules: f6(x44, x45, x46) -> f6(-527 * x44 + 336 * x45, -336 * x44 + -527 * x45, x46 + -648 * x44 + 264 * x45 + -4) :|: TRUE && x46 + -1 * x47 + 4 * x48 + 28 * x49 = -2 && x45 + -24 * x48 + 7 * x49 = 0 && x44 + 7 * x48 + 24 * x49 = 0 && x46 + 3 * x44 + -4 * x45 >= 2 && x50 >= 1 && x46 >= 1 && x51 >= 1 && x47 + 3 * x48 + -4 * x49 >= 2 && x47 >= 1 && x46 + -4 * x44 + -28 * x45 + -1 * x52 + 4 * x53 + 28 * x54 = 0 && 24 * x44 + -7 * x45 + -24 * x53 + 7 * x54 = 0 && -7 * x44 + -24 * x45 + 7 * x53 + 24 * x54 = 0 && x46 + -121 * x44 + -72 * x45 >= 4 && x55 >= 1 && x46 + -4 * x44 + -28 * x45 >= 3 && x56 >= 1 && x52 + 3 * x53 + -4 * x54 >= 2 && x52 >= 1 ---------------------------------------- (15) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (16) Obligation: Rules: f6(x44:0, x45:0, x46:0) -> f6(-527 * x44:0 + 336 * x45:0, -336 * x44:0 + -527 * x45:0, x46:0 + -648 * x44:0 + 264 * x45:0 - 4) :|: x52:0 + 3 * x53:0 + -4 * x54:0 >= 2 && x52:0 > 0 && x56:0 > 0 && x46:0 + -4 * x44:0 + -28 * x45:0 >= 3 && x55:0 > 0 && x46:0 + -121 * x44:0 + -72 * x45:0 >= 4 && 0 = -7 * x44:0 + -24 * x45:0 + 7 * x53:0 + 24 * x54:0 && 24 * x44:0 + -7 * x45:0 + -24 * x53:0 + 7 * x54:0 = 0 && x46:0 + -4 * x44:0 + -28 * x45:0 + -1 * x52:0 + 4 * x53:0 + 28 * x54:0 = 0 && x47:0 > 0 && x47:0 + 3 * x48:0 + -4 * x49:0 >= 2 && x51:0 > 0 && x46:0 > 0 && x50:0 > 0 && x46:0 + 3 * x44:0 + -4 * x45:0 >= 2 && x44:0 + 7 * x48:0 + 24 * x49:0 = 0 && x46:0 + -1 * x47:0 + 4 * x48:0 + 28 * x49:0 = -2 && x45:0 + -24 * x48:0 + 7 * x49:0 = 0 ---------------------------------------- (17) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f6 ] = 1/4*f6_3 + -11/40*f6_1 + -1/20*f6_2 The following rules are decreasing: f6(x44:0, x45:0, x46:0) -> f6(-527 * x44:0 + 336 * x45:0, -336 * x44:0 + -527 * x45:0, x46:0 + -648 * x44:0 + 264 * x45:0 - 4) :|: x52:0 + 3 * x53:0 + -4 * x54:0 >= 2 && x52:0 > 0 && x56:0 > 0 && x46:0 + -4 * x44:0 + -28 * x45:0 >= 3 && x55:0 > 0 && x46:0 + -121 * x44:0 + -72 * x45:0 >= 4 && 0 = -7 * x44:0 + -24 * x45:0 + 7 * x53:0 + 24 * x54:0 && 24 * x44:0 + -7 * x45:0 + -24 * x53:0 + 7 * x54:0 = 0 && x46:0 + -4 * x44:0 + -28 * x45:0 + -1 * x52:0 + 4 * x53:0 + 28 * x54:0 = 0 && x47:0 > 0 && x47:0 + 3 * x48:0 + -4 * x49:0 >= 2 && x51:0 > 0 && x46:0 > 0 && x50:0 > 0 && x46:0 + 3 * x44:0 + -4 * x45:0 >= 2 && x44:0 + 7 * x48:0 + 24 * x49:0 = 0 && x46:0 + -1 * x47:0 + 4 * x48:0 + 28 * x49:0 = -2 && x45:0 + -24 * x48:0 + 7 * x49:0 = 0 The following rules are bounded: f6(x44:0, x45:0, x46:0) -> f6(-527 * x44:0 + 336 * x45:0, -336 * x44:0 + -527 * x45:0, x46:0 + -648 * x44:0 + 264 * x45:0 - 4) :|: x52:0 + 3 * x53:0 + -4 * x54:0 >= 2 && x52:0 > 0 && x56:0 > 0 && x46:0 + -4 * x44:0 + -28 * x45:0 >= 3 && x55:0 > 0 && x46:0 + -121 * x44:0 + -72 * x45:0 >= 4 && 0 = -7 * x44:0 + -24 * x45:0 + 7 * x53:0 + 24 * x54:0 && 24 * x44:0 + -7 * x45:0 + -24 * x53:0 + 7 * x54:0 = 0 && x46:0 + -4 * x44:0 + -28 * x45:0 + -1 * x52:0 + 4 * x53:0 + 28 * x54:0 = 0 && x47:0 > 0 && x47:0 + 3 * x48:0 + -4 * x49:0 >= 2 && x51:0 > 0 && x46:0 > 0 && x50:0 > 0 && x46:0 + 3 * x44:0 + -4 * x45:0 >= 2 && x44:0 + 7 * x48:0 + 24 * x49:0 = 0 && x46:0 + -1 * x47:0 + 4 * x48:0 + 28 * x49:0 = -2 && x45:0 + -24 * x48:0 + 7 * x49:0 = 0 ---------------------------------------- (18) YES