26.94/7.71 YES 26.94/7.72 proof of /export/starexec/sandbox2/benchmark/theBenchmark.c 26.94/7.72 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 26.94/7.72 26.94/7.72 26.94/7.72 Termination of the given C Problem could be proven: 26.94/7.72 26.94/7.72 (0) C Problem 26.94/7.72 (1) CToIRSProof [EQUIVALENT, 0 ms] 26.94/7.72 (2) IntTRS 26.94/7.72 (3) TerminationGraphProcessor [SOUND, 104 ms] 26.94/7.72 (4) IntTRS 26.94/7.72 (5) IntTRSCompressionProof [EQUIVALENT, 14 ms] 26.94/7.72 (6) IntTRS 26.94/7.72 (7) RankingReductionPairProof [EQUIVALENT, 58 ms] 26.94/7.72 (8) AND 26.94/7.72 (9) IntTRS 26.94/7.72 (10) IntTRSCompressionProof [EQUIVALENT, 0 ms] 26.94/7.72 (11) IntTRS 26.94/7.72 (12) RankingReductionPairProof [EQUIVALENT, 12 ms] 26.94/7.72 (13) AND 26.94/7.72 (14) IntTRS 26.94/7.72 (15) IntTRSCompressionProof [EQUIVALENT, 0 ms] 26.94/7.72 (16) IntTRS 26.94/7.72 (17) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 26.94/7.72 (18) YES 26.94/7.72 (19) IntTRS 26.94/7.72 (20) IntTRSCompressionProof [EQUIVALENT, 0 ms] 26.94/7.72 (21) IntTRS 26.94/7.72 (22) RankingReductionPairProof [EQUIVALENT, 7 ms] 26.94/7.72 (23) YES 26.94/7.72 (24) IntTRS 26.94/7.72 (25) IntTRSCompressionProof [EQUIVALENT, 0 ms] 26.94/7.72 (26) IntTRS 26.94/7.72 (27) RankingReductionPairProof [EQUIVALENT, 14 ms] 26.94/7.72 (28) AND 26.94/7.72 (29) IntTRS 26.94/7.72 (30) IntTRSCompressionProof [EQUIVALENT, 0 ms] 26.94/7.72 (31) IntTRS 26.94/7.72 (32) RankingReductionPairProof [EQUIVALENT, 8 ms] 26.94/7.72 (33) IntTRS 26.94/7.72 (34) IntTRSCompressionProof [EQUIVALENT, 0 ms] 26.94/7.72 (35) IntTRS 26.94/7.72 (36) PolynomialOrderProcessor [EQUIVALENT, 3 ms] 26.94/7.72 (37) YES 26.94/7.72 (38) IntTRS 26.94/7.72 (39) TerminationGraphProcessor [EQUIVALENT, 0 ms] 26.94/7.72 (40) YES 26.94/7.72 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (0) 26.94/7.72 Obligation: 26.94/7.72 c file /export/starexec/sandbox2/benchmark/theBenchmark.c 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (1) CToIRSProof (EQUIVALENT) 26.94/7.72 Parsed C Integer Program as IRS. 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (2) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f1(MAX, a, b, c) -> f2(1000, a, b, c) :|: TRUE 26.94/7.72 f2(x, x1, x2, x3) -> f3(x, 1, x2, x3) :|: TRUE 26.94/7.72 f3(x4, x5, x6, x7) -> f4(x4, x5, 1, x7) :|: TRUE 26.94/7.72 f4(x8, x9, x10, x11) -> f5(x8, x9, x10, 1) :|: TRUE 26.94/7.72 f6(x12, x13, x14, x15) -> f7(x12, arith, x14, x15) :|: TRUE && arith = x13 + 1 26.94/7.72 f8(x16, x17, x18, x19) -> f11(x16, 1, x18, x19) :|: TRUE 26.94/7.72 f11(x76, x77, x78, x79) -> f12(x76, x77, x80, x79) :|: TRUE && x80 = x78 + 1 26.94/7.72 f7(x24, x25, x26, x27) -> f8(x24, x25, x26, x27) :|: x25 > x24 26.94/7.72 f7(x28, x29, x30, x31) -> f9(x28, x29, x30, x31) :|: x29 <= x28 26.94/7.72 f12(x32, x33, x34, x35) -> f10(x32, x33, x34, x35) :|: TRUE 26.94/7.72 f9(x36, x37, x38, x39) -> f10(x36, x37, x38, x39) :|: TRUE 26.94/7.72 f13(x40, x41, x42, x43) -> f16(x40, x41, 1, x43) :|: TRUE 26.94/7.72 f16(x81, x82, x83, x84) -> f17(x81, x82, x83, x85) :|: TRUE && x85 = x84 + 1 26.94/7.72 f10(x48, x49, x50, x51) -> f13(x48, x49, x50, x51) :|: x50 > x48 26.94/7.72 f10(x52, x53, x54, x55) -> f14(x52, x53, x54, x55) :|: x54 <= x52 26.94/7.72 f17(x56, x57, x58, x59) -> f15(x56, x57, x58, x59) :|: TRUE 26.94/7.72 f14(x60, x61, x62, x63) -> f15(x60, x61, x62, x63) :|: TRUE 26.94/7.72 f5(x64, x65, x66, x67) -> f6(x64, x65, x66, x67) :|: x65 * x65 * x65 < x66 * x66 * x66 + x67 * x67 * x67 && x67 <= x64 26.94/7.72 f5(x86, x87, x88, x89) -> f6(x86, x87, x88, x89) :|: x87 * x87 * x87 > x88 * x88 * x88 + x89 * x89 * x89 && x89 <= x86 26.94/7.72 f15(x68, x69, x70, x71) -> f5(x68, x69, x70, x71) :|: TRUE 26.94/7.72 f5(x72, x73, x74, x75) -> f18(x72, x73, x74, x75) :|: x73 * x73 * x73 = x74 * x74 * x74 + x75 * x75 * x75 26.94/7.72 f5(x90, x91, x92, x93) -> f18(x90, x91, x92, x93) :|: x93 > x90 26.94/7.72 Start term: f1(MAX, a, b, c) 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (3) TerminationGraphProcessor (SOUND) 26.94/7.72 Constructed the termination graph and obtained one non-trivial SCC. 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (4) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f5(x64, x65, x66, x67) -> f6(x64, x65, x66, x67) :|: x65 * x65 * x65 < x66 * x66 * x66 + x67 * x67 * x67 && x67 <= x64 26.94/7.72 f15(x68, x69, x70, x71) -> f5(x68, x69, x70, x71) :|: TRUE 26.94/7.72 f17(x56, x57, x58, x59) -> f15(x56, x57, x58, x59) :|: TRUE 26.94/7.72 f16(x81, x82, x83, x84) -> f17(x81, x82, x83, x85) :|: TRUE && x85 = x84 + 1 26.94/7.72 f13(x40, x41, x42, x43) -> f16(x40, x41, 1, x43) :|: TRUE 26.94/7.72 f10(x48, x49, x50, x51) -> f13(x48, x49, x50, x51) :|: x50 > x48 26.94/7.72 f12(x32, x33, x34, x35) -> f10(x32, x33, x34, x35) :|: TRUE 26.94/7.72 f11(x76, x77, x78, x79) -> f12(x76, x77, x80, x79) :|: TRUE && x80 = x78 + 1 26.94/7.72 f8(x16, x17, x18, x19) -> f11(x16, 1, x18, x19) :|: TRUE 26.94/7.72 f7(x24, x25, x26, x27) -> f8(x24, x25, x26, x27) :|: x25 > x24 26.94/7.72 f6(x12, x13, x14, x15) -> f7(x12, arith, x14, x15) :|: TRUE && arith = x13 + 1 26.94/7.72 f5(x86, x87, x88, x89) -> f6(x86, x87, x88, x89) :|: x87 * x87 * x87 > x88 * x88 * x88 + x89 * x89 * x89 && x89 <= x86 26.94/7.72 f9(x36, x37, x38, x39) -> f10(x36, x37, x38, x39) :|: TRUE 26.94/7.72 f7(x28, x29, x30, x31) -> f9(x28, x29, x30, x31) :|: x29 <= x28 26.94/7.72 f14(x60, x61, x62, x63) -> f15(x60, x61, x62, x63) :|: TRUE 26.94/7.72 f10(x52, x53, x54, x55) -> f14(x52, x53, x54, x55) :|: x54 <= x52 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (5) IntTRSCompressionProof (EQUIVALENT) 26.94/7.72 Compressed rules. 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (6) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x68:0, x69:0, x70:0, x71:0) -> f7(x68:0, x69:0 + 1, x70:0, x71:0) :|: x70:0 * x70:0 * x70:0 + x71:0 * x71:0 * x71:0 > x69:0 * x69:0 * x69:0 && x71:0 <= x68:0 26.94/7.72 f7(x24:0, x25:0, x26:0, x27:0) -> f10(x24:0, 1, x26:0 + 1, x27:0) :|: x25:0 > x24:0 26.94/7.72 f10(x48:0, x49:0, x50:0, x51:0) -> f15(x48:0, x49:0, 1, x51:0 + 1) :|: x50:0 > x48:0 26.94/7.72 f15(x, x1, x2, x3) -> f7(x, x1 + 1, x2, x3) :|: x2 * x2 * x2 + x3 * x3 * x3 < x1 * x1 * x1 && x3 <= x 26.94/7.72 f10(x52:0, x53:0, x54:0, x55:0) -> f15(x52:0, x53:0, x54:0, x55:0) :|: x54:0 <= x52:0 26.94/7.72 f7(x28:0, x29:0, x30:0, x31:0) -> f10(x28:0, x29:0, x30:0, x31:0) :|: x29:0 <= x28:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (7) RankingReductionPairProof (EQUIVALENT) 26.94/7.72 Interpretation: 26.94/7.72 [ f15 ] = -3*f15_4 + 3*f15_1 26.94/7.72 [ f7 ] = 3*f7_1 + -3*f7_4 26.94/7.72 [ f10 ] = 3*f10_1 + -3*f10_4 26.94/7.72 26.94/7.72 The following rules are decreasing: 26.94/7.72 f10(x48:0, x49:0, x50:0, x51:0) -> f15(x48:0, x49:0, 1, x51:0 + 1) :|: x50:0 > x48:0 26.94/7.72 26.94/7.72 The following rules are bounded: 26.94/7.72 f15(x, x1, x2, x3) -> f7(x, x1 + 1, x2, x3) :|: x2 * x2 * x2 + x3 * x3 * x3 < x1 * x1 * x1 && x3 <= x 26.94/7.72 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (8) 26.94/7.72 Complex Obligation (AND) 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (9) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x68:0, x69:0, x70:0, x71:0) -> f7(x68:0, x69:0 + 1, x70:0, x71:0) :|: x70:0 * x70:0 * x70:0 + x71:0 * x71:0 * x71:0 > x69:0 * x69:0 * x69:0 && x71:0 <= x68:0 26.94/7.72 f7(x24:0, x25:0, x26:0, x27:0) -> f10(x24:0, 1, x26:0 + 1, x27:0) :|: x25:0 > x24:0 26.94/7.72 f15(x, x1, x2, x3) -> f7(x, x1 + 1, x2, x3) :|: x2 * x2 * x2 + x3 * x3 * x3 < x1 * x1 * x1 && x3 <= x 26.94/7.72 f10(x52:0, x53:0, x54:0, x55:0) -> f15(x52:0, x53:0, x54:0, x55:0) :|: x54:0 <= x52:0 26.94/7.72 f7(x28:0, x29:0, x30:0, x31:0) -> f10(x28:0, x29:0, x30:0, x31:0) :|: x29:0 <= x28:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (10) IntTRSCompressionProof (EQUIVALENT) 26.94/7.72 Compressed rules. 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (11) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f7(x24:0:0, x25:0:0, x26:0:0, x27:0:0) -> f15(x24:0:0, 1, x26:0:0 + 1, x27:0:0) :|: x25:0:0 > x24:0:0 && x26:0:0 + 1 <= x24:0:0 26.94/7.72 f15(x68:0:0, x69:0:0, x70:0:0, x71:0:0) -> f7(x68:0:0, x69:0:0 + 1, x70:0:0, x71:0:0) :|: x70:0:0 * x70:0:0 * x70:0:0 + x71:0:0 * x71:0:0 * x71:0:0 > x69:0:0 * x69:0:0 * x69:0:0 && x71:0:0 <= x68:0:0 26.94/7.72 f7(x28:0:0, x29:0:0, x30:0:0, x31:0:0) -> f15(x28:0:0, x29:0:0, x30:0:0, x31:0:0) :|: x29:0:0 <= x28:0:0 && x30:0:0 <= x28:0:0 26.94/7.72 f15(x:0, x1:0, x2:0, x3:0) -> f7(x:0, x1:0 + 1, x2:0, x3:0) :|: x2:0 * x2:0 * x2:0 + x3:0 * x3:0 * x3:0 < x1:0 * x1:0 * x1:0 && x:0 >= x3:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (12) RankingReductionPairProof (EQUIVALENT) 26.94/7.72 Interpretation: 26.94/7.72 [ f7 ] = 2*f7_1 + -2*f7_3 + 1 26.94/7.72 [ f15 ] = 2*f15_1 + -2*f15_3 + 1 26.94/7.72 26.94/7.72 The following rules are decreasing: 26.94/7.72 f7(x24:0:0, x25:0:0, x26:0:0, x27:0:0) -> f15(x24:0:0, 1, x26:0:0 + 1, x27:0:0) :|: x25:0:0 > x24:0:0 && x26:0:0 + 1 <= x24:0:0 26.94/7.72 26.94/7.72 The following rules are bounded: 26.94/7.72 f7(x28:0:0, x29:0:0, x30:0:0, x31:0:0) -> f15(x28:0:0, x29:0:0, x30:0:0, x31:0:0) :|: x29:0:0 <= x28:0:0 && x30:0:0 <= x28:0:0 26.94/7.72 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (13) 26.94/7.72 Complex Obligation (AND) 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (14) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x68:0:0, x69:0:0, x70:0:0, x71:0:0) -> f7(x68:0:0, x69:0:0 + 1, x70:0:0, x71:0:0) :|: x70:0:0 * x70:0:0 * x70:0:0 + x71:0:0 * x71:0:0 * x71:0:0 > x69:0:0 * x69:0:0 * x69:0:0 && x71:0:0 <= x68:0:0 26.94/7.72 f7(x28:0:0, x29:0:0, x30:0:0, x31:0:0) -> f15(x28:0:0, x29:0:0, x30:0:0, x31:0:0) :|: x29:0:0 <= x28:0:0 && x30:0:0 <= x28:0:0 26.94/7.72 f15(x:0, x1:0, x2:0, x3:0) -> f7(x:0, x1:0 + 1, x2:0, x3:0) :|: x2:0 * x2:0 * x2:0 + x3:0 * x3:0 * x3:0 < x1:0 * x1:0 * x1:0 && x:0 >= x3:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (15) IntTRSCompressionProof (EQUIVALENT) 26.94/7.72 Compressed rules. 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (16) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x68:0:0:0, x69:0:0:0, x70:0:0:0, x71:0:0:0) -> f15(x68:0:0:0, x69:0:0:0 + 1, x70:0:0:0, x71:0:0:0) :|: x71:0:0:0 <= x68:0:0:0 && x70:0:0:0 * x70:0:0:0 * x70:0:0:0 + x71:0:0:0 * x71:0:0:0 * x71:0:0:0 > x69:0:0:0 * x69:0:0:0 * x69:0:0:0 && x70:0:0:0 <= x68:0:0:0 && x69:0:0:0 + 1 <= x68:0:0:0 26.94/7.72 f15(x:0:0, x1:0:0, x2:0:0, x3:0:0) -> f15(x:0:0, x1:0:0 + 1, x2:0:0, x3:0:0) :|: x:0:0 >= x3:0:0 && x2:0:0 * x2:0:0 * x2:0:0 + x3:0:0 * x3:0:0 * x3:0:0 < x1:0:0 * x1:0:0 * x1:0:0 && x:0:0 >= x2:0:0 && x:0:0 >= x1:0:0 + 1 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (17) PolynomialOrderProcessor (EQUIVALENT) 26.94/7.72 Found the following polynomial interpretation: 26.94/7.72 [f15(x, x1, x2, x3)] = x - x1 26.94/7.72 26.94/7.72 The following rules are decreasing: 26.94/7.72 f15(x68:0:0:0, x69:0:0:0, x70:0:0:0, x71:0:0:0) -> f15(x68:0:0:0, x69:0:0:0 + 1, x70:0:0:0, x71:0:0:0) :|: x71:0:0:0 <= x68:0:0:0 && x70:0:0:0 * x70:0:0:0 * x70:0:0:0 + x71:0:0:0 * x71:0:0:0 * x71:0:0:0 > x69:0:0:0 * x69:0:0:0 * x69:0:0:0 && x70:0:0:0 <= x68:0:0:0 && x69:0:0:0 + 1 <= x68:0:0:0 26.94/7.72 f15(x:0:0, x1:0:0, x2:0:0, x3:0:0) -> f15(x:0:0, x1:0:0 + 1, x2:0:0, x3:0:0) :|: x:0:0 >= x3:0:0 && x2:0:0 * x2:0:0 * x2:0:0 + x3:0:0 * x3:0:0 * x3:0:0 < x1:0:0 * x1:0:0 * x1:0:0 && x:0:0 >= x2:0:0 && x:0:0 >= x1:0:0 + 1 26.94/7.72 The following rules are bounded: 26.94/7.72 f15(x68:0:0:0, x69:0:0:0, x70:0:0:0, x71:0:0:0) -> f15(x68:0:0:0, x69:0:0:0 + 1, x70:0:0:0, x71:0:0:0) :|: x71:0:0:0 <= x68:0:0:0 && x70:0:0:0 * x70:0:0:0 * x70:0:0:0 + x71:0:0:0 * x71:0:0:0 * x71:0:0:0 > x69:0:0:0 * x69:0:0:0 * x69:0:0:0 && x70:0:0:0 <= x68:0:0:0 && x69:0:0:0 + 1 <= x68:0:0:0 26.94/7.72 f15(x:0:0, x1:0:0, x2:0:0, x3:0:0) -> f15(x:0:0, x1:0:0 + 1, x2:0:0, x3:0:0) :|: x:0:0 >= x3:0:0 && x2:0:0 * x2:0:0 * x2:0:0 + x3:0:0 * x3:0:0 * x3:0:0 < x1:0:0 * x1:0:0 * x1:0:0 && x:0:0 >= x2:0:0 && x:0:0 >= x1:0:0 + 1 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (18) 26.94/7.72 YES 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (19) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f7(x24:0:0, x25:0:0, x26:0:0, x27:0:0) -> f15(x24:0:0, 1, x26:0:0 + 1, x27:0:0) :|: x25:0:0 > x24:0:0 && x26:0:0 + 1 <= x24:0:0 26.94/7.72 f15(x68:0:0, x69:0:0, x70:0:0, x71:0:0) -> f7(x68:0:0, x69:0:0 + 1, x70:0:0, x71:0:0) :|: x70:0:0 * x70:0:0 * x70:0:0 + x71:0:0 * x71:0:0 * x71:0:0 > x69:0:0 * x69:0:0 * x69:0:0 && x71:0:0 <= x68:0:0 26.94/7.72 f15(x:0, x1:0, x2:0, x3:0) -> f7(x:0, x1:0 + 1, x2:0, x3:0) :|: x2:0 * x2:0 * x2:0 + x3:0 * x3:0 * x3:0 < x1:0 * x1:0 * x1:0 && x:0 >= x3:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (20) IntTRSCompressionProof (EQUIVALENT) 26.94/7.72 Compressed rules. 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (21) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f7(x24:0:0:0, x25:0:0:0, x26:0:0:0, x27:0:0:0) -> f7(x24:0:0:0, 2, x26:0:0:0 + 1, x27:0:0:0) :|: x26:0:0:0 + 1 <= x24:0:0:0 && x25:0:0:0 > x24:0:0:0 && x27:0:0:0 <= x24:0:0:0 && (x26:0:0:0 + 1) * (x26:0:0:0 + 1) * (x26:0:0:0 + 1) + x27:0:0:0 * x27:0:0:0 * x27:0:0:0 > 1 26.94/7.72 f7(x, x1, x2, x3) -> f7(x, 2, x2 + 1, x3) :|: x2 + 1 <= x && x1 > x && x3 <= x && (x2 + 1) * (x2 + 1) * (x2 + 1) + x3 * x3 * x3 < 1 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (22) RankingReductionPairProof (EQUIVALENT) 26.94/7.72 Interpretation: 26.94/7.72 [ f7 ] = -1*f7_3 + f7_1 26.94/7.72 26.94/7.72 The following rules are decreasing: 26.94/7.72 f7(x24:0:0:0, x25:0:0:0, x26:0:0:0, x27:0:0:0) -> f7(x24:0:0:0, 2, x26:0:0:0 + 1, x27:0:0:0) :|: x26:0:0:0 + 1 <= x24:0:0:0 && x25:0:0:0 > x24:0:0:0 && x27:0:0:0 <= x24:0:0:0 && (x26:0:0:0 + 1) * (x26:0:0:0 + 1) * (x26:0:0:0 + 1) + x27:0:0:0 * x27:0:0:0 * x27:0:0:0 > 1 26.94/7.72 f7(x, x1, x2, x3) -> f7(x, 2, x2 + 1, x3) :|: x2 + 1 <= x && x1 > x && x3 <= x && (x2 + 1) * (x2 + 1) * (x2 + 1) + x3 * x3 * x3 < 1 26.94/7.72 26.94/7.72 The following rules are bounded: 26.94/7.72 f7(x24:0:0:0, x25:0:0:0, x26:0:0:0, x27:0:0:0) -> f7(x24:0:0:0, 2, x26:0:0:0 + 1, x27:0:0:0) :|: x26:0:0:0 + 1 <= x24:0:0:0 && x25:0:0:0 > x24:0:0:0 && x27:0:0:0 <= x24:0:0:0 && (x26:0:0:0 + 1) * (x26:0:0:0 + 1) * (x26:0:0:0 + 1) + x27:0:0:0 * x27:0:0:0 * x27:0:0:0 > 1 26.94/7.72 f7(x, x1, x2, x3) -> f7(x, 2, x2 + 1, x3) :|: x2 + 1 <= x && x1 > x && x3 <= x && (x2 + 1) * (x2 + 1) * (x2 + 1) + x3 * x3 * x3 < 1 26.94/7.72 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (23) 26.94/7.72 YES 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (24) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x68:0, x69:0, x70:0, x71:0) -> f7(x68:0, x69:0 + 1, x70:0, x71:0) :|: x70:0 * x70:0 * x70:0 + x71:0 * x71:0 * x71:0 > x69:0 * x69:0 * x69:0 && x71:0 <= x68:0 26.94/7.72 f7(x24:0, x25:0, x26:0, x27:0) -> f10(x24:0, 1, x26:0 + 1, x27:0) :|: x25:0 > x24:0 26.94/7.72 f10(x48:0, x49:0, x50:0, x51:0) -> f15(x48:0, x49:0, 1, x51:0 + 1) :|: x50:0 > x48:0 26.94/7.72 f10(x52:0, x53:0, x54:0, x55:0) -> f15(x52:0, x53:0, x54:0, x55:0) :|: x54:0 <= x52:0 26.94/7.72 f7(x28:0, x29:0, x30:0, x31:0) -> f10(x28:0, x29:0, x30:0, x31:0) :|: x29:0 <= x28:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (25) IntTRSCompressionProof (EQUIVALENT) 26.94/7.72 Compressed rules. 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (26) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x68:0:0, x69:0:0, x70:0:0, x71:0:0) -> f10(x68:0:0, 1, x70:0:0 + 1, x71:0:0) :|: x70:0:0 * x70:0:0 * x70:0:0 + x71:0:0 * x71:0:0 * x71:0:0 > x69:0:0 * x69:0:0 * x69:0:0 && x71:0:0 <= x68:0:0 && x69:0:0 + 1 > x68:0:0 26.94/7.72 f15(x, x1, x2, x3) -> f10(x, x1 + 1, x2, x3) :|: x2 * x2 * x2 + x3 * x3 * x3 > x1 * x1 * x1 && x3 <= x && x1 + 1 <= x 26.94/7.72 f10(x52:0:0, x53:0:0, x54:0:0, x55:0:0) -> f15(x52:0:0, x53:0:0, x54:0:0, x55:0:0) :|: x54:0:0 <= x52:0:0 26.94/7.72 f10(x48:0:0, x49:0:0, x50:0:0, x51:0:0) -> f15(x48:0:0, x49:0:0, 1, x51:0:0 + 1) :|: x50:0:0 > x48:0:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (27) RankingReductionPairProof (EQUIVALENT) 26.94/7.72 Interpretation: 26.94/7.72 [ f15 ] = -3*f15_4 + 3*f15_1 26.94/7.72 [ f10 ] = 3*f10_1 + -3*f10_4 26.94/7.72 26.94/7.72 The following rules are decreasing: 26.94/7.72 f10(x48:0:0, x49:0:0, x50:0:0, x51:0:0) -> f15(x48:0:0, x49:0:0, 1, x51:0:0 + 1) :|: x50:0:0 > x48:0:0 26.94/7.72 26.94/7.72 The following rules are bounded: 26.94/7.72 f15(x68:0:0, x69:0:0, x70:0:0, x71:0:0) -> f10(x68:0:0, 1, x70:0:0 + 1, x71:0:0) :|: x70:0:0 * x70:0:0 * x70:0:0 + x71:0:0 * x71:0:0 * x71:0:0 > x69:0:0 * x69:0:0 * x69:0:0 && x71:0:0 <= x68:0:0 && x69:0:0 + 1 > x68:0:0 26.94/7.72 f15(x, x1, x2, x3) -> f10(x, x1 + 1, x2, x3) :|: x2 * x2 * x2 + x3 * x3 * x3 > x1 * x1 * x1 && x3 <= x && x1 + 1 <= x 26.94/7.72 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (28) 26.94/7.72 Complex Obligation (AND) 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (29) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x68:0:0, x69:0:0, x70:0:0, x71:0:0) -> f10(x68:0:0, 1, x70:0:0 + 1, x71:0:0) :|: x70:0:0 * x70:0:0 * x70:0:0 + x71:0:0 * x71:0:0 * x71:0:0 > x69:0:0 * x69:0:0 * x69:0:0 && x71:0:0 <= x68:0:0 && x69:0:0 + 1 > x68:0:0 26.94/7.72 f15(x, x1, x2, x3) -> f10(x, x1 + 1, x2, x3) :|: x2 * x2 * x2 + x3 * x3 * x3 > x1 * x1 * x1 && x3 <= x && x1 + 1 <= x 26.94/7.72 f10(x52:0:0, x53:0:0, x54:0:0, x55:0:0) -> f15(x52:0:0, x53:0:0, x54:0:0, x55:0:0) :|: x54:0:0 <= x52:0:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (30) IntTRSCompressionProof (EQUIVALENT) 26.94/7.72 Compressed rules. 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (31) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x68:0:0:0, x69:0:0:0, x70:0:0:0, x71:0:0:0) -> f15(x68:0:0:0, 1, x70:0:0:0 + 1, x71:0:0:0) :|: x69:0:0:0 + 1 > x68:0:0:0 && x70:0:0:0 + 1 <= x68:0:0:0 && x71:0:0:0 <= x68:0:0:0 && x70:0:0:0 * x70:0:0:0 * x70:0:0:0 + x71:0:0:0 * x71:0:0:0 * x71:0:0:0 > x69:0:0:0 * x69:0:0:0 * x69:0:0:0 26.94/7.72 f15(x:0, x1:0, x2:0, x3:0) -> f15(x:0, x1:0 + 1, x2:0, x3:0) :|: x:0 >= x1:0 + 1 && x:0 >= x2:0 && x:0 >= x3:0 && x2:0 * x2:0 * x2:0 + x3:0 * x3:0 * x3:0 > x1:0 * x1:0 * x1:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (32) RankingReductionPairProof (EQUIVALENT) 26.94/7.72 Interpretation: 26.94/7.72 [ f15 ] = f15_1 + -1*f15_3 26.94/7.72 26.94/7.72 The following rules are decreasing: 26.94/7.72 f15(x68:0:0:0, x69:0:0:0, x70:0:0:0, x71:0:0:0) -> f15(x68:0:0:0, 1, x70:0:0:0 + 1, x71:0:0:0) :|: x69:0:0:0 + 1 > x68:0:0:0 && x70:0:0:0 + 1 <= x68:0:0:0 && x71:0:0:0 <= x68:0:0:0 && x70:0:0:0 * x70:0:0:0 * x70:0:0:0 + x71:0:0:0 * x71:0:0:0 * x71:0:0:0 > x69:0:0:0 * x69:0:0:0 * x69:0:0:0 26.94/7.72 26.94/7.72 The following rules are bounded: 26.94/7.72 f15(x68:0:0:0, x69:0:0:0, x70:0:0:0, x71:0:0:0) -> f15(x68:0:0:0, 1, x70:0:0:0 + 1, x71:0:0:0) :|: x69:0:0:0 + 1 > x68:0:0:0 && x70:0:0:0 + 1 <= x68:0:0:0 && x71:0:0:0 <= x68:0:0:0 && x70:0:0:0 * x70:0:0:0 * x70:0:0:0 + x71:0:0:0 * x71:0:0:0 * x71:0:0:0 > x69:0:0:0 * x69:0:0:0 * x69:0:0:0 26.94/7.72 f15(x:0, x1:0, x2:0, x3:0) -> f15(x:0, x1:0 + 1, x2:0, x3:0) :|: x:0 >= x1:0 + 1 && x:0 >= x2:0 && x:0 >= x3:0 && x2:0 * x2:0 * x2:0 + x3:0 * x3:0 * x3:0 > x1:0 * x1:0 * x1:0 26.94/7.72 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (33) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x:0, x1:0, x2:0, x3:0) -> f15(x:0, x1:0 + 1, x2:0, x3:0) :|: x:0 >= x1:0 + 1 && x:0 >= x2:0 && x:0 >= x3:0 && x2:0 * x2:0 * x2:0 + x3:0 * x3:0 * x3:0 > x1:0 * x1:0 * x1:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (34) IntTRSCompressionProof (EQUIVALENT) 26.94/7.72 Compressed rules. 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (35) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f15(x:0:0, x1:0:0, x2:0:0, x3:0:0) -> f15(x:0:0, x1:0:0 + 1, x2:0:0, x3:0:0) :|: x:0:0 >= x3:0:0 && x2:0:0 * x2:0:0 * x2:0:0 + x3:0:0 * x3:0:0 * x3:0:0 > x1:0:0 * x1:0:0 * x1:0:0 && x:0:0 >= x2:0:0 && x:0:0 >= x1:0:0 + 1 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (36) PolynomialOrderProcessor (EQUIVALENT) 26.94/7.72 Found the following polynomial interpretation: 26.94/7.72 [f15(x, x1, x2, x3)] = x - x1 26.94/7.72 26.94/7.72 The following rules are decreasing: 26.94/7.72 f15(x:0:0, x1:0:0, x2:0:0, x3:0:0) -> f15(x:0:0, x1:0:0 + 1, x2:0:0, x3:0:0) :|: x:0:0 >= x3:0:0 && x2:0:0 * x2:0:0 * x2:0:0 + x3:0:0 * x3:0:0 * x3:0:0 > x1:0:0 * x1:0:0 * x1:0:0 && x:0:0 >= x2:0:0 && x:0:0 >= x1:0:0 + 1 26.94/7.72 The following rules are bounded: 26.94/7.72 f15(x:0:0, x1:0:0, x2:0:0, x3:0:0) -> f15(x:0:0, x1:0:0 + 1, x2:0:0, x3:0:0) :|: x:0:0 >= x3:0:0 && x2:0:0 * x2:0:0 * x2:0:0 + x3:0:0 * x3:0:0 * x3:0:0 > x1:0:0 * x1:0:0 * x1:0:0 && x:0:0 >= x2:0:0 && x:0:0 >= x1:0:0 + 1 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (37) 26.94/7.72 YES 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (38) 26.94/7.72 Obligation: 26.94/7.72 Rules: 26.94/7.72 f10(x52:0:0, x53:0:0, x54:0:0, x55:0:0) -> f15(x52:0:0, x53:0:0, x54:0:0, x55:0:0) :|: x54:0:0 <= x52:0:0 26.94/7.72 f10(x48:0:0, x49:0:0, x50:0:0, x51:0:0) -> f15(x48:0:0, x49:0:0, 1, x51:0:0 + 1) :|: x50:0:0 > x48:0:0 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (39) TerminationGraphProcessor (EQUIVALENT) 26.94/7.72 Constructed the termination graph and obtained no non-trivial SCC(s). 26.94/7.72 26.94/7.72 ---------------------------------------- 26.94/7.72 26.94/7.72 (40) 26.94/7.72 YES 27.22/7.76 EOF