Certification Problem

Input (TPDB SRS_Standard/ICFP_2010/39849)

The rewrite relation of the following TRS is considered.

0(1(2(x1))) → 0(2(1(1(x1)))) (1)
0(3(2(x1))) → 0(2(1(3(x1)))) (2)
2(4(1(x1))) → 4(2(1(1(x1)))) (3)
0(0(3(2(x1)))) → 0(0(2(1(3(x1))))) (4)
0(1(0(3(x1)))) → 0(1(1(3(0(x1))))) (5)
0(1(0(5(x1)))) → 0(0(1(1(5(x1))))) (6)
0(1(2(2(x1)))) → 0(2(1(1(2(x1))))) (7)
0(1(2(3(x1)))) → 0(2(1(3(1(x1))))) (8)
0(1(2(5(x1)))) → 2(1(1(0(5(x1))))) (9)
0(1(4(1(x1)))) → 0(4(1(1(1(x1))))) (10)
0(1(4(2(x1)))) → 0(0(2(1(4(x1))))) (11)
0(1(4(2(x1)))) → 0(4(0(2(1(x1))))) (12)
0(1(4(3(x1)))) → 4(0(1(1(3(x1))))) (13)
0(1(4(5(x1)))) → 0(1(1(5(4(x1))))) (14)
0(1(5(2(x1)))) → 0(2(5(1(1(x1))))) (15)
0(2(0(3(x1)))) → 0(0(2(3(1(x1))))) (16)
0(3(0(1(x1)))) → 0(0(1(3(1(x1))))) (17)
0(3(0(2(x1)))) → 0(0(2(3(1(x1))))) (18)
0(3(0(3(x1)))) → 0(0(3(1(3(x1))))) (19)
0(3(2(0(x1)))) → 0(2(1(3(0(x1))))) (20)
0(3(5(1(x1)))) → 0(5(3(1(1(x1))))) (21)
0(4(0(1(x1)))) → 0(0(4(1(1(x1))))) (22)
0(5(2(0(x1)))) → 2(1(5(0(0(x1))))) (23)
2(1(2(3(x1)))) → 2(1(1(3(2(x1))))) (24)
2(1(4(1(x1)))) → 4(2(1(1(1(x1))))) (25)
2(2(0(3(x1)))) → 2(0(2(1(3(x1))))) (26)
2(2(4(1(x1)))) → 2(4(2(1(1(x1))))) (27)
2(3(1(4(x1)))) → 2(1(1(3(4(x1))))) (28)
2(4(1(4(x1)))) → 4(4(2(1(1(x1))))) (29)
2(4(3(1(x1)))) → 4(2(3(1(1(x1))))) (30)
2(5(0(1(x1)))) → 0(2(5(1(1(x1))))) (31)
2(5(0(3(x1)))) → 5(0(2(1(3(x1))))) (32)
3(0(1(0(x1)))) → 3(1(0(0(0(x1))))) (33)
3(0(1(4(x1)))) → 3(1(1(0(4(x1))))) (34)
3(0(3(0(x1)))) → 3(1(3(0(0(x1))))) (35)
3(1(0(3(x1)))) → 3(1(1(3(0(x1))))) (36)
3(1(2(1(x1)))) → 1(3(2(1(1(x1))))) (37)
3(1(2(1(x1)))) → 3(2(1(1(1(x1))))) (38)
3(2(0(1(x1)))) → 1(3(0(2(1(x1))))) (39)
3(2(0(1(x1)))) → 3(1(0(2(1(x1))))) (40)
3(4(1(2(x1)))) → 3(2(1(1(4(x1))))) (41)
3(5(1(4(x1)))) → 3(1(1(5(4(x1))))) (42)
4(1(0(1(x1)))) → 4(0(1(1(1(x1))))) (43)
4(1(2(1(x1)))) → 2(4(1(1(1(x1))))) (44)
4(1(4(3(x1)))) → 4(1(1(3(4(x1))))) (45)
4(2(4(1(x1)))) → 4(4(2(1(1(x1))))) (46)
4(4(1(2(x1)))) → 4(2(1(1(4(x1))))) (47)
4(5(0(1(x1)))) → 5(0(4(1(1(x1))))) (48)
5(1(0(3(x1)))) → 5(0(1(1(3(x1))))) (49)
5(1(0(3(x1)))) → 5(1(1(3(0(x1))))) (50)
5(1(3(1(x1)))) → 5(3(1(1(1(x1))))) (51)
5(1(4(3(x1)))) → 4(1(1(3(5(x1))))) (52)
5(1(4(4(x1)))) → 4(1(1(5(4(x1))))) (53)
5(1(5(3(x1)))) → 5(5(1(1(3(x1))))) (54)
5(2(0(1(x1)))) → 2(0(5(1(1(x1))))) (55)
5(2(0(5(x1)))) → 5(0(2(1(5(x1))))) (56)
5(3(4(1(x1)))) → 5(4(3(1(1(x1))))) (57)
5(4(0(1(x1)))) → 5(0(4(1(1(x1))))) (58)
5(4(1(0(x1)))) → 4(1(1(5(0(x1))))) (59)
5(4(1(0(x1)))) → 5(1(1(4(0(x1))))) (60)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by AProVE @ termCOMP 2023)

