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, 96 ms]
(4) IntTRS
(5) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(6) IntTRS
(7) PolynomialOrderProcessor [EQUIVALENT, 7 ms]
(8) AND
    (9) IntTRS
        (10) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (11) IntTRS
        (12) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
        (13) IntTRS
        (14) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (15) IntTRS
        (16) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
        (17) YES
    (18) IntTRS
        (19) TerminationGraphProcessor [EQUIVALENT, 7 ms]
        (20) YES


----------------------------------------

(0)
Obligation:
c file /export/starexec/sandbox/benchmark/theBenchmark.c
----------------------------------------

(1) CToIRSProof (EQUIVALENT)
Parsed C Integer Program as IRS.
----------------------------------------

(2)
Obligation:
Rules:
f1(MAX, a, b, c) -> f2(1000, a, b, c) :|: TRUE
f2(x, x1, x2, x3) -> f3(x, 1, x2, x3) :|: TRUE
f3(x4, x5, x6, x7) -> f4(x4, x5, 1, x7) :|: TRUE
f4(x8, x9, x10, x11) -> f5(x8, x9, x10, 1) :|: TRUE
f6(x12, x13, x14, x15) -> f7(x12, arith, x14, x15) :|: TRUE && arith = x13 + 1
f8(x16, x17, x18, x19) -> f11(x16, 1, x18, x19) :|: TRUE
f11(x76, x77, x78, x79) -> f12(x76, x77, x80, x79) :|: TRUE && x80 = x78 + 1
f7(x24, x25, x26, x27) -> f8(x24, x25, x26, x27) :|: x25 > x24
f7(x28, x29, x30, x31) -> f9(x28, x29, x30, x31) :|: x29 <= x28
f12(x32, x33, x34, x35) -> f10(x32, x33, x34, x35) :|: TRUE
f9(x36, x37, x38, x39) -> f10(x36, x37, x38, x39) :|: TRUE
f13(x40, x41, x42, x43) -> f16(x40, x41, 1, x43) :|: TRUE
f16(x81, x82, x83, x84) -> f17(x81, x82, x83, x85) :|: TRUE && x85 = x84 + 1
f10(x48, x49, x50, x51) -> f13(x48, x49, x50, x51) :|: x50 > x48
f10(x52, x53, x54, x55) -> f14(x52, x53, x54, x55) :|: x54 <= x52
f17(x56, x57, x58, x59) -> f15(x56, x57, x58, x59) :|: TRUE
f14(x60, x61, x62, x63) -> f15(x60, x61, x62, x63) :|: TRUE
f5(x64, x65, x66, x67) -> f6(x64, x65, x66, x67) :|: x65 * x65 * x65 < x66 * x66 * x66 + x67 * x67 * x67 && x67 <= x64
f5(x86, x87, x88, x89) -> f6(x86, x87, x88, x89) :|: x87 * x87 * x87 > x88 * x88 * x88 + x89 * x89 * x89 && x89 <= x86
f15(x68, x69, x70, x71) -> f5(x68, x69, x70, x71) :|: TRUE
f5(x72, x73, x74, x75) -> f18(x72, x73, x74, x75) :|: x73 * x73 * x73 = x74 * x74 * x74 + x75 * x75 * x75
f5(x90, x91, x92, x93) -> f18(x90, x91, x92, x93) :|: x93 > x90
Start term: f1(MAX, a, b, c)

----------------------------------------

(3) TerminationGraphProcessor (SOUND)
Constructed the termination graph and obtained one non-trivial SCC.

----------------------------------------

(4)
Obligation:
Rules:
f5(x64, x65, x66, x67) -> f6(x64, x65, x66, x67) :|: x65 * x65 * x65 < x66 * x66 * x66 + x67 * x67 * x67 && x67 <= x64
f15(x68, x69, x70, x71) -> f5(x68, x69, x70, x71) :|: TRUE
f17(x56, x57, x58, x59) -> f15(x56, x57, x58, x59) :|: TRUE
f16(x81, x82, x83, x84) -> f17(x81, x82, x83, x85) :|: TRUE && x85 = x84 + 1
f13(x40, x41, x42, x43) -> f16(x40, x41, 1, x43) :|: TRUE
f10(x48, x49, x50, x51) -> f13(x48, x49, x50, x51) :|: x50 > x48
f12(x32, x33, x34, x35) -> f10(x32, x33, x34, x35) :|: TRUE
f11(x76, x77, x78, x79) -> f12(x76, x77, x80, x79) :|: TRUE && x80 = x78 + 1
f8(x16, x17, x18, x19) -> f11(x16, 1, x18, x19) :|: TRUE
f7(x24, x25, x26, x27) -> f8(x24, x25, x26, x27) :|: x25 > x24
f6(x12, x13, x14, x15) -> f7(x12, arith, x14, x15) :|: TRUE && arith = x13 + 1
f5(x86, x87, x88, x89) -> f6(x86, x87, x88, x89) :|: x87 * x87 * x87 > x88 * x88 * x88 + x89 * x89 * x89 && x89 <= x86
f9(x36, x37, x38, x39) -> f10(x36, x37, x38, x39) :|: TRUE
f7(x28, x29, x30, x31) -> f9(x28, x29, x30, x31) :|: x29 <= x28
f14(x60, x61, x62, x63) -> f15(x60, x61, x62, x63) :|: TRUE
f10(x52, x53, x54, x55) -> f14(x52, x53, x54, x55) :|: x54 <= x52

