/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, 100 ms]
(4) IntTRS
(5) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(6) IntTRS
(7) PolynomialOrderProcessor [EQUIVALENT, 20 ms]
(8) IntTRS
(9) TerminationGraphProcessor [EQUIVALENT, 20 ms]
(10) AND
    (11) IntTRS
        (12) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (13) IntTRS
        (14) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
        (15) YES
    (16) IntTRS
        (17) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (18) IntTRS
        (19) PolynomialOrderProcessor [EQUIVALENT, 0 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(x, y, m) -> f2(x, 0, m) :|: TRUE
f2(x1, x2, x3) -> f3(x1, x2, x4) :|: TRUE
f3(x5, x6, x7) -> f4(x7, x6, x7) :|: TRUE
f9(x8, x9, x10) -> f10(x8, arith, x10) :|: TRUE && arith = x9 + 1
f6(x11, x12, x13) -> f9(x11, x12, x13) :|: x12 <= x13 && x14 < 0
f6(x51, x52, x53) -> f9(x51, x52, x53) :|: x52 <= x53 && x54 > 0
f10(x15, x16, x17) -> f6(x15, x16, x17) :|: TRUE
f6(x18, x19, x20) -> f11(x18, x19, x20) :|: x19 > x20
f6(x55, x56, x57) -> f11(x55, x56, x57) :|: x58 = 0
f11(x59, x60, x61) -> f12(x62, x60, x61) :|: TRUE && x62 = x59 - 1
f5(x25, x26, x27) -> f6(x25, x26, x27) :|: x28 < 0
f5(x63, x64, x65) -> f6(x63, x64, x65) :|: x66 > 0
f5(x29, x30, x31) -> f7(x29, x30, x31) :|: x32 = 0
f12(x33, x34, x35) -> f8(x33, x34, x35) :|: TRUE
f7(x36, x37, x38) -> f8(x36, x37, x38) :|: TRUE
f8(x67, x68, x69) -> f13(x67, x70, x69) :|: TRUE && x70 = x68 - 1
f4(x42, x43, x44) -> f5(x42, x43, x44) :|: x42 >= 0 && x43 >= 0
f13(x45, x46, x47) -> f4(x45, x46, x47) :|: TRUE
f4(x48, x49, x50) -> f14(x48, x49, x50) :|: x48 < 0
f4(x71, x72, x73) -> f14(x71, x72, x73) :|: x72 < 0
Start term: f1(x, y, m)

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

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

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

(4)
Obligation:
Rules:
f4(x42, x43, x44) -> f5(x42, x43, x44) :|: x42 >= 0 && x43 >= 0
f13(x45, x46, x47) -> f4(x45, x46, x47) :|: TRUE
f8(x67, x68, x69) -> f13(x67, x70, x69) :|: TRUE && x70 = x68 - 1
f12(x33, x34, x35) -> f8(x33, x34, x35) :|: TRUE
f11(x59, x60, x61) -> f12(x62, x60, x61) :|: TRUE && x62 = x59 - 1
f6(x18, x19, x20) -> f11(x18, x19, x20) :|: x19 > x20
f5(x25, x26, x27) -> f6(x25, x26, x27) :|: x28 < 0
f10(x15, x16, x17) -> f6(x15, x16, x17) :|: TRUE
f9(x8, x9, x10) -> f10(x8, arith, x10) :|: TRUE && arith = x9 + 1
f6(x11, x12, x13) -> f9(x11, x12, x13) :|: x12 <= x13 && x14 < 0
f5(x63, x64, x65) -> f6(x63, x64, x65) :|: x66 > 0
f6(x51, x52, x53) -> f9(x51, x52, x53) :|: x52 <= x53 && x54 > 0
f6(x55, x56, x57) -> f11(x55, x56, x57) :|: x58 = 0
f7(x36, x37, x38) -> f8(x36, x37, x38) :|: TRUE
f5(x29, x30, x31) -> f7(x29, x30, x31) :|: x32 = 0

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

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

(6)
Obligation:
Rules:
f8(x67:0, x68:0, x69:0) -> f6(x67:0, x68:0 - 1, x69:0) :|: x67:0 > -1 && x68:0 > 0 && x28:0 < 0
f8(x, x1, x2) -> f8(x, x1 - 1, x2) :|: x > -1 && x1 > 0
f6(x55:0, x56:0, x57:0) -> f8(x55:0 - 1, x56:0, x57:0) :|: TRUE
f6(x11:0, x12:0, x13:0) -> f6(x11:0, x12:0 + 1, x13:0) :|: x13:0 >= x12:0 && x14:0 < 0
f8(x3, x4, x5) -> f6(x3, x4 - 1, x5) :|: x3 > -1 && x4 > 0 && x6 > 0
f6(x51:0, x52:0, x53:0) -> f6(x51:0, x52:0 + 1, x53:0) :|: x53:0 >= x52:0 && x54:0 > 0
f6(x18:0, x19:0, x20:0) -> f8(x18:0 - 1, x19:0, x20:0) :|: x20:0 < x19:0

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

(7) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f8(x, x1, x2)] = x
[f6(x3, x4, x5)] = -1 + x3