1 String Reversal

Since only unary symbols occur, one can reverse all terms and obtains the TRS
2(1(0(x1))) → 1(1(2(0(x1)))) (61)
2(3(0(x1))) → 3(1(2(0(x1)))) (62)
1(4(2(x1))) → 1(1(2(4(x1)))) (63)
2(3(0(0(x1)))) → 3(1(2(0(0(x1))))) (64)
3(0(1(0(x1)))) → 0(3(1(1(0(x1))))) (65)
5(0(1(0(x1)))) → 5(1(1(0(0(x1))))) (66)
2(2(1(0(x1)))) → 2(1(1(2(0(x1))))) (67)
3(2(1(0(x1)))) → 1(3(1(2(0(x1))))) (68)
5(2(1(0(x1)))) → 5(0(1(1(2(x1))))) (69)
1(4(1(0(x1)))) → 1(1(1(4(0(x1))))) (70)
2(4(1(0(x1)))) → 4(1(2(0(0(x1))))) (71)
2(4(1(0(x1)))) → 1(2(0(4(0(x1))))) (72)
3(4(1(0(x1)))) → 3(1(1(0(4(x1))))) (73)
5(4(1(0(x1)))) → 4(5(1(1(0(x1))))) (74)
2(5(1(0(x1)))) → 1(1(5(2(0(x1))))) (75)
3(0(2(0(x1)))) → 1(3(2(0(0(x1))))) (76)
1(0(3(0(x1)))) → 1(3(1(0(0(x1))))) (77)
2(0(3(0(x1)))) → 1(3(2(0(0(x1))))) (78)
3(0(3(0(x1)))) → 3(1(3(0(0(x1))))) (35)
0(2(3(0(x1)))) → 0(3(1(2(0(x1))))) (79)
1(5(3(0(x1)))) → 1(1(3(5(0(x1))))) (80)
1(0(4(0(x1)))) → 1(1(4(0(0(x1))))) (81)
0(2(5(0(x1)))) → 0(0(5(1(2(x1))))) (82)
3(2(1(2(x1)))) → 2(3(1(1(2(x1))))) (83)
1(4(1(2(x1)))) → 1(1(1(2(4(x1))))) (84)
3(0(2(2(x1)))) → 3(1(2(0(2(x1))))) (85)
1(4(2(2(x1)))) → 1(1(2(4(2(x1))))) (86)
4(1(3(2(x1)))) → 4(3(1(1(2(x1))))) (87)
4(1(4(2(x1)))) → 1(1(2(4(4(x1))))) (88)
1(3(4(2(x1)))) → 1(1(3(2(4(x1))))) (89)
1(0(5(2(x1)))) → 1(1(5(2(0(x1))))) (90)
3(0(5(2(x1)))) → 3(1(2(0(5(x1))))) (91)
0(1(0(3(x1)))) → 0(0(0(1(3(x1))))) (92)
4(1(0(3(x1)))) → 4(0(1(1(3(x1))))) (93)
0(3(0(3(x1)))) → 0(0(3(1(3(x1))))) (19)
3(0(1(3(x1)))) → 0(3(1(1(3(x1))))) (94)
1(2(1(3(x1)))) → 1(1(2(3(1(x1))))) (95)
1(2(1(3(x1)))) → 1(1(1(2(3(x1))))) (96)
1(0(2(3(x1)))) → 1(2(0(3(1(x1))))) (97)
1(0(2(3(x1)))) → 1(2(0(1(3(x1))))) (98)
2(1(4(3(x1)))) → 4(1(1(2(3(x1))))) (99)
4(1(5(3(x1)))) → 4(5(1(1(3(x1))))) (100)
1(0(1(4(x1)))) → 1(1(1(0(4(x1))))) (101)
1(2(1(4(x1)))) → 1(1(1(4(2(x1))))) (102)
3(4(1(4(x1)))) → 4(3(1(1(4(x1))))) (103)
1(4(2(4(x1)))) → 1(1(2(4(4(x1))))) (104)
2(1(4(4(x1)))) → 4(1(1(2(4(x1))))) (105)
1(0(5(4(x1)))) → 1(1(4(0(5(x1))))) (106)
3(0(1(5(x1)))) → 3(1(1(0(5(x1))))) (107)
3(0(1(5(x1)))) → 0(3(1(1(5(x1))))) (108)
1(3(1(5(x1)))) → 1(1(1(3(5(x1))))) (109)
3(4(1(5(x1)))) → 5(3(1(1(4(x1))))) (110)
4(4(1(5(x1)))) → 4(5(1(1(4(x1))))) (111)
3(5(1(5(x1)))) → 3(1(1(5(5(x1))))) (112)
1(0(2(5(x1)))) → 1(1(5(0(2(x1))))) (113)
5(0(2(5(x1)))) → 5(1(2(0(5(x1))))) (114)
1(4(3(5(x1)))) → 1(1(3(4(5(x1))))) (115)
1(0(4(5(x1)))) → 1(1(4(0(5(x1))))) (116)
0(1(4(5(x1)))) → 0(5(1(1(4(x1))))) (117)
0(1(4(5(x1)))) → 0(4(1(1(5(x1))))) (118)

