Certification Problem

Input (TPDB SRS_Standard/ICFP_2010/88143)

The rewrite relation of the following TRS is considered.

0(0(0(1(1(1(2(3(3(1(3(3(2(x1))))))))))))) → 0(2(2(1(0(1(2(3(0(0(3(2(2(3(1(2(2(x1))))))))))))))))) (1)
0(0(0(3(3(1(1(1(3(3(1(3(2(x1))))))))))))) → 3(0(2(1(0(3(3(3(1(2(2(2(1(2(1(2(2(x1))))))))))))))))) (2)
0(0(2(0(3(1(3(2(1(0(0(2(3(x1))))))))))))) → 0(2(2(2(1(3(3(3(2(2(0(3(1(3(2(1(2(x1))))))))))))))))) (3)
0(1(0(0(3(3(2(1(2(0(1(2(3(x1))))))))))))) → 3(2(2(1(2(2(0(3(0(2(2(2(1(2(2(3(1(x1))))))))))))))))) (4)
0(1(2(0(1(1(0(2(2(1(2(0(2(x1))))))))))))) → 2(0(3(3(2(2(1(0(3(3(3(3(2(2(2(3(3(x1))))))))))))))))) (5)
0(1(2(1(1(1(2(2(0(1(3(2(0(x1))))))))))))) → 2(3(2(0(1(2(3(0(3(3(2(1(3(3(1(3(3(x1))))))))))))))))) (6)
0(2(2(0(0(3(1(0(3(2(1(3(0(x1))))))))))))) → 3(1(2(2(1(3(3(2(2(3(0(2(2(1(1(1(0(x1))))))))))))))))) (7)
0(2(3(3(1(0(3(3(0(2(3(1(1(x1))))))))))))) → 2(1(3(2(2(2(0(2(2(2(3(3(2(2(2(0(3(x1))))))))))))))))) (8)
0(3(0(3(0(2(3(0(0(3(1(2(1(x1))))))))))))) → 3(1(1(2(2(3(0(1(2(2(2(2(3(2(2(2(0(x1))))))))))))))))) (9)
0(3(0(3(1(0(1(2(2(0(3(1(3(x1))))))))))))) → 2(3(2(2(3(0(3(0(3(3(2(2(1(2(2(0(3(x1))))))))))))))))) (10)
1(0(0(1(2(2(2(3(2(3(2(0(1(x1))))))))))))) → 1(2(1(0(2(2(1(2(1(0(3(3(2(2(2(3(3(x1))))))))))))))))) (11)
1(0(2(3(0(3(2(3(2(2(3(2(3(x1))))))))))))) → 1(3(2(2(1(2(2(2(3(3(2(2(3(1(2(1(2(x1))))))))))))))))) (12)
1(3(1(0(1(1(3(2(2(1(1(2(1(x1))))))))))))) → 1(2(3(2(3(2(1(2(2(2(2(2(2(0(1(2(2(x1))))))))))))))))) (13)
2(0(0(1(3(0(3(1(3(0(1(2(1(x1))))))))))))) → 2(2(3(3(0(1(0(0(3(3(3(1(0(2(2(1(2(x1))))))))))))))))) (14)
2(0(0(2(3(0(3(1(0(0(2(1(3(x1))))))))))))) → 2(0(2(1(2(2(2(2(3(2(3(1(3(3(1(3(1(x1))))))))))))))))) (15)
2(1(0(2(2(0(0(1(3(2(0(3(3(x1))))))))))))) → 2(0(2(2(1(3(2(1(1(1(2(2(1(3(3(3(3(x1))))))))))))))))) (16)
2(1(0(3(0(3(0(3(3(0(2(1(1(x1))))))))))))) → 2(2(0(1(2(1(1(0(2(2(2(3(2(3(0(2(2(x1))))))))))))))))) (17)
2(1(1(2(0(1(1(3(0(2(3(0(1(x1))))))))))))) → 2(2(3(3(3(3(3(2(1(0(1(2(2(3(3(2(2(x1))))))))))))))))) (18)
2(1(1(3(3(0(3(2(3(2(1(1(3(x1))))))))))))) → 2(3(2(3(2(2(3(3(2(1(2(2(3(3(0(1(3(x1))))))))))))))))) (19)
2(1(1(3(3(3(0(3(0(3(0(0(2(x1))))))))))))) → 2(0(2(2(0(2(1(3(3(3(2(3(3(2(3(3(2(x1))))))))))))))))) (20)
2(2(0(0(1(0(2(3(0(3(0(1(0(x1))))))))))))) → 2(2(2(1(0(2(0(1(3(1(3(0(3(3(3(3(2(x1))))))))))))))))) (21)
2(2(0(0(3(0(2(2(3(0(1(3(3(x1))))))))))))) → 2(2(1(1(0(1(2(1(2(0(2(2(2(0(2(2(2(x1))))))))))))))))) (22)
2(2(0(3(0(1(0(2(3(2(3(1(2(x1))))))))))))) → 2(2(0(2(2(2(1(0(0(3(1(3(1(3(3(2(2(x1))))))))))))))))) (23)
2(2(1(0(2(1(2(1(1(0(1(2(0(x1))))))))))))) → 2(2(0(2(0(3(1(2(2(0(1(2(2(2(2(2(2(x1))))))))))))))))) (24)
2(3(1(1(0(2(3(1(2(3(3(1(1(x1))))))))))))) → 2(2(2(1(2(1(1(2(0(2(0(0(3(0(1(3(3(x1))))))))))))))))) (25)
2(3(2(0(3(0(1(3(2(2(2(0(2(x1))))))))))))) → 2(1(2(2(3(0(0(1(3(2(2(3(2(2(3(3(2(x1))))))))))))))))) (26)
2(3(2(1(1(1(3(2(3(2(3(2(1(x1))))))))))))) → 2(2(2(0(3(2(2(0(2(3(2(3(0(2(2(0(2(x1))))))))))))))))) (27)
3(0(2(3(0(1(0(3(3(0(0(1(0(x1))))))))))))) → 3(0(0(1(2(2(3(3(3(2(0(1(2(0(3(3(2(x1))))))))))))))))) (28)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by AProVE @ termCOMP 2023)

