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


Termination of the given IRSwT could not be shown:

(0) IRSwT
(1) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(2) IRSwT
(3) IRSwTTerminationDigraphProof [EQUIVALENT, 172 ms]
(4) IRSwT
(5) IntTRSCompressionProof [EQUIVALENT, 40 ms]
(6) IRSwT
(7) IRSwTChainingProof [EQUIVALENT, 0 ms]
(8) IRSwT
(9) IRSwTTerminationDigraphProof [EQUIVALENT, 12 ms]
(10) IRSwT
(11) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(12) IRSwT
(13) TempFilterProof [SOUND, 274 ms]
(14) IRSwT
(15) IRSwTTerminationDigraphProof [EQUIVALENT, 12 ms]
(16) IRSwT


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

(0)
Obligation:
Rules:
l0(op1HAT0, op2HAT0) -> l1(op1HATpost, op2HATpost) :|: op2HAT0 = op2HATpost && op1HAT0 = op1HATpost && 0 <= op1HAT0 && 0 <= op2HAT0 && op2HAT0 <= 0
l2(x, x1) -> l3(x2, x3) :|: x3 = -1 + x1 && x2 = 1 + x && 1 <= x1
l3(x4, x5) -> l2(x6, x7) :|: x5 = x7 && x4 = x6
l2(x8, x9) -> l4(x10, x11) :|: x11 = 1 + x9 && x10 = -1 + x8 && 1 <= x8
l4(x12, x13) -> l2(x14, x15) :|: x12 = x14 && x15 = -1 + x13 && 1 <= x13
l4(x16, x17) -> l1(x18, x19) :|: x17 = x19 && x16 = x18
l1(x20, x21) -> l4(x22, x23) :|: x23 = 1 + x21 && x22 = -1 + x20 && 1 <= x20
l5(x24, x25) -> l0(x26, x27) :|: x25 = x27 && x24 = x26
Start term: l5(op1HAT0, op2HAT0)

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

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

(2)
Obligation:
Rules:
l0(op1HAT0, op2HAT0) -> l1(op1HATpost, op2HATpost) :|: op2HAT0 = op2HATpost && op1HAT0 = op1HATpost && 0 <= op1HAT0 && 0 <= op2HAT0 && op2HAT0 <= 0
l2(x, x1) -> l3(x2, x3) :|: x3 = -1 + x1 && x2 = 1 + x && 1 <= x1
l3(x4, x5) -> l2(x6, x7) :|: x5 = x7 && x4 = x6
l2(x8, x9) -> l4(x10, x11) :|: x11 = 1 + x9 && x10 = -1 + x8 && 1 <= x8
l4(x12, x13) -> l2(x14, x15) :|: x12 = x14 && x15 = -1 + x13 && 1 <= x13
l4(x16, x17) -> l1(x18, x19) :|: x17 = x19 && x16 = x18
l1(x20, x21) -> l4(x22, x23) :|: x23 = 1 + x21 && x22 = -1 + x20 && 1 <= x20
l5(x24, x25) -> l0(x26, x27) :|: x25 = x27 && x24 = x26
Start term: l5(op1HAT0, op2HAT0)

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

(3) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) l0(op1HAT0, op2HAT0) -> l1(op1HATpost, op2HATpost) :|: op2HAT0 = op2HATpost && op1HAT0 = op1HATpost && 0 <= op1HAT0 && 0 <= op2HAT0 && op2HAT0 <= 0
(2) l2(x, x1) -> l3(x2, x3) :|: x3 = -1 + x1 && x2 = 1 + x && 1 <= x1
(3) l3(x4, x5) -> l2(x6, x7) :|: x5 = x7 && x4 = x6
(4) l2(x8, x9) -> l4(x10, x11) :|: x11 = 1 + x9 && x10 = -1 + x8 && 1 <= x8
(5) l4(x12, x13) -> l2(x14, x15) :|: x12 = x14 && x15 = -1 + x13 && 1 <= x13
(6) l4(x16, x17) -> l1(x18, x19) :|: x17 = x19 && x16 = x18
(7) l1(x20, x21) -> l4(x22, x23) :|: x23 = 1 + x21 && x22 = -1 + x20 && 1 <= x20
(8) l5(x24, x25) -> l0(x26, x27) :|: x25 = x27 && x24 = x26

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

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