1.1 Closure Under Flat Contexts

Using the flat contexts

{2(☐), 1(☐), 0(☐), 3(☐), 4(☐), 5(☐)}

We obtain the transformed TRS

There are 153 ruless (increase limit for explicit display).

1.1.1 Semantic Labeling

Root-labeling is applied.

We obtain the labeled TRS

There are 918 ruless (increase limit for explicit display).

1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[14(x1)] = 1 · x1 + 9
[42(x1)] = 1 · x1 + 13
[21(x1)] = 1 · x1 + 30
[11(x1)] = 1 · x1
[12(x1)] = 1 · x1
[24(x1)] = 1 · x1
[41(x1)] = 1 · x1 + 39
[44(x1)] = 1 · x1 + 9
[22(x1)] = 1 · x1 + 5
[25(x1)] = 1 · x1 + 17
[45(x1)] = 1 · x1 + 27
[20(x1)] = 1 · x1
[40(x1)] = 1 · x1 + 10
[23(x1)] = 1 · x1 + 27
[43(x1)] = 1 · x1 + 37
[50(x1)] = 1 · x1 + 23
[01(x1)] = 1 · x1 + 49
[10(x1)] = 1 · x1 + 45
[51(x1)] = 1 · x1 + 25
[00(x1)] = 1 · x1 + 36
[04(x1)] = 1 · x1 + 17
[02(x1)] = 1 · x1 + 39
[05(x1)] = 1 · x1 + 21
[03(x1)] = 1 · x1 + 48
[52(x1)] = 1 · x1
[34(x1)] = 1 · x1
[31(x1)] = 1 · x1 + 14
[30(x1)] = 1 · x1 + 37
[13(x1)] = 1 · x1 + 21
[15(x1)] = 1 · x1 + 29
[53(x1)] = 1 · x1 + 22
[35(x1)] = 1 · x1 + 20
[32(x1)] = 1 · x1 + 2
[54(x1)] = 1 · x1 + 9
[55(x1)] = 1 · x1 + 13
[33(x1)] = 1 · x1 + 13
all of the following rules can be deleted.

There are 814 ruless (increase limit for explicit display).

