YES
proof of prog.inttrs
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination of the given IRSwT could be proven:

(0) IRSwT
(1) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(2) IRSwT
(3) IRSwTTerminationDigraphProof [EQUIVALENT, 248 ms]
(4) AND
    (5) IRSwT
        (6) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (7) IRSwT
        (8) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (9) IRSwT
        (10) TempFilterProof [SOUND, 26 ms]
        (11) IntTRS
        (12) PolynomialOrderProcessor [EQUIVALENT, 11 ms]
        (13) YES
    (14) IRSwT
        (15) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (16) IRSwT
        (17) TempFilterProof [SOUND, 114 ms]
        (18) IntTRS
        (19) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
        (20) IntTRS
        (21) PolynomialOrderProcessor [EQUIVALENT, 6 ms]
        (22) IntTRS
        (23) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
        (24) YES


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

(0)
Obligation:
Rules:
f164_0_createList_Return(arg1, arg2) -> f346_0_main_NULL(arg1P, arg2P) :|: 0 = arg1P && arg2 + 2 <= arg1 && 0 <= arg2P - 1 && 0 <= arg1 - 1 && arg2P <= arg1
f1_0_main_Load(x, x1) -> f346_0_main_NULL(x2, x3) :|: -1 <= x4 - 1 && 0 <= x1 - 1 && 0 <= x - 1 && 0 <= x3 - 1 && 0 = x2
f346_0_main_NULL(x5, x7) -> f346_0_main_NULL(x8, x9) :|: 1 = x8 && 0 = x5 && -1 <= x9 - 1 && 6 <= x7 - 1 && x9 + 7 <= x7
f346_0_main_NULL(x10, x11) -> f346_0_main_NULL(x12, x13) :|: 2 = x12 && 1 = x10 && 2 <= x13 - 1 && 0 <= x11 - 1 && x13 - 2 <= x11
f346_0_main_NULL(x14, x15) -> f346_0_main_NULL(x16, x17) :|: 0 = x16 && 2 = x14 && 4 <= x17 - 1 && 0 <= x15 - 1 && x17 - 4 <= x15
f1_0_main_Load(x18, x19) -> f188_0_createList_LE(x20, x21) :|: 0 <= x18 - 1 && 0 <= x19 - 1 && -1 <= x20 - 1
f188_0_createList_LE(x22, x23) -> f188_0_createList_LE(x24, x25) :|: x22 - 1 = x24 && 0 <= x22 - 1
__init(x26, x27) -> f1_0_main_Load(x28, x29) :|: 0 <= 0
Start term: __init(arg1, arg2)

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

(1) IRSFormatTransformerProof (EQUIVALENT)
Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %).
----------------------------------------

(2)
Obligation:
Rules:
f164_0_createList_Return(arg1, arg2) -> f346_0_main_NULL(arg1P, arg2P) :|: 0 = arg1P && arg2 + 2 <= arg1 && 0 <= arg2P - 1 && 0 <= arg1 - 1 && arg2P <= arg1
f1_0_main_Load(x, x1) -> f346_0_main_NULL(x2, x3) :|: -1 <= x4 - 1 && 0 <= x1 - 1 && 0 <= x - 1 && 0 <= x3 - 1 && 0 = x2
f346_0_main_NULL(x5, x7) -> f346_0_main_NULL(x8, x9) :|: 1 = x8 && 0 = x5 && -1 <= x9 - 1 && 6 <= x7 - 1 && x9 + 7 <= x7
f346_0_main_NULL(x10, x11) -> f346_0_main_NULL(x12, x13) :|: 2 = x12 && 1 = x10 && 2 <= x13 - 1 && 0 <= x11 - 1 && x13 - 2 <= x11
f346_0_main_NULL(x14, x15) -> f346_0_main_NULL(x16, x17) :|: 0 = x16 && 2 = x14 && 4 <= x17 - 1 && 0 <= x15 - 1 && x17 - 4 <= x15
f1_0_main_Load(x18, x19) -> f188_0_createList_LE(x20, x21) :|: 0 <= x18 - 1 && 0 <= x19 - 1 && -1 <= x20 - 1
f188_0_createList_LE(x22, x23) -> f188_0_createList_LE(x24, x25) :|: x22 - 1 = x24 && 0 <= x22 - 1
__init(x26, x27) -> f1_0_main_Load(x28, x29) :|: 0 <= 0
Start term: __init(arg1, arg2)

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