The following rules are decreasing:
f8(x67:0, x68:0, x69:0) -> f6(x67:0, x68:0 - 1, x69:0) :|: x67:0 > -1 && x68:0 > 0 && x28:0 < 0
f8(x3, x4, x5) -> f6(x3, x4 - 1, x5) :|: x3 > -1 && x4 > 0 && x6 > 0
The following rules are bounded:
f8(x67:0, x68:0, x69:0) -> f6(x67:0, x68:0 - 1, x69:0) :|: x67:0 > -1 && x68:0 > 0 && x28:0 < 0
f8(x, x1, x2) -> f8(x, x1 - 1, x2) :|: x > -1 && x1 > 0
f8(x3, x4, x5) -> f6(x3, x4 - 1, x5) :|: x3 > -1 && x4 > 0 && x6 > 0

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

(8)
Obligation:
Rules:
f8(x, x1, x2) -> f8(x, x1 - 1, x2) :|: x > -1 && x1 > 0
f6(x55:0, x56:0, x57:0) -> f8(x55:0 - 1, x56:0, x57:0) :|: TRUE
f6(x11:0, x12:0, x13:0) -> f6(x11:0, x12:0 + 1, x13:0) :|: x13:0 >= x12:0 && x14:0 < 0
f6(x51:0, x52:0, x53:0) -> f6(x51:0, x52:0 + 1, x53:0) :|: x53:0 >= x52:0 && x54:0 > 0
f6(x18:0, x19:0, x20:0) -> f8(x18:0 - 1, x19:0, x20:0) :|: x20:0 < x19:0

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

(9) TerminationGraphProcessor (EQUIVALENT)
Constructed the termination graph and obtained 2 non-trivial SCCs.

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

(10)
Complex Obligation (AND)

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

(11)
Obligation:
Rules:
f6(x11:0, x12:0, x13:0) -> f6(x11:0, x12:0 + 1, x13:0) :|: x13:0 >= x12:0 && x14:0 < 0
f6(x51:0, x52:0, x53:0) -> f6(x51:0, x52:0 + 1, x53:0) :|: x53:0 >= x52:0 && x54:0 > 0

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

(12) IntTRSUnneededArgumentFilterProof (EQUIVALENT)
Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements:

   f6(x1, x2, x3) -> f6(x2, x3)

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

(13)
Obligation:
Rules:
f6(x12:0, x13:0) -> f6(x12:0 + 1, x13:0) :|: x13:0 >= x12:0 && x14:0 < 0
f6(x52:0, x53:0) -> f6(x52:0 + 1, x53:0) :|: x53:0 >= x52:0 && x54:0 > 0

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

(14) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f6(x, x1)] = -x + x1

The following rules are decreasing:
f6(x12:0, x13:0) -> f6(x12:0 + 1, x13:0) :|: x13:0 >= x12:0 && x14:0 < 0
f6(x52:0, x53:0) -> f6(x52:0 + 1, x53:0) :|: x53:0 >= x52:0 && x54:0 > 0
The following rules are bounded:
f6(x12:0, x13:0) -> f6(x12:0 + 1, x13:0) :|: x13:0 >= x12:0 && x14:0 < 0
f6(x52:0, x53:0) -> f6(x52:0 + 1, x53:0) :|: x53:0 >= x52:0 && x54:0 > 0

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

(15)
YES

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

(16)
Obligation:
Rules:
f8(x, x1, x2) -> f8(x, x1 - 1, x2) :|: x > -1 && x1 > 0

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

(17) IntTRSUnneededArgumentFilterProof (EQUIVALENT)
Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements:

   f8(x1, x2, x3) -> f8(x1, x2)

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

(18)
Obligation:
Rules:
f8(x, x1) -> f8(x, x1 - 1) :|: x > -1 && x1 > 0

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

(19) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f8(x, x1)] = x1

The following rules are decreasing:
f8(x, x1) -> f8(x, x1 - 1) :|: x > -1 && x1 > 0
The following rules are bounded:
f8(x, x1) -> f8(x, x1 - 1) :|: x > -1 && x1 > 0

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

(20)
YES