18.34/5.53 YES 18.34/5.54 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 18.34/5.54 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 18.34/5.54 18.34/5.54 18.34/5.54 Termination of the given C Problem could be proven: 18.34/5.54 18.34/5.54 (0) C Problem 18.34/5.54 (1) CToIRSProof [EQUIVALENT, 0 ms] 18.34/5.54 (2) IntTRS 18.34/5.54 (3) TerminationGraphProcessor [SOUND, 53 ms] 18.34/5.54 (4) IntTRS 18.34/5.54 (5) IntTRSCompressionProof [EQUIVALENT, 0 ms] 18.34/5.54 (6) IntTRS 18.34/5.54 (7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] 18.34/5.54 (8) IntTRS 18.34/5.54 (9) TerminationGraphProcessor [EQUIVALENT, 4 ms] 18.34/5.54 (10) IntTRS 18.34/5.54 (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] 18.34/5.54 (12) IntTRS 18.34/5.54 (13) TerminationGraphProcessor [EQUIVALENT, 40 ms] 18.34/5.54 (14) IntTRS 18.34/5.54 (15) IntTRSCompressionProof [EQUIVALENT, 0 ms] 18.34/5.54 (16) IntTRS 18.34/5.54 (17) RankingReductionPairProof [EQUIVALENT, 11 ms] 18.34/5.54 (18) YES 18.34/5.54 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (0) 18.34/5.54 Obligation: 18.34/5.54 c file /export/starexec/sandbox/benchmark/theBenchmark.c 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (1) CToIRSProof (EQUIVALENT) 18.34/5.54 Parsed C Integer Program as IRS. 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (2) 18.34/5.54 Obligation: 18.34/5.54 Rules: 18.34/5.54 f1(a, b, q, olda) -> f2(a, b, x_1, olda) :|: TRUE 18.34/5.54 f2(x, x1, x2, x3) -> f3(x4, x1, x2, x3) :|: TRUE 18.34/5.54 f3(x5, x6, x7, x8) -> f4(x5, x9, x7, x8) :|: TRUE 18.34/5.54 f5(x10, x11, x12, x13) -> f6(x10, x11, arith, x13) :|: TRUE && arith = x12 + x10 - 1 18.34/5.54 f6(x14, x15, x16, x17) -> f7(x14, x15, x16, x14) :|: TRUE 18.34/5.54 f7(x38, x39, x40, x41) -> f8(x42, x39, x40, x41) :|: TRUE && x42 = 3 * x41 - 4 * x39 18.34/5.54 f8(x43, x44, x45, x46) -> f9(x43, x47, x45, x46) :|: TRUE && x47 = 4 * x46 + 3 * x44 18.34/5.54 f4(x26, x27, x28, x29) -> f5(x26, x27, x28, x29) :|: x28 > 0 18.34/5.54 f9(x30, x31, x32, x33) -> f4(x30, x31, x32, x33) :|: TRUE 18.34/5.54 f4(x34, x35, x36, x37) -> f10(x34, x35, x36, x37) :|: x36 <= 0 18.34/5.54 Start term: f1(a, b, q, olda) 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (3) TerminationGraphProcessor (SOUND) 18.34/5.54 Constructed the termination graph and obtained one non-trivial SCC. 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (4) 18.34/5.54 Obligation: 18.34/5.54 Rules: 18.34/5.54 f4(x26, x27, x28, x29) -> f5(x26, x27, x28, x29) :|: x28 > 0 18.34/5.54 f9(x30, x31, x32, x33) -> f4(x30, x31, x32, x33) :|: TRUE 18.34/5.54 f8(x43, x44, x45, x46) -> f9(x43, x47, x45, x46) :|: TRUE && x47 = 4 * x46 + 3 * x44 18.34/5.54 f7(x38, x39, x40, x41) -> f8(x42, x39, x40, x41) :|: TRUE && x42 = 3 * x41 - 4 * x39 18.34/5.54 f6(x14, x15, x16, x17) -> f7(x14, x15, x16, x14) :|: TRUE 18.34/5.54 f5(x10, x11, x12, x13) -> f6(x10, x11, arith, x13) :|: TRUE && arith = x12 + x10 - 1 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (5) IntTRSCompressionProof (EQUIVALENT) 18.34/5.54 Compressed rules. 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (6) 18.34/5.54 Obligation: 18.34/5.54 Rules: 18.34/5.54 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 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (7) IntTRSUnneededArgumentFilterProof (EQUIVALENT) 18.34/5.54 Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: 18.34/5.54 18.34/5.54 f6(x1, x2, x3, x4) -> f6(x1, x2, x3) 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (8) 18.34/5.54 Obligation: 18.34/5.54 Rules: 18.34/5.54 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 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (9) TerminationGraphProcessor (EQUIVALENT) 18.34/5.54 Constructed the termination graph and obtained one non-trivial SCC. 18.34/5.54 18.34/5.54 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 18.34/5.54 has been transformed into 18.34/5.54 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. 18.34/5.54 18.34/5.54 18.34/5.54 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 18.34/5.54 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 18.34/5.54 have been merged into the new rule 18.34/5.54 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) 18.34/5.54 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (10) 18.34/5.54 Obligation: 18.34/5.54 Rules: 18.34/5.54 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 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (11) IntTRSCompressionProof (EQUIVALENT) 18.34/5.54 Compressed rules. 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (12) 18.34/5.54 Obligation: 18.34/5.54 Rules: 18.34/5.54 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 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (13) TerminationGraphProcessor (EQUIVALENT) 18.34/5.54 Constructed the termination graph and obtained one non-trivial SCC. 18.34/5.54 18.34/5.54 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 18.34/5.54 has been transformed into 18.34/5.54 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. 18.34/5.54 18.34/5.54 18.34/5.54 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 18.34/5.54 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 18.34/5.54 have been merged into the new rule 18.34/5.54 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) 18.34/5.54 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (14) 18.34/5.54 Obligation: 18.34/5.54 Rules: 18.34/5.54 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 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (15) IntTRSCompressionProof (EQUIVALENT) 18.34/5.54 Compressed rules. 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (16) 18.34/5.54 Obligation: 18.34/5.54 Rules: 18.34/5.54 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.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (17) RankingReductionPairProof (EQUIVALENT) 18.34/5.54 Interpretation: 18.34/5.54 [ f6 ] = 1/4*f6_3 + -11/40*f6_1 + -1/20*f6_2 18.34/5.54 18.34/5.54 The following rules are decreasing: 18.34/5.54 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.34/5.54 18.34/5.54 The following rules are bounded: 18.34/5.54 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.34/5.54 18.34/5.54 18.34/5.54 ---------------------------------------- 18.34/5.54 18.34/5.54 (18) 18.34/5.54 YES 18.69/5.64 EOF