(3) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f164_0_createList_Return(arg1, arg2) -> f346_0_main_NULL(arg1P, arg2P) :|: 0 = arg1P && arg2 + 2 <= arg1 && 0 <= arg2P - 1 && 0 <= arg1 - 1 && arg2P <= arg1
(2) f1_0_main_Load(x, x1) -> f346_0_main_NULL(x2, x3) :|: -1 <= x4 - 1 && 0 <= x1 - 1 && 0 <= x - 1 && 0 <= x3 - 1 && 0 = x2
(3) f346_0_main_NULL(x5, x7) -> f346_0_main_NULL(x8, x9) :|: 1 = x8 && 0 = x5 && -1 <= x9 - 1 && 6 <= x7 - 1 && x9 + 7 <= x7
(4) f346_0_main_NULL(x10, x11) -> f346_0_main_NULL(x12, x13) :|: 2 = x12 && 1 = x10 && 2 <= x13 - 1 && 0 <= x11 - 1 && x13 - 2 <= x11
(5) f346_0_main_NULL(x14, x15) -> f346_0_main_NULL(x16, x17) :|: 0 = x16 && 2 = x14 && 4 <= x17 - 1 && 0 <= x15 - 1 && x17 - 4 <= x15
(6) f1_0_main_Load(x18, x19) -> f188_0_createList_LE(x20, x21) :|: 0 <= x18 - 1 && 0 <= x19 - 1 && -1 <= x20 - 1
(7) f188_0_createList_LE(x22, x23) -> f188_0_createList_LE(x24, x25) :|: x22 - 1 = x24 && 0 <= x22 - 1
(8) __init(x26, x27) -> f1_0_main_Load(x28, x29) :|: 0 <= 0

Arcs:
(1) -> (3)
(2) -> (3)
(3) -> (4)
(4) -> (5)
(5) -> (3)
(6) -> (7)
(7) -> (7)
(8) -> (2), (6)

This digraph is fully evaluated!
----------------------------------------

(4)
Complex Obligation (AND)

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

(5)
Obligation:

Termination digraph:
Nodes:
(1) f188_0_createList_LE(x22, x23) -> f188_0_createList_LE(x24, x25) :|: x22 - 1 = x24 && 0 <= x22 - 1

Arcs:
(1) -> (1)

This digraph is fully evaluated!

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

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

(7)
Obligation:
Rules:
f188_0_createList_LE(x22:0, x23:0) -> f188_0_createList_LE(x22:0 - 1, x25:0) :|: x22:0 > 0

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

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

   f188_0_createList_LE(x1, x2) -> f188_0_createList_LE(x1)

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

(9)
Obligation:
Rules:
f188_0_createList_LE(x22:0) -> f188_0_createList_LE(x22:0 - 1) :|: x22:0 > 0

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

(10) TempFilterProof (SOUND)
Used the following sort dictionary for filtering: 
f188_0_createList_LE(INTEGER)
Replaced non-predefined constructor symbols by 0.
----------------------------------------

(11)
Obligation:
Rules:
f188_0_createList_LE(x22:0) -> f188_0_createList_LE(c) :|: c = x22:0 - 1 && x22:0 > 0

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

(12) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f188_0_createList_LE(x)] = x

The following rules are decreasing:
f188_0_createList_LE(x22:0) -> f188_0_createList_LE(c) :|: c = x22:0 - 1 && x22:0 > 0
The following rules are bounded:
f188_0_createList_LE(x22:0) -> f188_0_createList_LE(c) :|: c = x22:0 - 1 && x22:0 > 0

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

(13)
YES

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

(14)
Obligation:

Termination digraph:
Nodes:
(1) f346_0_main_NULL(x5, x7) -> f346_0_main_NULL(x8, x9) :|: 1 = x8 && 0 = x5 && -1 <= x9 - 1 && 6 <= x7 - 1 && x9 + 7 <= x7
(2) f346_0_main_NULL(x14, x15) -> f346_0_main_NULL(x16, x17) :|: 0 = x16 && 2 = x14 && 4 <= x17 - 1 && 0 <= x15 - 1 && x17 - 4 <= x15
(3) f346_0_main_NULL(x10, x11) -> f346_0_main_NULL(x12, x13) :|: 2 = x12 && 1 = x10 && 2 <= x13 - 1 && 0 <= x11 - 1 && x13 - 2 <= x11

Arcs:
(1) -> (3)
(2) -> (1)
(3) -> (2)

This digraph is fully evaluated!

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

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

(16)
Obligation:
Rules:
f346_0_main_NULL(cons_0, x7:0) -> f346_0_main_NULL(1, x9:0) :|: x7:0 > 6 && x9:0 > -1 && x9:0 + 7 <= x7:0 && cons_0 = 0
f346_0_main_NULL(cons_2, x15:0) -> f346_0_main_NULL(0, x17:0) :|: x15:0 > 0 && x17:0 > 4 && x17:0 - 4 <= x15:0 && cons_2 = 2
f346_0_main_NULL(cons_1, x11:0) -> f346_0_main_NULL(2, x13:0) :|: x11:0 > 0 && x13:0 > 2 && x13:0 - 2 <= x11:0 && cons_1 = 1

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

