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, 246 ms]
(4) IRSwT
(5) IntTRSCompressionProof [EQUIVALENT, 31 ms]
(6) IRSwT
(7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
(8) IRSwT
(9) FilterProof [EQUIVALENT, 0 ms]
(10) IntTRS
(11) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(12) IntTRS
(13) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
(14) IntTRS
(15) TerminationGraphProcessor [EQUIVALENT, 0 ms]
(16) YES


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

(0)
Obligation:
Rules:
f1_0_main_Load(arg1, arg2) -> f274_0_power_LE(arg1P, arg2P) :|: -1 <= arg2 - 1 && 1 <= arg1P - 1 && x3 <= 1 && -1 <= x3 - 1 && 0 <= arg1 - 1
f1_0_main_Load(x, x1) -> f274_0_power_LE(x2, x4) :|: -1 <= x1 - 1 && 1 <= x2 - 1 && 2 <= x5 - 1 && 0 <= x - 1
f274_0_power_LE(x6, x8) -> f274_0_power_LE'(x9, x10) :|: x6 - 2 * x13 = 0 && x14 <= x6 - 1 && 0 <= x6 - 1 && x6 = x9
f274_0_power_LE'(x16, x19) -> f274_0_power_LE(x20, x22) :|: x16 - 2 * x23 = 0 && 0 <= x16 - 1 && x20 <= x16 - 1 && 0 <= x16 - 2 * x23 && x16 - 2 * x23 <= 1 && x16 - 2 * x20 <= 1 && 0 <= x16 - 2 * x20
f274_0_power_LE(x24, x25) -> f274_0_power_LE'(x26, x27) :|: x24 - 2 * x28 = 1 && x29 <= x24 - 1 && 0 <= x24 - 1 && x24 = x26
f274_0_power_LE'(x30, x31) -> f274_0_power_LE(x32, x33) :|: x30 - 2 * x34 = 1 && 0 <= x30 - 1 && x32 <= x30 - 1 && 0 <= x30 - 2 * x34 && x30 - 2 * x34 <= 1 && x30 - 2 * x32 <= 1 && 0 <= x30 - 2 * x32
__init(x35, x36) -> f1_0_main_Load(x37, x38) :|: 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:
f1_0_main_Load(arg1, arg2) -> f274_0_power_LE(arg1P, arg2P) :|: -1 <= arg2 - 1 && 1 <= arg1P - 1 && x3 <= 1 && -1 <= x3 - 1 && 0 <= arg1 - 1
f1_0_main_Load(x, x1) -> f274_0_power_LE(x2, x4) :|: -1 <= x1 - 1 && 1 <= x2 - 1 && 2 <= x5 - 1 && 0 <= x - 1
f274_0_power_LE(x6, x8) -> f274_0_power_LE'(x9, x10) :|: x6 - 2 * x13 = 0 && x14 <= x6 - 1 && 0 <= x6 - 1 && x6 = x9
f274_0_power_LE'(x16, x19) -> f274_0_power_LE(x20, x22) :|: x16 - 2 * x23 = 0 && 0 <= x16 - 1 && x20 <= x16 - 1 && 0 <= x16 - 2 * x23 && x16 - 2 * x23 <= 1 && x16 - 2 * x20 <= 1 && 0 <= x16 - 2 * x20
f274_0_power_LE(x24, x25) -> f274_0_power_LE'(x26, x27) :|: x24 - 2 * x28 = 1 && x29 <= x24 - 1 && 0 <= x24 - 1 && x24 = x26
f274_0_power_LE'(x30, x31) -> f274_0_power_LE(x32, x33) :|: x30 - 2 * x34 = 1 && 0 <= x30 - 1 && x32 <= x30 - 1 && 0 <= x30 - 2 * x34 && x30 - 2 * x34 <= 1 && x30 - 2 * x32 <= 1 && 0 <= x30 - 2 * x32
__init(x35, x36) -> f1_0_main_Load(x37, x38) :|: 0 <= 0
Start term: __init(arg1, arg2)

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

(3) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f1_0_main_Load(arg1, arg2) -> f274_0_power_LE(arg1P, arg2P) :|: -1 <= arg2 - 1 && 1 <= arg1P - 1 && x3 <= 1 && -1 <= x3 - 1 && 0 <= arg1 - 1
(2) f1_0_main_Load(x, x1) -> f274_0_power_LE(x2, x4) :|: -1 <= x1 - 1 && 1 <= x2 - 1 && 2 <= x5 - 1 && 0 <= x - 1
(3) f274_0_power_LE(x6, x8) -> f274_0_power_LE'(x9, x10) :|: x6 - 2 * x13 = 0 && x14 <= x6 - 1 && 0 <= x6 - 1 && x6 = x9
(4) f274_0_power_LE'(x16, x19) -> f274_0_power_LE(x20, x22) :|: x16 - 2 * x23 = 0 && 0 <= x16 - 1 && x20 <= x16 - 1 && 0 <= x16 - 2 * x23 && x16 - 2 * x23 <= 1 && x16 - 2 * x20 <= 1 && 0 <= x16 - 2 * x20
(5) f274_0_power_LE(x24, x25) -> f274_0_power_LE'(x26, x27) :|: x24 - 2 * x28 = 1 && x29 <= x24 - 1 && 0 <= x24 - 1 && x24 = x26
(6) f274_0_power_LE'(x30, x31) -> f274_0_power_LE(x32, x33) :|: x30 - 2 * x34 = 1 && 0 <= x30 - 1 && x32 <= x30 - 1 && 0 <= x30 - 2 * x34 && x30 - 2 * x34 <= 1 && x30 - 2 * x32 <= 1 && 0 <= x30 - 2 * x32
(7) __init(x35, x36) -> f1_0_main_Load(x37, x38) :|: 0 <= 0

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

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

(4)
Obligation:

Termination digraph:
Nodes:
(1) f274_0_power_LE(x6, x8) -> f274_0_power_LE'(x9, x10) :|: x6 - 2 * x13 = 0 && x14 <= x6 - 1 && 0 <= x6 - 1 && x6 = x9
(2) f274_0_power_LE'(x30, x31) -> f274_0_power_LE(x32, x33) :|: x30 - 2 * x34 = 1 && 0 <= x30 - 1 && x32 <= x30 - 1 && 0 <= x30 - 2 * x34 && x30 - 2 * x34 <= 1 && x30 - 2 * x32 <= 1 && 0 <= x30 - 2 * x32
(3) f274_0_power_LE(x24, x25) -> f274_0_power_LE'(x26, x27) :|: x24 - 2 * x28 = 1 && x29 <= x24 - 1 && 0 <= x24 - 1 && x24 = x26
(4) f274_0_power_LE'(x16, x19) -> f274_0_power_LE(x20, x22) :|: x16 - 2 * x23 = 0 && 0 <= x16 - 1 && x20 <= x16 - 1 && 0 <= x16 - 2 * x23 && x16 - 2 * x23 <= 1 && x16 - 2 * x20 <= 1 && 0 <= x16 - 2 * x20

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

This digraph is fully evaluated!

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

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

(6)
Obligation:
Rules:
f274_0_power_LE'(x30:0, x31:0) -> f274_0_power_LE(x32:0, x33:0) :|: x30:0 - 2 * x32:0 <= 1 && x30:0 - 2 * x32:0 >= 0 && x30:0 - 2 * x34:0 <= 1 && x30:0 - 2 * x34:0 >= 0 && x32:0 <= x30:0 - 1 && x30:0 > 0 && x30:0 - 2 * x34:0 = 1
f274_0_power_LE'(x16:0, x19:0) -> f274_0_power_LE(x20:0, x22:0) :|: x16:0 - 2 * x20:0 <= 1 && x16:0 - 2 * x20:0 >= 0 && x16:0 - 2 * x23:0 <= 1 && x16:0 - 2 * x23:0 >= 0 && x20:0 <= x16:0 - 1 && x16:0 > 0 && x16:0 - 2 * x23:0 = 0
f274_0_power_LE(x6:0, x8:0) -> f274_0_power_LE'(x6:0, x10:0) :|: x6:0 - 2 * x13:0 = 0 && x6:0 - 1 >= x14:0 && x6:0 > 0
f274_0_power_LE(x24:0, x25:0) -> f274_0_power_LE'(x24:0, x27:0) :|: x24:0 - 2 * x28:0 = 1 && x29:0 <= x24:0 - 1 && x24:0 > 0

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

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

   f274_0_power_LE'(x1, x2) -> f274_0_power_LE'(x1)
   f274_0_power_LE(x1, x2) -> f274_0_power_LE(x1)

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

(8)
Obligation:
Rules:
f274_0_power_LE'(x30:0) -> f274_0_power_LE(x32:0) :|: x30:0 - 2 * x32:0 <= 1 && x30:0 - 2 * x32:0 >= 0 && x30:0 - 2 * x34:0 <= 1 && x30:0 - 2 * x34:0 >= 0 && x32:0 <= x30:0 - 1 && x30:0 > 0 && x30:0 - 2 * x34:0 = 1
f274_0_power_LE'(x16:0) -> f274_0_power_LE(x20:0) :|: x16:0 - 2 * x20:0 <= 1 && x16:0 - 2 * x20:0 >= 0 && x16:0 - 2 * x23:0 <= 1 && x16:0 - 2 * x23:0 >= 0 && x20:0 <= x16:0 - 1 && x16:0 > 0 && x16:0 - 2 * x23:0 = 0
f274_0_power_LE(x6:0) -> f274_0_power_LE'(x6:0) :|: x6:0 - 2 * x13:0 = 0 && x6:0 - 1 >= x14:0 && x6:0 > 0
f274_0_power_LE(x24:0) -> f274_0_power_LE'(x24:0) :|: x24:0 - 2 * x28:0 = 1 && x29:0 <= x24:0 - 1 && x24:0 > 0

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

(9) FilterProof (EQUIVALENT)
Used the following sort dictionary for filtering: 
f274_0_power_LE'(INTEGER)
f274_0_power_LE(INTEGER)
Replaced non-predefined constructor symbols by 0.
----------------------------------------

(10)
Obligation:
Rules:
f274_0_power_LE'(x30:0) -> f274_0_power_LE(x32:0) :|: x30:0 - 2 * x32:0 <= 1 && x30:0 - 2 * x32:0 >= 0 && x30:0 - 2 * x34:0 <= 1 && x30:0 - 2 * x34:0 >= 0 && x32:0 <= x30:0 - 1 && x30:0 > 0 && x30:0 - 2 * x34:0 = 1
f274_0_power_LE'(x16:0) -> f274_0_power_LE(x20:0) :|: x16:0 - 2 * x20:0 <= 1 && x16:0 - 2 * x20:0 >= 0 && x16:0 - 2 * x23:0 <= 1 && x16:0 - 2 * x23:0 >= 0 && x20:0 <= x16:0 - 1 && x16:0 > 0 && x16:0 - 2 * x23:0 = 0
f274_0_power_LE(x6:0) -> f274_0_power_LE'(x6:0) :|: x6:0 - 2 * x13:0 = 0 && x6:0 - 1 >= x14:0 && x6:0 > 0
f274_0_power_LE(x24:0) -> f274_0_power_LE'(x24:0) :|: x24:0 - 2 * x28:0 = 1 && x29:0 <= x24:0 - 1 && x24:0 > 0

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

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

(12)
Obligation:
Rules:
f274_0_power_LE(x24:0:0) -> f274_0_power_LE'(x24:0:0) :|: x24:0:0 - 2 * x28:0:0 = 1 && x29:0:0 <= x24:0:0 - 1 && x24:0:0 > 0
f274_0_power_LE(x6:0:0) -> f274_0_power_LE'(x6:0:0) :|: x6:0:0 - 2 * x13:0:0 = 0 && x6:0:0 - 1 >= x14:0:0 && x6:0:0 > 0
f274_0_power_LE'(x30:0:0) -> f274_0_power_LE(x32:0:0) :|: x30:0:0 > 0 && x30:0:0 - 2 * x34:0:0 = 1 && x32:0:0 <= x30:0:0 - 1 && x30:0:0 - 2 * x34:0:0 >= 0 && x30:0:0 - 2 * x34:0:0 <= 1 && x30:0:0 - 2 * x32:0:0 >= 0 && x30:0:0 - 2 * x32:0:0 <= 1
f274_0_power_LE'(x16:0:0) -> f274_0_power_LE(x20:0:0) :|: x16:0:0 > 0 && x16:0:0 - 2 * x23:0:0 = 0 && x20:0:0 <= x16:0:0 - 1 && x16:0:0 - 2 * x23:0:0 >= 0 && x16:0:0 - 2 * x23:0:0 <= 1 && x16:0:0 - 2 * x20:0:0 >= 0 && x16:0:0 - 2 * x20:0:0 <= 1

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

(13) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f274_0_power_LE(x)] = 1 + x
[f274_0_power_LE'(x1)] = x1

The following rules are decreasing:
f274_0_power_LE(x24:0:0) -> f274_0_power_LE'(x24:0:0) :|: x24:0:0 - 2 * x28:0:0 = 1 && x29:0:0 <= x24:0:0 - 1 && x24:0:0 > 0
f274_0_power_LE(x6:0:0) -> f274_0_power_LE'(x6:0:0) :|: x6:0:0 - 2 * x13:0:0 = 0 && x6:0:0 - 1 >= x14:0:0 && x6:0:0 > 0
The following rules are bounded:
f274_0_power_LE(x24:0:0) -> f274_0_power_LE'(x24:0:0) :|: x24:0:0 - 2 * x28:0:0 = 1 && x29:0:0 <= x24:0:0 - 1 && x24:0:0 > 0
f274_0_power_LE(x6:0:0) -> f274_0_power_LE'(x6:0:0) :|: x6:0:0 - 2 * x13:0:0 = 0 && x6:0:0 - 1 >= x14:0:0 && x6:0:0 > 0
f274_0_power_LE'(x30:0:0) -> f274_0_power_LE(x32:0:0) :|: x30:0:0 > 0 && x30:0:0 - 2 * x34:0:0 = 1 && x32:0:0 <= x30:0:0 - 1 && x30:0:0 - 2 * x34:0:0 >= 0 && x30:0:0 - 2 * x34:0:0 <= 1 && x30:0:0 - 2 * x32:0:0 >= 0 && x30:0:0 - 2 * x32:0:0 <= 1
f274_0_power_LE'(x16:0:0) -> f274_0_power_LE(x20:0:0) :|: x16:0:0 > 0 && x16:0:0 - 2 * x23:0:0 = 0 && x20:0:0 <= x16:0:0 - 1 && x16:0:0 - 2 * x23:0:0 >= 0 && x16:0:0 - 2 * x23:0:0 <= 1 && x16:0:0 - 2 * x20:0:0 >= 0 && x16:0:0 - 2 * x20:0:0 <= 1

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

(14)
Obligation:
Rules:
f274_0_power_LE'(x30:0:0) -> f274_0_power_LE(x32:0:0) :|: x30:0:0 > 0 && x30:0:0 - 2 * x34:0:0 = 1 && x32:0:0 <= x30:0:0 - 1 && x30:0:0 - 2 * x34:0:0 >= 0 && x30:0:0 - 2 * x34:0:0 <= 1 && x30:0:0 - 2 * x32:0:0 >= 0 && x30:0:0 - 2 * x32:0:0 <= 1
f274_0_power_LE'(x16:0:0) -> f274_0_power_LE(x20:0:0) :|: x16:0:0 > 0 && x16:0:0 - 2 * x23:0:0 = 0 && x20:0:0 <= x16:0:0 - 1 && x16:0:0 - 2 * x23:0:0 >= 0 && x16:0:0 - 2 * x23:0:0 <= 1 && x16:0:0 - 2 * x20:0:0 >= 0 && x16:0:0 - 2 * x20:0:0 <= 1

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

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

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

(16)
YES