(4)
Obligation:

Termination digraph:
Nodes:
(1) l1(x20, x21) -> l4(x22, x23) :|: x23 = 1 + x21 && x22 = -1 + x20 && 1 <= x20
(2) l4(x16, x17) -> l1(x18, x19) :|: x17 = x19 && x16 = x18
(3) l2(x8, x9) -> l4(x10, x11) :|: x11 = 1 + x9 && x10 = -1 + x8 && 1 <= x8
(4) l3(x4, x5) -> l2(x6, x7) :|: x5 = x7 && x4 = x6
(5) l2(x, x1) -> l3(x2, x3) :|: x3 = -1 + x1 && x2 = 1 + x && 1 <= x1
(6) l4(x12, x13) -> l2(x14, x15) :|: x12 = x14 && x15 = -1 + x13 && 1 <= x13

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

This digraph is fully evaluated!

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

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

(6)
Obligation:
Rules:
l2(x:0, x1:0) -> l2(1 + x:0, -1 + x1:0) :|: x1:0 > 0
l4(x12:0, x13:0) -> l2(x12:0, -1 + x13:0) :|: x13:0 > 0
l2(x8:0, x9:0) -> l4(-1 + x8:0, 1 + x9:0) :|: x8:0 > 0
l4(x16:0, x17:0) -> l4(-1 + x16:0, 1 + x17:0) :|: x16:0 > 0

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

(7) IRSwTChainingProof (EQUIVALENT)
Chaining!
----------------------------------------

(8)
Obligation:
Rules:
l2(x, x1) -> l2(2 + x, -2 + x1) :|: TRUE && x1 >= 2
l4(x12:0, x13:0) -> l2(x12:0, -1 + x13:0) :|: x13:0 > 0
l2(x8:0, x9:0) -> l4(-1 + x8:0, 1 + x9:0) :|: x8:0 > 0
l2(x8, x9) -> l4(x8, x9) :|: TRUE && x9 >= 1 && x8 >= 0
l4(x16:0, x17:0) -> l4(-1 + x16:0, 1 + x17:0) :|: x16:0 > 0

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

(9) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) l2(x, x1) -> l2(2 + x, -2 + x1) :|: TRUE && x1 >= 2
(2) l4(x12:0, x13:0) -> l2(x12:0, -1 + x13:0) :|: x13:0 > 0
(3) l2(x8:0, x9:0) -> l4(-1 + x8:0, 1 + x9:0) :|: x8:0 > 0
(4) l2(x8, x9) -> l4(x8, x9) :|: TRUE && x9 >= 1 && x8 >= 0
(5) l4(x16:0, x17:0) -> l4(-1 + x16:0, 1 + x17:0) :|: x16:0 > 0

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

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

(10)
Obligation:

Termination digraph:
Nodes:
(1) l2(x, x1) -> l2(2 + x, -2 + x1) :|: TRUE && x1 >= 2
(2) l4(x12:0, x13:0) -> l2(x12:0, -1 + x13:0) :|: x13:0 > 0
(3) l4(x16:0, x17:0) -> l4(-1 + x16:0, 1 + x17:0) :|: x16:0 > 0
(4) l2(x8, x9) -> l4(x8, x9) :|: TRUE && x9 >= 1 && x8 >= 0
(5) l2(x8:0, x9:0) -> l4(-1 + x8:0, 1 + x9:0) :|: x8:0 > 0

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

This digraph is fully evaluated!

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

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

(12)
Obligation:
Rules:
l4(x16:0:0, x17:0:0) -> l4(-1 + x16:0:0, 1 + x17:0:0) :|: x16:0:0 > 0
l2(x8:0, x9:0) -> l4(x8:0, x9:0) :|: x8:0 > -1 && x9:0 > 0
l2(x:0, x1:0) -> l2(2 + x:0, -2 + x1:0) :|: x1:0 > 1
l4(x12:0:0, x13:0:0) -> l2(x12:0:0, -1 + x13:0:0) :|: x13:0:0 > 0
l2(x8:0:0, x9:0:0) -> l4(-1 + x8:0:0, 1 + x9:0:0) :|: x8:0:0 > 0

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

(13) TempFilterProof (SOUND)
Used the following sort dictionary for filtering: 
l4(VARIABLE, VARIABLE)
l2(VARIABLE, VARIABLE)
Replaced non-predefined constructor symbols by 0.The following proof was generated: 
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination of the given IntTRS could not be shown:



