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, 963 ms]
(4) AND
    (5) IRSwT
        (6) IntTRSCompressionProof [EQUIVALENT, 6 ms]
        (7) IRSwT
        (8) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (9) IRSwT
        (10) TempFilterProof [SOUND, 7 ms]
        (11) IntTRS
        (12) RankingReductionPairProof [EQUIVALENT, 0 ms]
        (13) YES
    (14) IRSwT
        (15) IntTRSCompressionProof [EQUIVALENT, 7 ms]
        (16) IRSwT
        (17) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (18) IRSwT
        (19) TempFilterProof [SOUND, 14 ms]
        (20) IntTRS
        (21) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
        (22) YES
    (23) IRSwT
        (24) IntTRSCompressionProof [EQUIVALENT, 18 ms]
        (25) IRSwT
        (26) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (27) IRSwT
        (28) TempFilterProof [SOUND, 12 ms]
        (29) IntTRS
        (30) RankingReductionPairProof [EQUIVALENT, 9 ms]
        (31) YES


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

(0)
Obligation:
Rules:
l0(__const_10HAT0, i2HAT0, size1010HAT0, size1HAT0, size77HAT0, tmp1111HAT0, tmp88HAT0) -> l1(__const_10HATpost, i2HATpost, size1010HATpost, size1HATpost, size77HATpost, tmp1111HATpost, tmp88HATpost) :|: tmp88HAT0 = tmp88HATpost && tmp1111HAT0 = tmp1111HATpost && size77HAT0 = size77HATpost && size1010HAT0 = size1010HATpost && size1HAT0 = size1HATpost && i2HAT0 = i2HATpost && __const_10HAT0 = __const_10HATpost
l2(x, x1, x2, x3, x4, x5, x6) -> l3(x7, x8, x9, x10, x11, x12, x13) :|: x6 = x13 && x5 = x12 && x4 = x11 && x2 = x9 && x3 = x10 && x1 = x8 && x = x7 && x3 <= x1
l2(x14, x15, x16, x17, x18, x19, x20) -> l4(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x19 = x26 && x18 = x25 && x16 = x23 && x17 = x24 && x14 = x21 && x22 = 1 + x15 && 1 + x15 <= x17
l5(x28, x29, x30, x31, x32, x33, x34) -> l6(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x33 = x40 && x32 = x39 && x30 = x37 && x31 = x38 && x29 = x36 && x28 = x35
l6(x42, x43, x44, x45, x46, x47, x48) -> l4(x49, x50, x51, x52, x53, x54, x55) :|: x48 = x55 && x47 = x54 && x46 = x53 && x44 = x51 && x45 = x52 && x42 = x49 && x50 = 0 && x45 <= x43
l6(x56, x57, x58, x59, x60, x61, x62) -> l5(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x58 = x65 && x59 = x66 && x56 = x63 && x64 = 1 + x57 && 1 + x57 <= x59
l4(x70, x71, x72, x73, x74, x75, x76) -> l2(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x72 = x79 && x73 = x80 && x71 = x78 && x70 = x77
l1(x84, x85, x86, x87, x88, x89, x90) -> l5(x91, x92, x93, x94, x95, x96, x97) :|: x90 = x97 && x89 = x96 && x88 = x95 && x86 = x93 && x87 = x94 && x84 = x91 && x92 = 0 && x87 <= x85
l1(x98, x99, x100, x101, x102, x103, x104) -> l0(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x100 = x107 && x101 = x108 && x98 = x105 && x106 = 1 + x99 && 1 + x99 <= x101
l7(x112, x113, x114, x115, x116, x117, x118) -> l0(x119, x120, x121, x122, x123, x124, x125) :|: x112 = x119 && x120 = 0 && x124 = x124 && x121 = x122 && x125 = x125 && x123 = x122 && x122 = x112
l8(x126, x127, x128, x129, x130, x131, x132) -> l7(x133, x134, x135, x136, x137, x138, x139) :|: x132 = x139 && x131 = x138 && x130 = x137 && x128 = x135 && x129 = x136 && x127 = x134 && x126 = x133
Start term: l8(__const_10HAT0, i2HAT0, size1010HAT0, size1HAT0, size77HAT0, tmp1111HAT0, tmp88HAT0)

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

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

(2)
Obligation:
Rules:
l0(__const_10HAT0, i2HAT0, size1010HAT0, size1HAT0, size77HAT0, tmp1111HAT0, tmp88HAT0) -> l1(__const_10HATpost, i2HATpost, size1010HATpost, size1HATpost, size77HATpost, tmp1111HATpost, tmp88HATpost) :|: tmp88HAT0 = tmp88HATpost && tmp1111HAT0 = tmp1111HATpost && size77HAT0 = size77HATpost && size1010HAT0 = size1010HATpost && size1HAT0 = size1HATpost && i2HAT0 = i2HATpost && __const_10HAT0 = __const_10HATpost
l2(x, x1, x2, x3, x4, x5, x6) -> l3(x7, x8, x9, x10, x11, x12, x13) :|: x6 = x13 && x5 = x12 && x4 = x11 && x2 = x9 && x3 = x10 && x1 = x8 && x = x7 && x3 <= x1
l2(x14, x15, x16, x17, x18, x19, x20) -> l4(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x19 = x26 && x18 = x25 && x16 = x23 && x17 = x24 && x14 = x21 && x22 = 1 + x15 && 1 + x15 <= x17
l5(x28, x29, x30, x31, x32, x33, x34) -> l6(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x33 = x40 && x32 = x39 && x30 = x37 && x31 = x38 && x29 = x36 && x28 = x35
l6(x42, x43, x44, x45, x46, x47, x48) -> l4(x49, x50, x51, x52, x53, x54, x55) :|: x48 = x55 && x47 = x54 && x46 = x53 && x44 = x51 && x45 = x52 && x42 = x49 && x50 = 0 && x45 <= x43
l6(x56, x57, x58, x59, x60, x61, x62) -> l5(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x58 = x65 && x59 = x66 && x56 = x63 && x64 = 1 + x57 && 1 + x57 <= x59
l4(x70, x71, x72, x73, x74, x75, x76) -> l2(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x72 = x79 && x73 = x80 && x71 = x78 && x70 = x77
l1(x84, x85, x86, x87, x88, x89, x90) -> l5(x91, x92, x93, x94, x95, x96, x97) :|: x90 = x97 && x89 = x96 && x88 = x95 && x86 = x93 && x87 = x94 && x84 = x91 && x92 = 0 && x87 <= x85
l1(x98, x99, x100, x101, x102, x103, x104) -> l0(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x100 = x107 && x101 = x108 && x98 = x105 && x106 = 1 + x99 && 1 + x99 <= x101
l7(x112, x113, x114, x115, x116, x117, x118) -> l0(x119, x120, x121, x122, x123, x124, x125) :|: x112 = x119 && x120 = 0 && x124 = x124 && x121 = x122 && x125 = x125 && x123 = x122 && x122 = x112
l8(x126, x127, x128, x129, x130, x131, x132) -> l7(x133, x134, x135, x136, x137, x138, x139) :|: x132 = x139 && x131 = x138 && x130 = x137 && x128 = x135 && x129 = x136 && x127 = x134 && x126 = x133
Start term: l8(__const_10HAT0, i2HAT0, size1010HAT0, size1HAT0, size77HAT0, tmp1111HAT0, tmp88HAT0)

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

(3) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) l0(__const_10HAT0, i2HAT0, size1010HAT0, size1HAT0, size77HAT0, tmp1111HAT0, tmp88HAT0) -> l1(__const_10HATpost, i2HATpost, size1010HATpost, size1HATpost, size77HATpost, tmp1111HATpost, tmp88HATpost) :|: tmp88HAT0 = tmp88HATpost && tmp1111HAT0 = tmp1111HATpost && size77HAT0 = size77HATpost && size1010HAT0 = size1010HATpost && size1HAT0 = size1HATpost && i2HAT0 = i2HATpost && __const_10HAT0 = __const_10HATpost
(2) l2(x, x1, x2, x3, x4, x5, x6) -> l3(x7, x8, x9, x10, x11, x12, x13) :|: x6 = x13 && x5 = x12 && x4 = x11 && x2 = x9 && x3 = x10 && x1 = x8 && x = x7 && x3 <= x1
(3) l2(x14, x15, x16, x17, x18, x19, x20) -> l4(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x19 = x26 && x18 = x25 && x16 = x23 && x17 = x24 && x14 = x21 && x22 = 1 + x15 && 1 + x15 <= x17
(4) l5(x28, x29, x30, x31, x32, x33, x34) -> l6(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x33 = x40 && x32 = x39 && x30 = x37 && x31 = x38 && x29 = x36 && x28 = x35
(5) l6(x42, x43, x44, x45, x46, x47, x48) -> l4(x49, x50, x51, x52, x53, x54, x55) :|: x48 = x55 && x47 = x54 && x46 = x53 && x44 = x51 && x45 = x52 && x42 = x49 && x50 = 0 && x45 <= x43
(6) l6(x56, x57, x58, x59, x60, x61, x62) -> l5(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x58 = x65 && x59 = x66 && x56 = x63 && x64 = 1 + x57 && 1 + x57 <= x59
(7) l4(x70, x71, x72, x73, x74, x75, x76) -> l2(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x72 = x79 && x73 = x80 && x71 = x78 && x70 = x77
(8) l1(x84, x85, x86, x87, x88, x89, x90) -> l5(x91, x92, x93, x94, x95, x96, x97) :|: x90 = x97 && x89 = x96 && x88 = x95 && x86 = x93 && x87 = x94 && x84 = x91 && x92 = 0 && x87 <= x85
(9) l1(x98, x99, x100, x101, x102, x103, x104) -> l0(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x100 = x107 && x101 = x108 && x98 = x105 && x106 = 1 + x99 && 1 + x99 <= x101
(10) l7(x112, x113, x114, x115, x116, x117, x118) -> l0(x119, x120, x121, x122, x123, x124, x125) :|: x112 = x119 && x120 = 0 && x124 = x124 && x121 = x122 && x125 = x125 && x123 = x122 && x122 = x112
(11) l8(x126, x127, x128, x129, x130, x131, x132) -> l7(x133, x134, x135, x136, x137, x138, x139) :|: x132 = x139 && x131 = x138 && x130 = x137 && x128 = x135 && x129 = x136 && x127 = x134 && x126 = x133

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

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

(4)
Complex Obligation (AND)

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

(5)
Obligation:

Termination digraph:
Nodes:
(1) l0(__const_10HAT0, i2HAT0, size1010HAT0, size1HAT0, size77HAT0, tmp1111HAT0, tmp88HAT0) -> l1(__const_10HATpost, i2HATpost, size1010HATpost, size1HATpost, size77HATpost, tmp1111HATpost, tmp88HATpost) :|: tmp88HAT0 = tmp88HATpost && tmp1111HAT0 = tmp1111HATpost && size77HAT0 = size77HATpost && size1010HAT0 = size1010HATpost && size1HAT0 = size1HATpost && i2HAT0 = i2HATpost && __const_10HAT0 = __const_10HATpost
(2) l1(x98, x99, x100, x101, x102, x103, x104) -> l0(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x100 = x107 && x101 = x108 && x98 = x105 && x106 = 1 + x99 && 1 + x99 <= x101

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

This digraph is fully evaluated!

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

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

(7)
Obligation:
Rules:
l0(__const_10HAT0:0, i2HAT0:0, size1010HAT0:0, size1HAT0:0, size77HAT0:0, tmp1111HAT0:0, tmp88HAT0:0) -> l0(__const_10HAT0:0, 1 + i2HAT0:0, size1010HAT0:0, size1HAT0:0, size77HAT0:0, tmp1111HAT0:0, tmp88HAT0:0) :|: size1HAT0:0 >= 1 + i2HAT0:0

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

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

   l0(x1, x2, x3, x4, x5, x6, x7) -> l0(x2, x4)

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

(9)
Obligation:
Rules:
l0(i2HAT0:0, size1HAT0:0) -> l0(1 + i2HAT0:0, size1HAT0:0) :|: size1HAT0:0 >= 1 + i2HAT0:0

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

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

(11)
Obligation:
Rules:
l0(i2HAT0:0, size1HAT0:0) -> l0(c, size1HAT0:0) :|: c = 1 + i2HAT0:0 && size1HAT0:0 >= 1 + i2HAT0:0

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

(12) RankingReductionPairProof (EQUIVALENT)
Interpretation:
[ l0 ] = l0_2 + -1*l0_1

The following rules are decreasing:
l0(i2HAT0:0, size1HAT0:0) -> l0(c, size1HAT0:0) :|: c = 1 + i2HAT0:0 && size1HAT0:0 >= 1 + i2HAT0:0

The following rules are bounded:
l0(i2HAT0:0, size1HAT0:0) -> l0(c, size1HAT0:0) :|: c = 1 + i2HAT0:0 && size1HAT0:0 >= 1 + i2HAT0:0


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

(13)
YES

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

(14)
Obligation:

Termination digraph:
Nodes:
(1) l5(x28, x29, x30, x31, x32, x33, x34) -> l6(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x33 = x40 && x32 = x39 && x30 = x37 && x31 = x38 && x29 = x36 && x28 = x35
(2) l6(x56, x57, x58, x59, x60, x61, x62) -> l5(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x58 = x65 && x59 = x66 && x56 = x63 && x64 = 1 + x57 && 1 + x57 <= x59

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

This digraph is fully evaluated!

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

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

(16)
Obligation:
Rules:
l5(x28:0, x29:0, x30:0, x31:0, x32:0, x33:0, x34:0) -> l5(x28:0, 1 + x29:0, x30:0, x31:0, x32:0, x33:0, x34:0) :|: x31:0 >= 1 + x29:0

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

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

   l5(x1, x2, x3, x4, x5, x6, x7) -> l5(x2, x4)

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

(18)
Obligation:
Rules:
l5(x29:0, x31:0) -> l5(1 + x29:0, x31:0) :|: x31:0 >= 1 + x29:0

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

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

(20)
Obligation:
Rules:
l5(x29:0, x31:0) -> l5(c, x31:0) :|: c = 1 + x29:0 && x31:0 >= 1 + x29:0

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

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

The following rules are decreasing:
l5(x29:0, x31:0) -> l5(c, x31:0) :|: c = 1 + x29:0 && x31:0 >= 1 + x29:0
The following rules are bounded:
l5(x29:0, x31:0) -> l5(c, x31:0) :|: c = 1 + x29:0 && x31:0 >= 1 + x29:0

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

(22)
YES

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

(23)
Obligation:

Termination digraph:
Nodes:
(1) l4(x70, x71, x72, x73, x74, x75, x76) -> l2(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x72 = x79 && x73 = x80 && x71 = x78 && x70 = x77
(2) l2(x14, x15, x16, x17, x18, x19, x20) -> l4(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x19 = x26 && x18 = x25 && x16 = x23 && x17 = x24 && x14 = x21 && x22 = 1 + x15 && 1 + x15 <= x17

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

This digraph is fully evaluated!

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

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

(25)
Obligation:
Rules:
l4(x21:0, x71:0, x23:0, x24:0, x25:0, x26:0, x27:0) -> l4(x21:0, 1 + x71:0, x23:0, x24:0, x25:0, x26:0, x27:0) :|: x24:0 >= 1 + x71:0

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

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

   l4(x1, x2, x3, x4, x5, x6, x7) -> l4(x2, x4)

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

(27)
Obligation:
Rules:
l4(x71:0, x24:0) -> l4(1 + x71:0, x24:0) :|: x24:0 >= 1 + x71:0

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

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

(29)
Obligation:
Rules:
l4(x71:0, x24:0) -> l4(c, x24:0) :|: c = 1 + x71:0 && x24:0 >= 1 + x71:0

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

(30) RankingReductionPairProof (EQUIVALENT)
Interpretation:
[ l4 ] = l4_2 + -1*l4_1

The following rules are decreasing:
l4(x71:0, x24:0) -> l4(c, x24:0) :|: c = 1 + x71:0 && x24:0 >= 1 + x71:0

The following rules are bounded:
l4(x71:0, x24:0) -> l4(c, x24:0) :|: c = 1 + x71:0 && x24:0 >= 1 + x71:0


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

(31)
YES