----------------------------------------

(5) IntTRSCompressionProof (EQUIVALENT)
Compressed rules.
----------------------------------------

(6)
Obligation:
Rules:
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
f7(x24:0, x25:0, x26:0, x27:0) -> f10(x24:0, 1, x26:0 + 1, x27:0) :|: x25:0 > x24:0
f10(x48:0, x49:0, x50:0, x51:0) -> f15(x48:0, x49:0, 1, x51:0 + 1) :|: x50:0 > x48:0
f15(x, x1, x2, x3) -> f7(x, x1 + 1, x2, x3) :|: x2 * x2 * x2 + x3 * x3 * x3 < x1 * x1 * x1 && x3 <= x
f10(x52:0, x53:0, x54:0, x55:0) -> f15(x52:0, x53:0, x54:0, x55:0) :|: x54:0 <= x52:0
f7(x28:0, x29:0, x30:0, x31:0) -> f10(x28:0, x29:0, x30:0, x31:0) :|: x29:0 <= x28:0

----------------------------------------

(7) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f15(x, x1, x2, x3)] = x - x3
[f7(x4, x5, x6, x7)] = x4 - x7
[f10(x8, x9, x10, x11)] = -x11 + x8

The following rules are decreasing:
f10(x48:0, x49:0, x50:0, x51:0) -> f15(x48:0, x49:0, 1, x51:0 + 1) :|: x50:0 > x48:0
The following rules are bounded:
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
f15(x, x1, x2, x3) -> f7(x, x1 + 1, x2, x3) :|: x2 * x2 * x2 + x3 * x3 * x3 < x1 * x1 * x1 && x3 <= x

----------------------------------------

(8)
Complex Obligation (AND)

----------------------------------------

(9)
Obligation:
Rules:
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
f7(x24:0, x25:0, x26:0, x27:0) -> f10(x24:0, 1, x26:0 + 1, x27:0) :|: x25:0 > x24:0
f15(x, x1, x2, x3) -> f7(x, x1 + 1, x2, x3) :|: x2 * x2 * x2 + x3 * x3 * x3 < x1 * x1 * x1 && x3 <= x
f10(x52:0, x53:0, x54:0, x55:0) -> f15(x52:0, x53:0, x54:0, x55:0) :|: x54:0 <= x52:0
f7(x28:0, x29:0, x30:0, x31:0) -> f10(x28:0, x29:0, x30:0, x31:0) :|: x29:0 <= x28:0

----------------------------------------

(10) IntTRSCompressionProof (EQUIVALENT)
Compressed rules.
----------------------------------------

(11)
Obligation:
Rules:
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
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
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
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

----------------------------------------

(12) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f7(x, x1, x2, x3)] = x - x2
[f15(x4, x5, x6, x7)] = x4 - x6

The following rules are decreasing:
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
The following rules are bounded:
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
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

----------------------------------------

(13)
Obligation:
Rules:
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
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
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

----------------------------------------

(14) IntTRSCompressionProof (EQUIVALENT)
Compressed rules.
----------------------------------------

(15)
Obligation:
Rules:
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
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

----------------------------------------

(16) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f15(x, x1, x2, x3)] = x - x1

The following rules are decreasing:
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
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
The following rules are bounded:
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
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

----------------------------------------

(17)
YES

----------------------------------------

(18)
Obligation:
Rules:
f7(x24:0, x25:0, x26:0, x27:0) -> f10(x24:0, 1, x26:0 + 1, x27:0) :|: x25:0 > x24:0
f10(x48:0, x49:0, x50:0, x51:0) -> f15(x48:0, x49:0, 1, x51:0 + 1) :|: x50:0 > x48:0
f10(x52:0, x53:0, x54:0, x55:0) -> f15(x52:0, x53:0, x54:0, x55:0) :|: x54:0 <= x52:0
f7(x28:0, x29:0, x30:0, x31:0) -> f10(x28:0, x29:0, x30:0, x31:0) :|: x29:0 <= x28:0

----------------------------------------

(19) TerminationGraphProcessor (EQUIVALENT)
Constructed the termination graph and obtained no non-trivial SCC(s).

----------------------------------------

(20)
YES