- IntTRS
  - PolynomialOrderProcessor

Rules:
l4(x16:0:0, x17:0:0) -> l4(c, c1) :|: c1 = 1 + x17:0:0 && c = -1 + x16:0:0 && x16:0:0 > 0
l2(x8:0, x9:0) -> l4(x8:0, x9:0) :|: x8:0 > -1 && x9:0 > 0
l2(x:0, x1:0) -> l2(c2, c3) :|: c3 = -2 + x1:0 && c2 = 2 + x:0 && x1:0 > 1
l4(x12:0:0, x13:0:0) -> l2(x12:0:0, c4) :|: c4 = -1 + x13:0:0 && x13:0:0 > 0
l2(x8:0:0, x9:0:0) -> l4(c5, c6) :|: c6 = 1 + x9:0:0 && c5 = -1 + x8:0:0 && x8:0:0 > 0

Found the following polynomial interpretation:
[l4(x, x1)] = -1 + x + x1
[l2(x2, x3)] = -1 + x2 + x3

The following rules are decreasing:
l4(x12:0:0, x13:0:0) -> l2(x12:0:0, c4) :|: c4 = -1 + x13:0:0 && x13:0:0 > 0
The following rules are bounded:
l2(x8:0, x9:0) -> l4(x8:0, x9:0) :|: x8:0 > -1 && x9:0 > 0



- IntTRS
  - PolynomialOrderProcessor
    - AND
      - IntTRS
      - IntTRS
        - PolynomialOrderProcessor
      - IntTRS

Rules:
l4(x16:0:0, x17:0:0) -> l4(c, c1) :|: c1 = 1 + x17:0:0 && c = -1 + x16:0:0 && x16:0:0 > 0
l2(x8:0, x9:0) -> l4(x8:0, x9:0) :|: x8:0 > -1 && x9:0 > 0
l2(x:0, x1:0) -> l2(c2, c3) :|: c3 = -2 + x1:0 && c2 = 2 + x:0 && x1:0 > 1
l2(x8:0:0, x9:0:0) -> l4(c5, c6) :|: c6 = 1 + x9:0:0 && c5 = -1 + x8:0:0 && x8:0:0 > 0

Found the following polynomial interpretation:
[l4(x, x1)] = -2 + x + x1
[l2(x2, x3)] = -1 + x2 + x3

The following rules are decreasing:
l2(x8:0, x9:0) -> l4(x8:0, x9:0) :|: x8:0 > -1 && x9:0 > 0
l2(x8:0:0, x9:0:0) -> l4(c5, c6) :|: c6 = 1 + x9:0:0 && c5 = -1 + x8:0:0 && x8:0:0 > 0
The following rules are bounded:
l2(x8:0, x9:0) -> l4(x8:0, x9:0) :|: x8:0 > -1 && x9:0 > 0


- IntTRS
  - PolynomialOrderProcessor
    - AND
      - IntTRS
      - IntTRS
        - PolynomialOrderProcessor
          - IntTRS
            - RankingReductionPairProof
      - IntTRS

Rules:
l4(x16:0:0, x17:0:0) -> l4(c, c1) :|: c1 = 1 + x17:0:0 && c = -1 + x16:0:0 && x16:0:0 > 0
l2(x:0, x1:0) -> l2(c2, c3) :|: c3 = -2 + x1:0 && c2 = 2 + x:0 && x1:0 > 1
l2(x8:0:0, x9:0:0) -> l4(c5, c6) :|: c6 = 1 + x9:0:0 && c5 = -1 + x8:0:0 && x8:0:0 > 0

Interpretation:
[ l4 ] = 0
[ l2 ] = 1

The following rules are decreasing:
l2(x8:0:0, x9:0:0) -> l4(c5, c6) :|: c6 = 1 + x9:0:0 && c5 = -1 + x8:0:0 && x8:0:0 > 0

The following rules are bounded:
l4(x16:0:0, x17:0:0) -> l4(c, c1) :|: c1 = 1 + x17:0:0 && c = -1 + x16:0:0 && x16:0:0 > 0
l2(x:0, x1:0) -> l2(c2, c3) :|: c3 = -2 + x1:0 && c2 = 2 + x:0 && x1:0 > 1
l2(x8:0:0, x9:0:0) -> l4(c5, c6) :|: c6 = 1 + x9:0:0 && c5 = -1 + x8:0:0 && x8:0:0 > 0