1 Closure Under Flat Contexts

Using the flat contexts

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

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

1.1 Semantic Labeling

Root-labeling is applied.

We obtain the labeled TRS

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

1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[00(x1)] = 1 · x1 + 68
[01(x1)] = 1 · x1 + 49
[11(x1)] = 1 · x1 + 100
[12(x1)] = 1 · x1
[23(x1)] = 1 · x1 + 45
[33(x1)] = 1 · x1 + 1
[31(x1)] = 1 · x1 + 10
[13(x1)] = 1 · x1 + 22
[32(x1)] = 1 · x1
[20(x1)] = 1 · x1 + 13
[02(x1)] = 1 · x1 + 35
[22(x1)] = 1 · x1
[21(x1)] = 1 · x1
[10(x1)] = 1 · x1
[30(x1)] = 1 · x1
[03(x1)] = 1 · x1 + 99
all of the following rules can be deleted.

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

1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[20(x1)] = 1 · x1 + 1
[00(x1)] = 1 · x1 + 3
[01(x1)] = 1 · x1
[13(x1)] = 1 · x1
[30(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[12(x1)] = 1 · x1
[21(x1)] = 1 · x1
[22(x1)] = 1 · x1
[23(x1)] = 1 · x1
[33(x1)] = 1 · x1
[10(x1)] = 1 · x1
[02(x1)] = 1 · x1
[11(x1)] = 1 · x1 + 3
[32(x1)] = 1 · x1
all of the following rules can be deleted.
20(00(01(13(30(03(31(13(30(01(12(21(13(x1))))))))))))) → 22(23(33(30(01(10(00(03(33(33(31(10(02(22(21(12(23(x1))))))))))))))))) (84)
22(21(10(02(21(12(21(11(10(01(12(20(02(x1))))))))))))) → 22(20(02(20(03(31(12(22(20(01(12(22(22(22(22(22(22(x1))))))))))))))))) (123)
20(01(10(00(03(33(32(21(12(20(01(12(23(31(x1)))))))))))))) → 23(32(22(21(12(22(20(03(30(02(22(22(21(12(22(23(31(11(x1)))))))))))))))))) (166)

1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[10(x1)] = 1 · x1 + 1
[03(x1)] = 1 · x1
[30(x1)] = 1 · x1
[31(x1)] = 1 · x1
[01(x1)] = 1 · x1
[12(x1)] = 1 · x1
[22(x1)] = 1 · x1
[20(x1)] = 1 · x1
[13(x1)] = 1 · x1
[23(x1)] = 1 · x1
[32(x1)] = 1 · x1
[33(x1)] = 1 · x1 + 1
[21(x1)] = 1 · x1
all of the following rules can be deleted.
10(03(30(03(31(10(01(12(22(20(03(31(13(30(x1)))))))))))))) → 12(23(32(22(23(30(03(30(03(33(32(22(21(12(22(20(03(30(x1)))))))))))))))))) (257)
10(03(30(03(31(10(01(12(22(20(03(31(13(31(x1)))))))))))))) → 12(23(32(22(23(30(03(30(03(33(32(22(21(12(22(20(03(31(x1)))))))))))))))))) (258)
10(03(30(03(31(10(01(12(22(20(03(31(13(32(x1)))))))))))))) → 12(23(32(22(23(30(03(30(03(33(32(22(21(12(22(20(03(32(x1)))))))))))))))))) (259)
10(03(30(03(31(10(01(12(22(20(03(31(13(33(x1)))))))))))))) → 12(23(32(22(23(30(03(30(03(33(32(22(21(12(22(20(03(33(x1)))))))))))))))))) (260)

1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[30(x1)] = 1 · x1
[03(x1)] = 1 · x1
[31(x1)] = 1 · x1
[10(x1)] = 1 · x1 + 1
[01(x1)] = 1 · x1
[12(x1)] = 1 · x1
[22(x1)] = 1 · x1
[20(x1)] = 1 · x1
[13(x1)] = 1 · x1
[32(x1)] = 1 · x1
[23(x1)] = 1 · x1
[33(x1)] = 1 · x1
[21(x1)] = 1 · x1
all of the following rules can be deleted.
30(03(30(03(31(10(01(12(22(20(03(31(13(30(x1)))))))))))))) → 32(23(32(22(23(30(03(30(03(33(32(22(21(12(22(20(03(30(x1)))))))))))))))))) (265)
30(03(30(03(31(10(01(12(22(20(03(31(13(31(x1)))))))))))))) → 32(23(32(22(23(30(03(30(03(33(32(22(21(12(22(20(03(31(x1)))))))))))))))))) (266)
30(03(30(03(31(10(01(12(22(20(03(31(13(32(x1)))))))))))))) → 32(23(32(22(23(30(03(30(03(33(32(22(21(12(22(20(03(32(x1)))))))))))))))))) (267)
30(03(30(03(31(10(01(12(22(20(03(31(13(33(x1)))))))))))))) → 32(23(32(22(23(30(03(30(03(33(32(22(21(12(22(20(03(33(x1)))))))))))))))))) (268)

1.1.1.1.1.1.1 R is empty

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