/export/starexec/sandbox2/solver/bin/starexec_run_c /export/starexec/sandbox2/benchmark/theBenchmark.c /export/starexec/sandbox2/output/output_files


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


YES
proof of /export/starexec/sandbox2/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, 84 ms]
(4) IntTRS
(5) IntTRSCompressionProof [EQUIVALENT, 35 ms]
(6) IntTRS
(7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
(8) IntTRS
(9) CaseAnalysis [EQUIVALENT, 40 ms]
(10) AND
    (11) IntTRS
        (12) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (13) IntTRS
        (14) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
        (15) AND
            (16) IntTRS
                (17) IntTRSCompressionProof [EQUIVALENT, 0 ms]
                (18) IntTRS
                (19) RankingReductionPairProof [EQUIVALENT, 0 ms]
                (20) YES
            (21) IntTRS
                (22) IntTRSCompressionProof [EQUIVALENT, 0 ms]
                (23) IntTRS
                (24) RankingReductionPairProof [EQUIVALENT, 6 ms]
                (25) IntTRS
                (26) IntTRSCompressionProof [EQUIVALENT, 0 ms]
                (27) IntTRS
                (28) RankingReductionPairProof [EQUIVALENT, 3 ms]
                (29) YES
    (30) IntTRS
        (31) TerminationGraphProcessor [EQUIVALENT, 12 ms]
        (32) IntTRS
        (33) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (34) IntTRS
        (35) PolynomialOrderProcessor [EQUIVALENT, 7 ms]
        (36) YES


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

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

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

(2)
Obligation:
Rules:
f1(r, da, db, temp) -> f2(x_1, da, db, temp) :|: TRUE
f3(x, x1, x2, x3) -> f6(x, arith, x2, x3) :|: TRUE && arith = 2 * x
f6(x70, x71, x72, x73) -> f7(x70, x71, x74, x73) :|: TRUE && x74 = 2 * x70
f9(x75, x76, x77, x78) -> f12(x75, x79, x77, x78) :|: TRUE && x79 = x76 - 1
f10(x12, x13, x14, x15) -> f13(x12, x13, x14, x13) :|: TRUE
f13(x80, x81, x82, x83) -> f14(x80, x84, x82, x83) :|: TRUE && x84 = x82 - 1
f14(x20, x21, x22, x23) -> f15(x20, x21, x21, x23) :|: TRUE
f8(x24, x25, x26, x27) -> f9(x24, x25, x26, x27) :|: x28 < 0
f8(x85, x86, x87, x88) -> f9(x85, x86, x87, x88) :|: x89 > 0
f8(x29, x30, x31, x32) -> f10(x29, x30, x31, x32) :|: x33 = 0
f12(x34, x35, x36, x37) -> f11(x34, x35, x36, x37) :|: TRUE
f15(x38, x39, x40, x41) -> f11(x38, x39, x40, x41) :|: TRUE
f7(x42, x43, x44, x45) -> f8(x42, x43, x44, x45) :|: x43 >= x42
f11(x46, x47, x48, x49) -> f7(x46, x47, x48, x49) :|: TRUE
f7(x50, x51, x52, x53) -> f16(x50, x51, x52, x53) :|: x51 < x50
f2(x54, x55, x56, x57) -> f3(x54, x55, x56, x57) :|: x54 >= 0
f2(x58, x59, x60, x61) -> f4(x58, x59, x60, x61) :|: x58 < 0
f16(x62, x63, x64, x65) -> f5(x62, x63, x64, x65) :|: TRUE
f4(x66, x67, x68, x69) -> f5(x66, x67, x68, x69) :|: TRUE
Start term: f1(r, da, db, temp)

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

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

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

(4)
Obligation:
Rules:
f7(x42, x43, x44, x45) -> f8(x42, x43, x44, x45) :|: x43 >= x42
f11(x46, x47, x48, x49) -> f7(x46, x47, x48, x49) :|: TRUE
f12(x34, x35, x36, x37) -> f11(x34, x35, x36, x37) :|: TRUE
f9(x75, x76, x77, x78) -> f12(x75, x79, x77, x78) :|: TRUE && x79 = x76 - 1
f8(x24, x25, x26, x27) -> f9(x24, x25, x26, x27) :|: x28 < 0
f8(x85, x86, x87, x88) -> f9(x85, x86, x87, x88) :|: x89 > 0
f15(x38, x39, x40, x41) -> f11(x38, x39, x40, x41) :|: TRUE
f14(x20, x21, x22, x23) -> f15(x20, x21, x21, x23) :|: TRUE
f13(x80, x81, x82, x83) -> f14(x80, x84, x82, x83) :|: TRUE && x84 = x82 - 1
f10(x12, x13, x14, x15) -> f13(x12, x13, x14, x13) :|: TRUE
f8(x29, x30, x31, x32) -> f10(x29, x30, x31, x32) :|: x33 = 0

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

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

(6)
Obligation:
Rules:
f11(x46:0, x47:0, x48:0, x49:0) -> f11(x46:0, x48:0 - 1, x48:0 - 1, x47:0) :|: x47:0 >= x46:0
f11(x, x1, x2, x3) -> f11(x, x1 - 1, x2, x3) :|: x1 >= x && x4 > 0
f11(x5, x6, x7, x8) -> f11(x5, x6 - 1, x7, x8) :|: x6 >= x5 && x9 < 0

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

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

   f11(x1, x2, x3, x4) -> f11(x1, x2, x3)

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

(8)
Obligation:
Rules:
f11(x46:0, x47:0, x48:0) -> f11(x46:0, x48:0 - 1, x48:0 - 1) :|: x47:0 >= x46:0
f11(x, x1, x2) -> f11(x, x1 - 1, x2) :|: x1 >= x && x4 > 0
f11(x5, x6, x7) -> f11(x5, x6 - 1, x7) :|: x6 >= x5 && x9 < 0

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

(9) CaseAnalysis (EQUIVALENT)
Found the following inductive condition: 
f11(x, x1, x2): -3*x1 + 3*x2>=0

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

(10)
Complex Obligation (AND)

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

(11)
Obligation:
Rules:
f11(x46:0, x47:0, x48:0) -> f11(x46:0, x48:0 - 1, x48:0 - 1) :|: x47:0 >= x46:0 && -3 * x47:0 + 3 * x48:0 >= 0
f11(x, x1, x2) -> f11(x, x1 - 1, x2) :|: x1 >= x && x4 > 0 && -3 * x1 + 3 * x2 >= 0
f11(x5, x6, x7) -> f11(x5, x6 - 1, x7) :|: x6 >= x5 && x9 < 0 && -3 * x6 + 3 * x7 >= 0

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

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

(13)
Obligation:
Rules:
f11(x5:0, x6:0, x7:0) -> f11(x5:0, x6:0 - 1, x7:0) :|: x6:0 >= x5:0 && x9:0 < 0 && 0 <= -3 * x6:0 + 3 * x7:0
f11(x:0, x1:0, x2:0) -> f11(x:0, x1:0 - 1, x2:0) :|: x:0 <= x1:0 && x4:0 > 0 && 0 <= -3 * x1:0 + 3 * x2:0
f11(x46:0:0, x47:0:0, x48:0:0) -> f11(x46:0:0, x48:0:0 - 1, x48:0:0 - 1) :|: x47:0:0 >= x46:0:0 && 0 <= -3 * x47:0:0 + 3 * x48:0:0

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

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

The following rules are decreasing:
f11(x46:0:0, x47:0:0, x48:0:0) -> f11(x46:0:0, x48:0:0 - 1, x48:0:0 - 1) :|: x47:0:0 >= x46:0:0 && 0 <= -3 * x47:0:0 + 3 * x48:0:0
The following rules are bounded:
f11(x:0, x1:0, x2:0) -> f11(x:0, x1:0 - 1, x2:0) :|: x:0 <= x1:0 && x4:0 > 0 && 0 <= -3 * x1:0 + 3 * x2:0

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

(15)
Complex Obligation (AND)

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

(16)
Obligation:
Rules:
f11(x5:0, x6:0, x7:0) -> f11(x5:0, x6:0 - 1, x7:0) :|: x6:0 >= x5:0 && x9:0 < 0 && 0 <= -3 * x6:0 + 3 * x7:0
f11(x:0, x1:0, x2:0) -> f11(x:0, x1:0 - 1, x2:0) :|: x:0 <= x1:0 && x4:0 > 0 && 0 <= -3 * x1:0 + 3 * x2:0

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

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

(18)
Obligation:
Rules:
f11(x5:0:0, x6:0:0, x7:0:0) -> f11(x5:0:0, x6:0:0 - 1, x7:0:0) :|: x6:0:0 >= x5:0:0 && x9:0:0 < 0 && 0 <= -3 * x6:0:0 + 3 * x7:0:0
f11(x:0:0, x1:0:0, x2:0:0) -> f11(x:0:0, x1:0:0 - 1, x2:0:0) :|: x:0:0 <= x1:0:0 && x4:0:0 > 0 && 0 <= -3 * x1:0:0 + 3 * x2:0:0

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

(19) RankingReductionPairProof (EQUIVALENT)
Interpretation:
[ f11 ] = f11_2 + -1*f11_1

The following rules are decreasing:
f11(x5:0:0, x6:0:0, x7:0:0) -> f11(x5:0:0, x6:0:0 - 1, x7:0:0) :|: x6:0:0 >= x5:0:0 && x9:0:0 < 0 && 0 <= -3 * x6:0:0 + 3 * x7:0:0
f11(x:0:0, x1:0:0, x2:0:0) -> f11(x:0:0, x1:0:0 - 1, x2:0:0) :|: x:0:0 <= x1:0:0 && x4:0:0 > 0 && 0 <= -3 * x1:0:0 + 3 * x2:0:0

The following rules are bounded:
f11(x5:0:0, x6:0:0, x7:0:0) -> f11(x5:0:0, x6:0:0 - 1, x7:0:0) :|: x6:0:0 >= x5:0:0 && x9:0:0 < 0 && 0 <= -3 * x6:0:0 + 3 * x7:0:0
f11(x:0:0, x1:0:0, x2:0:0) -> f11(x:0:0, x1:0:0 - 1, x2:0:0) :|: x:0:0 <= x1:0:0 && x4:0:0 > 0 && 0 <= -3 * x1:0:0 + 3 * x2:0:0


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

(20)
YES

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

(21)
Obligation:
Rules:
f11(x5:0, x6:0, x7:0) -> f11(x5:0, x6:0 - 1, x7:0) :|: x6:0 >= x5:0 && x9:0 < 0 && 0 <= -3 * x6:0 + 3 * x7:0
f11(x46:0:0, x47:0:0, x48:0:0) -> f11(x46:0:0, x48:0:0 - 1, x48:0:0 - 1) :|: x47:0:0 >= x46:0:0 && 0 <= -3 * x47:0:0 + 3 * x48:0:0

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

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

(23)
Obligation:
Rules:
f11(x5:0:0, x6:0:0, x7:0:0) -> f11(x5:0:0, x6:0:0 - 1, x7:0:0) :|: x6:0:0 >= x5:0:0 && x9:0:0 < 0 && 0 <= -3 * x6:0:0 + 3 * x7:0:0
f11(x46:0:0:0, x47:0:0:0, x48:0:0:0) -> f11(x46:0:0:0, x48:0:0:0 - 1, x48:0:0:0 - 1) :|: x47:0:0:0 >= x46:0:0:0 && 0 <= -3 * x47:0:0:0 + 3 * x48:0:0:0

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

(24) RankingReductionPairProof (EQUIVALENT)
Interpretation:
[ f11 ] = -1*f11_1 + f11_3

The following rules are decreasing:
f11(x46:0:0:0, x47:0:0:0, x48:0:0:0) -> f11(x46:0:0:0, x48:0:0:0 - 1, x48:0:0:0 - 1) :|: x47:0:0:0 >= x46:0:0:0 && 0 <= -3 * x47:0:0:0 + 3 * x48:0:0:0

The following rules are bounded:
f11(x5:0:0, x6:0:0, x7:0:0) -> f11(x5:0:0, x6:0:0 - 1, x7:0:0) :|: x6:0:0 >= x5:0:0 && x9:0:0 < 0 && 0 <= -3 * x6:0:0 + 3 * x7:0:0
f11(x46:0:0:0, x47:0:0:0, x48:0:0:0) -> f11(x46:0:0:0, x48:0:0:0 - 1, x48:0:0:0 - 1) :|: x47:0:0:0 >= x46:0:0:0 && 0 <= -3 * x47:0:0:0 + 3 * x48:0:0:0


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

(25)
Obligation:
Rules:
f11(x5:0:0, x6:0:0, x7:0:0) -> f11(x5:0:0, x6:0:0 - 1, x7:0:0) :|: x6:0:0 >= x5:0:0 && x9:0:0 < 0 && 0 <= -3 * x6:0:0 + 3 * x7:0:0

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

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

(27)
Obligation:
Rules:
f11(x5:0:0:0, x6:0:0:0, x7:0:0:0) -> f11(x5:0:0:0, x6:0:0:0 - 1, x7:0:0:0) :|: x6:0:0:0 >= x5:0:0:0 && x9:0:0:0 < 0 && 0 <= -3 * x6:0:0:0 + 3 * x7:0:0:0

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

(28) RankingReductionPairProof (EQUIVALENT)
Interpretation:
[ f11 ] = f11_2 + -1*f11_1

The following rules are decreasing:
f11(x5:0:0:0, x6:0:0:0, x7:0:0:0) -> f11(x5:0:0:0, x6:0:0:0 - 1, x7:0:0:0) :|: x6:0:0:0 >= x5:0:0:0 && x9:0:0:0 < 0 && 0 <= -3 * x6:0:0:0 + 3 * x7:0:0:0

The following rules are bounded:
f11(x5:0:0:0, x6:0:0:0, x7:0:0:0) -> f11(x5:0:0:0, x6:0:0:0 - 1, x7:0:0:0) :|: x6:0:0:0 >= x5:0:0:0 && x9:0:0:0 < 0 && 0 <= -3 * x6:0:0:0 + 3 * x7:0:0:0


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

(29)
YES

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

(30)
Obligation:
Rules:
f11(x46:0, x47:0, x48:0) -> f11(x46:0, x48:0 - 1, x48:0 - 1) :|: x47:0 >= x46:0 && -3 * x47:0 + 3 * x48:0 < 0
f11(x, x1, x2) -> f11(x, x1 - 1, x2) :|: x1 >= x && x4 > 0 && -3 * x1 + 3 * x2 < 0
f11(x5, x6, x7) -> f11(x5, x6 - 1, x7) :|: x6 >= x5 && x9 < 0 && -3 * x6 + 3 * x7 < 0

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

(31) TerminationGraphProcessor (EQUIVALENT)
Constructed the termination graph and obtained one non-trivial SCC.

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

(32)
Obligation:
Rules:
f11(x, x1, x2) -> f11(x, x1 - 1, x2) :|: x1 >= x && x4 > 0 && -3 * x1 + 3 * x2 < 0
f11(x5, x6, x7) -> f11(x5, x6 - 1, x7) :|: x6 >= x5 && x9 < 0 && -3 * x6 + 3 * x7 < 0

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

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

(34)
Obligation:
Rules:
f11(x:0, x1:0, x2:0) -> f11(x:0, x1:0 - 1, x2:0) :|: x:0 <= x1:0 && x4:0 > 0 && 0 > -3 * x1:0 + 3 * x2:0
f11(x5:0, x6:0, x7:0) -> f11(x5:0, x6:0 - 1, x7:0) :|: x6:0 >= x5:0 && x9:0 < 0 && 0 > -3 * x6:0 + 3 * x7:0

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

(35) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f11(x, x1, x2)] = x1 - x2

The following rules are decreasing:
f11(x:0, x1:0, x2:0) -> f11(x:0, x1:0 - 1, x2:0) :|: x:0 <= x1:0 && x4:0 > 0 && 0 > -3 * x1:0 + 3 * x2:0
f11(x5:0, x6:0, x7:0) -> f11(x5:0, x6:0 - 1, x7:0) :|: x6:0 >= x5:0 && x9:0 < 0 && 0 > -3 * x6:0 + 3 * x7:0
The following rules are bounded:
f11(x:0, x1:0, x2:0) -> f11(x:0, x1:0 - 1, x2:0) :|: x:0 <= x1:0 && x4:0 > 0 && 0 > -3 * x1:0 + 3 * x2:0
f11(x5:0, x6:0, x7:0) -> f11(x5:0, x6:0 - 1, x7:0) :|: x6:0 >= x5:0 && x9:0 < 0 && 0 > -3 * x6:0 + 3 * x7:0

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

(36)
YES