- IntTRS
  - PolynomialOrderProcessor
    - AND
      - IntTRS
      - IntTRS
        - PolynomialOrderProcessor
          - IntTRS
            - RankingReductionPairProof
              - IntTRS
                - RankingReductionPairProof
      - IntTRS

Rules:
l4(x16:0:0, x17:0:0) -> l4(c, c1) :|: c1 = 1 + x17:0:0 && c = -1 + x16:0:0 && x16:0:0 > 0
l2(x:0, x1:0) -> l2(c2, c3) :|: c3 = -2 + x1:0 && c2 = 2 + x:0 && x1:0 > 1

Interpretation:
[ l4 ] = l4_1
[ l2 ] = 1/2*l2_2

The following rules are decreasing:
l4(x16:0:0, x17:0:0) -> l4(c, c1) :|: c1 = 1 + x17:0:0 && c = -1 + x16:0:0 && x16:0:0 > 0
l2(x:0, x1:0) -> l2(c2, c3) :|: c3 = -2 + x1:0 && c2 = 2 + x:0 && x1:0 > 1

The following rules are bounded:
l4(x16:0:0, x17:0:0) -> l4(c, c1) :|: c1 = 1 + x17:0:0 && c = -1 + x16:0:0 && x16:0:0 > 0
l2(x:0, x1:0) -> l2(c2, c3) :|: c3 = -2 + x1:0 && c2 = 2 + x:0 && x1:0 > 1




- IntTRS
  - PolynomialOrderProcessor
    - AND
      - IntTRS
      - IntTRS
      - IntTRS

Rules:
l4(x16:0:0, x17:0:0) -> l4(c, c1) :|: c1 = 1 + x17:0:0 && c = -1 + x16:0:0 && x16:0:0 > 0
l2(x:0, x1:0) -> l2(c2, c3) :|: c3 = -2 + x1:0 && c2 = 2 + x:0 && x1:0 > 1
l4(x12:0:0, x13:0:0) -> l2(x12:0:0, c4) :|: c4 = -1 + x13:0:0 && x13:0:0 > 0
l2(x8:0:0, x9:0:0) -> l4(c5, c6) :|: c6 = 1 + x9:0:0 && c5 = -1 + x8:0:0 && x8:0:0 > 0



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

(14)
Obligation:
Rules:
l4(x16:0:0, x17:0:0) -> l4(-1 + x16:0:0, 1 + x17:0:0) :|: x16:0:0 > 0
l2(x:0, x1:0) -> l2(2 + x:0, -2 + x1:0) :|: x1:0 > 1
l4(x12:0:0, x13:0:0) -> l2(x12:0:0, -1 + x13:0:0) :|: x13:0:0 > 0
l2(x8:0:0, x9:0:0) -> l4(-1 + x8:0:0, 1 + x9:0:0) :|: x8:0:0 > 0

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

(15) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) l4(x16:0:0, x17:0:0) -> l4(-1 + x16:0:0, 1 + x17:0:0) :|: x16:0:0 > 0
(2) l2(x:0, x1:0) -> l2(2 + x:0, -2 + x1:0) :|: x1:0 > 1
(3) l4(x12:0:0, x13:0:0) -> l2(x12:0:0, -1 + x13:0:0) :|: x13:0:0 > 0
(4) l2(x8:0:0, x9:0:0) -> l4(-1 + x8:0:0, 1 + x9:0:0) :|: x8:0:0 > 0

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

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

(16)
Obligation:

Termination digraph:
Nodes:
(1) l4(x16:0:0, x17:0:0) -> l4(-1 + x16:0:0, 1 + x17:0:0) :|: x16:0:0 > 0
(2) l2(x8:0:0, x9:0:0) -> l4(-1 + x8:0:0, 1 + x9:0:0) :|: x8:0:0 > 0
(3) l2(x:0, x1:0) -> l2(2 + x:0, -2 + x1:0) :|: x1:0 > 1
(4) l4(x12:0:0, x13:0:0) -> l2(x12:0:0, -1 + x13:0:0) :|: x13:0:0 > 0

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

This digraph is fully evaluated!