1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[30(x1)] = 1 · x1
[05(x1)] = 1 · x1
[52(x1)] = 1 · x1 + 1
[20(x1)] = 1 · x1
[31(x1)] = 1 · x1
[12(x1)] = 1 · x1
[50(x1)] = 1 · x1
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[00(x1)] = 1 · x1
[13(x1)] = 1 · x1
[34(x1)] = 1 · x1
[32(x1)] = 1 · x1
[35(x1)] = 1 · x1
[33(x1)] = 1 · x1
[14(x1)] = 1 · x1
[45(x1)] = 1 · x1
[51(x1)] = 1 · x1 + 1
[04(x1)] = 1 · x1
[41(x1)] = 1 · x1
[11(x1)] = 1 · x1
[15(x1)] = 1 · x1
[54(x1)] = 1 · x1 + 1
[55(x1)] = 1 · x1 + 1
[53(x1)] = 1 · x1
[02(x1)] = 1 · x1
[24(x1)] = 1 · x1
[42(x1)] = 1 · x1
[21(x1)] = 1 · x1
[23(x1)] = 1 · x1
[22(x1)] = 1 · x1
[25(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[40(x1)] = 1 · x1
all of the following rules can be deleted.
30(05(52(20(x1)))) → 31(12(20(05(50(x1))))) (343)

1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1 + 1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[00(x1)] = 1 · x1
[13(x1)] = 1 · x1
[34(x1)] = 1 · x1
[32(x1)] = 1 · x1 + 1
[35(x1)] = 1 · x1
[30(x1)] = 1 · x1 + 1
[33(x1)] = 1 · x1
[14(x1)] = 1 · x1
[45(x1)] = 1 · x1
[51(x1)] = 1 · x1
[04(x1)] = 1 · x1
[41(x1)] = 1 · x1
[11(x1)] = 1 · x1
[15(x1)] = 1 · x1
[54(x1)] = 1 · x1
[52(x1)] = 1 · x1
[55(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1
[12(x1)] = 1 · x1
[24(x1)] = 1 · x1
[20(x1)] = 1 · x1 + 1
[42(x1)] = 1 · x1
[21(x1)] = 1 · x1
[23(x1)] = 1 · x1 + 1
[22(x1)] = 1 · x1
[25(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[40(x1)] = 1 · x1
all of the following rules can be deleted.
01(10(03(31(x1)))) → 00(00(01(13(31(x1))))) (345)
01(10(03(34(x1)))) → 00(00(01(13(34(x1))))) (346)
01(10(03(32(x1)))) → 00(00(01(13(32(x1))))) (347)
01(10(03(35(x1)))) → 00(00(01(13(35(x1))))) (348)
01(10(03(30(x1)))) → 00(00(01(13(30(x1))))) (349)
01(10(03(33(x1)))) → 00(00(01(13(33(x1))))) (350)

1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[01(x1)] = 1 · x1
[14(x1)] = 1 · x1
[45(x1)] = 1 · x1 + 1
[51(x1)] = 1 · x1
[04(x1)] = 1 · x1
[41(x1)] = 1 · x1
[11(x1)] = 1 · x1
[15(x1)] = 1 · x1
[54(x1)] = 1 · x1
[52(x1)] = 1 · x1
[55(x1)] = 1 · x1 + 1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1 + 1
[00(x1)] = 1 · x1
[33(x1)] = 1 · x1
[12(x1)] = 1 · x1
[24(x1)] = 1 · x1
[20(x1)] = 1 · x1
[42(x1)] = 1 · x1
[32(x1)] = 1 · x1
[21(x1)] = 1 · x1
[23(x1)] = 1 · x1
[22(x1)] = 1 · x1
[25(x1)] = 1 · x1
[34(x1)] = 1 · x1
[35(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[40(x1)] = 1 · x1
all of the following rules can be deleted.
01(14(45(51(x1)))) → 04(41(11(15(51(x1))))) (471)
01(14(45(54(x1)))) → 04(41(11(15(54(x1))))) (472)
01(14(45(52(x1)))) → 04(41(11(15(52(x1))))) (473)
01(14(45(55(x1)))) → 04(41(11(15(55(x1))))) (474)
01(14(45(50(x1)))) → 04(41(11(15(50(x1))))) (475)
01(14(45(53(x1)))) → 04(41(11(15(53(x1))))) (476)

1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1 + 1
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1 + 1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[04(x1)] = 1 · x1
[02(x1)] = 1 · x1 + 1
[05(x1)] = 1 · x1
[00(x1)] = 1 · x1
[33(x1)] = 1 · x1
[12(x1)] = 1 · x1
[24(x1)] = 1 · x1
[41(x1)] = 1 · x1
[14(x1)] = 1 · x1
[20(x1)] = 1 · x1
[52(x1)] = 1 · x1
[54(x1)] = 1 · x1
[45(x1)] = 1 · x1
[51(x1)] = 1 · x1
[55(x1)] = 1 · x1
[42(x1)] = 1 · x1
[32(x1)] = 1 · x1 + 1
[21(x1)] = 1 · x1
[23(x1)] = 1 · x1
[22(x1)] = 1 · x1
[25(x1)] = 1 · x1
[34(x1)] = 1 · x1
[35(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[40(x1)] = 1 · x1
[15(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
12(24(41(10(01(x1))))) → 14(41(12(20(00(01(x1)))))) (651)
12(24(41(10(04(x1))))) → 14(41(12(20(00(04(x1)))))) (652)
12(24(41(10(02(x1))))) → 14(41(12(20(00(02(x1)))))) (653)
12(24(41(10(05(x1))))) → 14(41(12(20(00(05(x1)))))) (654)
12(24(41(10(00(x1))))) → 14(41(12(20(00(00(x1)))))) (655)
12(24(41(10(03(x1))))) → 14(41(12(20(00(03(x1)))))) (656)
52(24(41(10(01(x1))))) → 54(41(12(20(00(01(x1)))))) (675)
52(24(41(10(04(x1))))) → 54(41(12(20(00(04(x1)))))) (676)
52(24(41(10(02(x1))))) → 54(41(12(20(00(02(x1)))))) (677)
52(24(41(10(05(x1))))) → 54(41(12(20(00(05(x1)))))) (678)
52(24(41(10(00(x1))))) → 54(41(12(20(00(00(x1)))))) (679)
52(24(41(10(03(x1))))) → 54(41(12(20(00(03(x1)))))) (680)

1.1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[04(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1 + 1
[00(x1)] = 1 · x1
[33(x1)] = 1 · x1
[54(x1)] = 1 · x1
[41(x1)] = 1 · x1
[45(x1)] = 1 · x1
[51(x1)] = 1 · x1
[55(x1)] = 1 · x1
[42(x1)] = 1 · x1
[20(x1)] = 1 · x1
[32(x1)] = 1 · x1
[21(x1)] = 1 · x1
[12(x1)] = 1 · x1
[23(x1)] = 1 · x1
[24(x1)] = 1 · x1
[22(x1)] = 1 · x1
[25(x1)] = 1 · x1
[34(x1)] = 1 · x1
[35(x1)] = 1 · x1
[14(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[40(x1)] = 1 · x1
[52(x1)] = 1 · x1
[15(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
05(54(41(10(01(x1))))) → 04(45(51(11(10(01(x1)))))) (729)
05(54(41(10(04(x1))))) → 04(45(51(11(10(04(x1)))))) (730)
05(54(41(10(02(x1))))) → 04(45(51(11(10(02(x1)))))) (731)
05(54(41(10(05(x1))))) → 04(45(51(11(10(05(x1)))))) (732)
05(54(41(10(00(x1))))) → 04(45(51(11(10(00(x1)))))) (733)
05(54(41(10(03(x1))))) → 04(45(51(11(10(03(x1)))))) (734)

1.1.1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[04(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1
[00(x1)] = 1 · x1
[33(x1)] = 1 · x1
[55(x1)] = 1 · x1 + 1
[54(x1)] = 1 · x1
[41(x1)] = 1 · x1
[45(x1)] = 1 · x1
[51(x1)] = 1 · x1
[42(x1)] = 1 · x1
[20(x1)] = 1 · x1
[32(x1)] = 1 · x1
[21(x1)] = 1 · x1
[12(x1)] = 1 · x1
[23(x1)] = 1 · x1
[24(x1)] = 1 · x1
[22(x1)] = 1 · x1
[25(x1)] = 1 · x1
[34(x1)] = 1 · x1
[35(x1)] = 1 · x1
[14(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[40(x1)] = 1 · x1
[52(x1)] = 1 · x1
[15(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
55(54(41(10(01(x1))))) → 54(45(51(11(10(01(x1)))))) (747)
55(54(41(10(04(x1))))) → 54(45(51(11(10(04(x1)))))) (748)
55(54(41(10(02(x1))))) → 54(45(51(11(10(02(x1)))))) (749)
55(54(41(10(05(x1))))) → 54(45(51(11(10(05(x1)))))) (750)
55(54(41(10(00(x1))))) → 54(45(51(11(10(00(x1)))))) (751)
55(54(41(10(03(x1))))) → 54(45(51(11(10(03(x1)))))) (752)

1.1.1.1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[04(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1
[00(x1)] = 1 · x1
[33(x1)] = 1 · x1
[42(x1)] = 1 · x1 + 1
[20(x1)] = 1 · x1
[41(x1)] = 1 · x1
[32(x1)] = 1 · x1
[21(x1)] = 1 · x1
[12(x1)] = 1 · x1
[23(x1)] = 1 · x1
[24(x1)] = 1 · x1
[22(x1)] = 1 · x1
[25(x1)] = 1 · x1
[34(x1)] = 1 · x1
[35(x1)] = 1 · x1
[14(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[45(x1)] = 1 · x1
[40(x1)] = 1 · x1
[52(x1)] = 1 · x1
[54(x1)] = 1 · x1
[15(x1)] = 1 · x1
[51(x1)] = 1 · x1
[55(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
42(20(03(30(01(x1))))) → 41(13(32(20(00(01(x1)))))) (849)
42(20(03(30(04(x1))))) → 41(13(32(20(00(04(x1)))))) (850)
42(20(03(30(02(x1))))) → 41(13(32(20(00(02(x1)))))) (851)
42(20(03(30(05(x1))))) → 41(13(32(20(00(05(x1)))))) (852)
42(20(03(30(00(x1))))) → 41(13(32(20(00(00(x1)))))) (853)
42(20(03(30(03(x1))))) → 41(13(32(20(00(03(x1)))))) (854)

1.1.1.1.1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[04(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1
[00(x1)] = 1 · x1
[33(x1)] = 1 · x1
[32(x1)] = 1 · x1 + 1
[21(x1)] = 1 · x1
[12(x1)] = 1 · x1
[23(x1)] = 1 · x1
[24(x1)] = 1 · x1
[22(x1)] = 1 · x1
[25(x1)] = 1 · x1
[20(x1)] = 1 · x1
[34(x1)] = 1 · x1
[35(x1)] = 1 · x1
[41(x1)] = 1 · x1
[14(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[42(x1)] = 1 · x1
[45(x1)] = 1 · x1
[40(x1)] = 1 · x1
[52(x1)] = 1 · x1
[54(x1)] = 1 · x1
[15(x1)] = 1 · x1
[51(x1)] = 1 · x1
[55(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
03(32(21(12(21(x1))))) → 02(23(31(11(12(21(x1)))))) (873)
03(32(21(12(24(x1))))) → 02(23(31(11(12(24(x1)))))) (874)
03(32(21(12(22(x1))))) → 02(23(31(11(12(22(x1)))))) (875)
03(32(21(12(25(x1))))) → 02(23(31(11(12(25(x1)))))) (876)
03(32(21(12(20(x1))))) → 02(23(31(11(12(20(x1)))))) (877)
03(32(21(12(23(x1))))) → 02(23(31(11(12(23(x1)))))) (878)

1.1.1.1.1.1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[04(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1
[00(x1)] = 1 · x1
[33(x1)] = 1 · x1
[34(x1)] = 1 · x1
[32(x1)] = 1 · x1
[35(x1)] = 1 · x1
[41(x1)] = 1 · x1
[14(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[42(x1)] = 1 · x1
[45(x1)] = 1 · x1
[40(x1)] = 1 · x1
[12(x1)] = 1 · x1 + 1
[21(x1)] = 1 · x1 + 1
[24(x1)] = 1 · x1
[52(x1)] = 1 · x1
[54(x1)] = 1 · x1
[15(x1)] = 1 · x1
[51(x1)] = 1 · x1
[55(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
12(21(14(44(41(x1))))) → 14(41(11(12(24(41(x1)))))) (1047)
12(21(14(44(44(x1))))) → 14(41(11(12(24(44(x1)))))) (1048)
12(21(14(44(42(x1))))) → 14(41(11(12(24(42(x1)))))) (1049)
12(21(14(44(45(x1))))) → 14(41(11(12(24(45(x1)))))) (1050)
12(21(14(44(40(x1))))) → 14(41(11(12(24(40(x1)))))) (1051)
12(21(14(44(43(x1))))) → 14(41(11(12(24(43(x1)))))) (1052)

1.1.1.1.1.1.1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[04(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1
[00(x1)] = 1 · x1
[33(x1)] = 1 · x1
[34(x1)] = 1 · x1
[32(x1)] = 1 · x1
[35(x1)] = 1 · x1
[41(x1)] = 1 · x1
[14(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[42(x1)] = 1 · x1
[45(x1)] = 1 · x1
[40(x1)] = 1 · x1
[52(x1)] = 1 · x1 + 1
[21(x1)] = 1 · x1
[54(x1)] = 1 · x1
[12(x1)] = 1 · x1
[24(x1)] = 1 · x1
[15(x1)] = 1 · x1
[51(x1)] = 1 · x1
[55(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
52(21(14(44(41(x1))))) → 54(41(11(12(24(41(x1)))))) (1071)
52(21(14(44(44(x1))))) → 54(41(11(12(24(44(x1)))))) (1072)
52(21(14(44(42(x1))))) → 54(41(11(12(24(42(x1)))))) (1073)
52(21(14(44(45(x1))))) → 54(41(11(12(24(45(x1)))))) (1074)
52(21(14(44(40(x1))))) → 54(41(11(12(24(40(x1)))))) (1075)
52(21(14(44(43(x1))))) → 54(41(11(12(24(43(x1)))))) (1076)

1.1.1.1.1.1.1.1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1 + 1
[01(x1)] = 1 · x1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[04(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1
[00(x1)] = 1 · x1
[33(x1)] = 1 · x1
[34(x1)] = 1 · x1
[32(x1)] = 1 · x1
[35(x1)] = 1 · x1
[41(x1)] = 1 · x1
[14(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[42(x1)] = 1 · x1
[45(x1)] = 1 · x1
[40(x1)] = 1 · x1
[15(x1)] = 1 · x1
[51(x1)] = 1 · x1
[54(x1)] = 1 · x1
[52(x1)] = 1 · x1
[55(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
13(30(01(10(01(x1))))) → 10(03(31(11(10(01(x1)))))) (579)
13(30(01(10(04(x1))))) → 10(03(31(11(10(04(x1)))))) (580)
13(30(01(10(02(x1))))) → 10(03(31(11(10(02(x1)))))) (581)
13(30(01(10(05(x1))))) → 10(03(31(11(10(05(x1)))))) (582)
13(30(01(10(00(x1))))) → 10(03(31(11(10(00(x1)))))) (583)
13(30(01(10(03(x1))))) → 10(03(31(11(10(03(x1)))))) (584)
13(30(01(13(31(x1))))) → 10(03(31(11(13(31(x1)))))) (939)
13(30(01(13(34(x1))))) → 10(03(31(11(13(34(x1)))))) (940)
13(30(01(13(32(x1))))) → 10(03(31(11(13(32(x1)))))) (941)
13(30(01(13(35(x1))))) → 10(03(31(11(13(35(x1)))))) (942)
13(30(01(13(30(x1))))) → 10(03(31(11(13(30(x1)))))) (943)
13(30(01(13(33(x1))))) → 10(03(31(11(13(33(x1)))))) (944)
13(30(01(15(51(x1))))) → 10(03(31(11(15(51(x1)))))) (1083)
13(30(01(15(54(x1))))) → 10(03(31(11(15(54(x1)))))) (1084)
13(30(01(15(52(x1))))) → 10(03(31(11(15(52(x1)))))) (1085)
13(30(01(15(55(x1))))) → 10(03(31(11(15(55(x1)))))) (1086)
13(30(01(15(50(x1))))) → 10(03(31(11(15(50(x1)))))) (1087)
13(30(01(15(53(x1))))) → 10(03(31(11(15(53(x1)))))) (1088)

1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[33(x1)] = 1 · x1
[30(x1)] = 1 · x1
[01(x1)] = 1 · x1 + 1
[10(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[04(x1)] = 1 · x1
[02(x1)] = 1 · x1
[05(x1)] = 1 · x1
[00(x1)] = 1 · x1
[13(x1)] = 1 · x1
[34(x1)] = 1 · x1
[32(x1)] = 1 · x1
[35(x1)] = 1 · x1
[41(x1)] = 1 · x1
[14(x1)] = 1 · x1
[43(x1)] = 1 · x1
[44(x1)] = 1 · x1
[42(x1)] = 1 · x1
[45(x1)] = 1 · x1
[40(x1)] = 1 · x1
[15(x1)] = 1 · x1
[51(x1)] = 1 · x1
[54(x1)] = 1 · x1
[52(x1)] = 1 · x1
[55(x1)] = 1 · x1
[50(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
33(30(01(10(01(x1))))) → 30(03(31(11(10(01(x1)))))) (591)
33(30(01(10(04(x1))))) → 30(03(31(11(10(04(x1)))))) (592)
33(30(01(10(02(x1))))) → 30(03(31(11(10(02(x1)))))) (593)
33(30(01(10(05(x1))))) → 30(03(31(11(10(05(x1)))))) (594)
33(30(01(10(00(x1))))) → 30(03(31(11(10(00(x1)))))) (595)
33(30(01(10(03(x1))))) → 30(03(31(11(10(03(x1)))))) (596)
33(30(01(13(31(x1))))) → 30(03(31(11(13(31(x1)))))) (951)
33(30(01(13(34(x1))))) → 30(03(31(11(13(34(x1)))))) (952)
33(30(01(13(32(x1))))) → 30(03(31(11(13(32(x1)))))) (953)
33(30(01(13(35(x1))))) → 30(03(31(11(13(35(x1)))))) (954)
33(30(01(13(30(x1))))) → 30(03(31(11(13(30(x1)))))) (955)
33(30(01(13(33(x1))))) → 30(03(31(11(13(33(x1)))))) (956)
33(30(01(15(51(x1))))) → 30(03(31(11(15(51(x1)))))) (1095)
33(30(01(15(54(x1))))) → 30(03(31(11(15(54(x1)))))) (1096)
33(30(01(15(52(x1))))) → 30(03(31(11(15(52(x1)))))) (1097)
33(30(01(15(55(x1))))) → 30(03(31(11(15(55(x1)))))) (1098)
33(30(01(15(50(x1))))) → 30(03(31(11(15(50(x1)))))) (1099)
33(30(01(15(53(x1))))) → 30(03(31(11(15(53(x1)))))) (1100)

1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[13(x1)] = 1 · x1
[34(x1)] = 1 · x1 + 1
[41(x1)] = 1 · x1
[14(x1)] = 1 · x1
[43(x1)] = 1 · x1
[31(x1)] = 1 · x1
[11(x1)] = 1 · x1
[44(x1)] = 1 · x1
[42(x1)] = 1 · x1
[45(x1)] = 1 · x1
[40(x1)] = 1 · x1
[15(x1)] = 1 · x1
[53(x1)] = 1 · x1
all of the following rules can be deleted.
13(34(41(14(41(x1))))) → 14(43(31(11(14(41(x1)))))) (1011)
13(34(41(14(44(x1))))) → 14(43(31(11(14(44(x1)))))) (1012)
13(34(41(14(42(x1))))) → 14(43(31(11(14(42(x1)))))) (1013)
13(34(41(14(45(x1))))) → 14(43(31(11(14(45(x1)))))) (1014)
13(34(41(14(40(x1))))) → 14(43(31(11(14(40(x1)))))) (1015)
13(34(41(14(43(x1))))) → 14(43(31(11(14(43(x1)))))) (1016)
13(34(41(15(53(x1))))) → 15(53(31(11(14(43(x1)))))) (1124)

1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1 R is empty

There are no rules in the TRS. Hence, it is terminating.