(17) TempFilterProof (SOUND)
Used the following sort dictionary for filtering: 
f346_0_main_NULL(VARIABLE, INTEGER)
Replaced non-predefined constructor symbols by 0.
----------------------------------------

(18)
Obligation:
Rules:
f346_0_main_NULL(c, x7:0) -> f346_0_main_NULL(c1, x9:0) :|: c1 = 1 && c = 0 && (x7:0 > 6 && x9:0 > -1 && x9:0 + 7 <= x7:0 && cons_0 = 0)
f346_0_main_NULL(c2, x15:0) -> f346_0_main_NULL(c3, x17:0) :|: c3 = 0 && c2 = 2 && (x15:0 > 0 && x17:0 > 4 && x17:0 - 4 <= x15:0 && cons_2 = 2)
f346_0_main_NULL(c4, x11:0) -> f346_0_main_NULL(c5, x13:0) :|: c5 = 2 && c4 = 1 && (x11:0 > 0 && x13:0 > 2 && x13:0 - 2 <= x11:0 && cons_1 = 1)

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

(19) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f346_0_main_NULL(x, x1)] = 10*x - 4*x^2 + x1

The following rules are decreasing:
f346_0_main_NULL(c, x7:0) -> f346_0_main_NULL(c1, x9:0) :|: c1 = 1 && c = 0 && (x7:0 > 6 && x9:0 > -1 && x9:0 + 7 <= x7:0 && cons_0 = 0)
The following rules are bounded:
f346_0_main_NULL(c, x7:0) -> f346_0_main_NULL(c1, x9:0) :|: c1 = 1 && c = 0 && (x7:0 > 6 && x9:0 > -1 && x9:0 + 7 <= x7:0 && cons_0 = 0)
f346_0_main_NULL(c2, x15:0) -> f346_0_main_NULL(c3, x17:0) :|: c3 = 0 && c2 = 2 && (x15:0 > 0 && x17:0 > 4 && x17:0 - 4 <= x15:0 && cons_2 = 2)
f346_0_main_NULL(c4, x11:0) -> f346_0_main_NULL(c5, x13:0) :|: c5 = 2 && c4 = 1 && (x11:0 > 0 && x13:0 > 2 && x13:0 - 2 <= x11:0 && cons_1 = 1)

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

(20)
Obligation:
Rules:
f346_0_main_NULL(c2, x15:0) -> f346_0_main_NULL(c3, x17:0) :|: c3 = 0 && c2 = 2 && (x15:0 > 0 && x17:0 > 4 && x17:0 - 4 <= x15:0 && cons_2 = 2)
f346_0_main_NULL(c4, x11:0) -> f346_0_main_NULL(c5, x13:0) :|: c5 = 2 && c4 = 1 && (x11:0 > 0 && x13:0 > 2 && x13:0 - 2 <= x11:0 && cons_1 = 1)

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

(21) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f346_0_main_NULL(x, x1)] = -1 + 3*x - x^2

The following rules are decreasing:
f346_0_main_NULL(c2, x15:0) -> f346_0_main_NULL(c3, x17:0) :|: c3 = 0 && c2 = 2 && (x15:0 > 0 && x17:0 > 4 && x17:0 - 4 <= x15:0 && cons_2 = 2)
The following rules are bounded:
f346_0_main_NULL(c2, x15:0) -> f346_0_main_NULL(c3, x17:0) :|: c3 = 0 && c2 = 2 && (x15:0 > 0 && x17:0 > 4 && x17:0 - 4 <= x15:0 && cons_2 = 2)
f346_0_main_NULL(c4, x11:0) -> f346_0_main_NULL(c5, x13:0) :|: c5 = 2 && c4 = 1 && (x11:0 > 0 && x13:0 > 2 && x13:0 - 2 <= x11:0 && cons_1 = 1)

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

(22)
Obligation:
Rules:
f346_0_main_NULL(c4, x11:0) -> f346_0_main_NULL(c5, x13:0) :|: c5 = 2 && c4 = 1 && (x11:0 > 0 && x13:0 > 2 && x13:0 - 2 <= x11:0 && cons_1 = 1)

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

(23) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f346_0_main_NULL(x, x1)] = 1 - x

The following rules are decreasing:
f346_0_main_NULL(c4, x11:0) -> f346_0_main_NULL(c5, x13:0) :|: c5 = 2 && c4 = 1 && (x11:0 > 0 && x13:0 > 2 && x13:0 - 2 <= x11:0 && cons_1 = 1)
The following rules are bounded:
f346_0_main_NULL(c4, x11:0) -> f346_0_main_NULL(c5, x13:0) :|: c5 = 2 && c4 = 1 && (x11:0 > 0 && x13:0 > 2 && x13:0 - 2 <= x11:0 && cons_1 = 1)

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

(24)
YES