Certification Problem

Input (TPDB SRS_Standard/ICFP_2010/88156)

The rewrite relation of the following TRS is considered.

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

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by ttt2 @ termCOMP 2023)

1 String Reversal

Since only unary symbols occur, one can reverse all terms and obtains the TRS
1(1(0(2(1(0(3(0(2(1(1(0(0(x1))))))))))))) 0(1(0(0(0(1(0(0(2(2(0(2(0(0(3(0(0(x1))))))))))))))))) (31)
1(2(0(1(1(2(2(0(1(3(0(1(0(x1))))))))))))) 2(1(0(3(0(1(0(1(0(0(0(0(3(2(2(0(0(x1))))))))))))))))) (32)
2(1(3(0(2(1(3(1(0(0(1(1(0(x1))))))))))))) 0(2(2(1(0(0(0(0(2(0(3(1(0(2(0(2(0(x1))))))))))))))))) (33)
1(1(1(1(0(0(3(0(1(2(3(1(0(x1))))))))))))) 0(1(0(0(3(0(3(0(2(3(0(0(1(3(1(3(0(x1))))))))))))))))) (34)
1(3(1(1(3(2(3(2(0(2(0(2(0(x1))))))))))))) 0(1(2(2(0(0(3(2(3(0(3(0(0(3(1(0(0(x1))))))))))))))))) (35)
3(0(2(3(0(2(1(2(2(3(2(2(0(x1))))))))))))) 0(3(0(0(1(2(0(1(0(0(3(2(0(1(2(3(0(x1))))))))))))))))) (36)
3(2(1(1(2(2(3(2(2(0(3(2(0(x1))))))))))))) 2(1(1(0(2(0(3(1(0(2(0(2(3(2(0(0(1(x1))))))))))))))))) (37)
2(3(1(2(0(0(2(0(1(1(3(2(0(x1))))))))))))) 0(2(2(0(0(2(2(1(0(2(2(3(0(0(2(2(0(x1))))))))))))))))) (38)
3(1(3(0(2(0(1(3(2(2(3(2(0(x1))))))))))))) 3(2(2(0(2(0(2(2(0(0(1(1(2(0(3(0(0(x1))))))))))))))))) (39)
1(1(2(2(1(0(1(0(2(3(0(0(1(x1))))))))))))) 2(1(0(0(1(0(2(0(2(0(0(0(1(3(3(0(0(x1))))))))))))))))) (40)
2(2(1(1(1(0(1(1(2(0(3(0(1(x1))))))))))))) 3(3(3(3(3(0(0(0(3(0(0(2(0(0(2(3(0(x1))))))))))))))))) (41)
2(3(2(3(1(0(0(2(2(0(2(1(1(x1))))))))))))) 1(0(0(2(3(0(0(1(0(3(2(1(0(0(0(0(2(x1))))))))))))))))) (42)
1(0(2(2(1(0(0(2(2(1(2(2(1(x1))))))))))))) 3(0(1(0(2(0(2(3(0(2(2(1(0(0(3(0(0(x1))))))))))))))))) (43)
0(1(1(1(0(0(1(2(0(1(3(2(1(x1))))))))))))) 0(3(1(0(1(0(0(0(3(0(2(1(0(1(0(3(0(x1))))))))))))))))) (44)
3(2(0(1(2(2(2(2(3(0(0(3(1(x1))))))))))))) 0(0(2(1(3(2(0(3(0(2(3(0(2(2(0(0(3(x1))))))))))))))))) (45)
0(1(3(1(0(2(1(3(1(0(1(3(1(x1))))))))))))) 0(0(0(0(3(0(1(3(3(0(0(3(1(3(0(2(1(x1))))))))))))))))) (46)
0(3(2(0(0(1(0(0(3(1(1(3(1(x1))))))))))))) 0(3(1(1(0(2(0(0(0(0(2(3(0(2(0(1(2(x1))))))))))))))))) (47)
1(0(0(3(1(0(2(0(1(3(1(3(1(x1))))))))))))) 1(0(3(3(3(1(0(0(2(0(0(1(0(0(0(2(2(x1))))))))))))))))) (48)
0(0(3(1(0(3(0(1(0(1(2(3(1(x1))))))))))))) 0(0(1(0(1(2(3(2(0(0(3(0(0(0(1(3(0(x1))))))))))))))))) (49)
1(1(0(0(2(3(0(3(2(0(3(3(1(x1))))))))))))) 1(3(2(0(1(0(0(0(2(0(0(3(0(3(0(2(3(x1))))))))))))))))) (50)
0(3(2(0(2(2(3(2(2(2(3(3(1(x1))))))))))))) 0(0(2(1(3(2(2(0(1(2(2(0(2(2(3(0(3(x1))))))))))))))))) (51)
0(1(2(2(2(2(3(2(2(1(2(0(2(x1))))))))))))) 0(3(2(0(0(1(3(0(2(0(0(1(0(0(0(0(1(x1))))))))))))))))) (52)
2(1(1(0(2(3(2(2(1(2(2(0(2(x1))))))))))))) 0(1(2(2(1(0(0(0(0(0(0(1(3(1(3(2(0(x1))))))))))))))))) (53)
1(0(1(2(0(0(2(2(1(3(3(0(2(x1))))))))))))) 2(0(1(2(0(0(0(1(3(0(2(0(0(1(0(2(3(x1))))))))))))))))) (54)
3(1(3(0(0(2(1(2(3(0(1(1(2(x1))))))))))))) 3(3(1(2(2(0(0(2(2(0(0(0(0(1(0(2(2(x1))))))))))))))))) (55)
3(2(1(2(3(3(0(1(0(1(0(2(2(x1))))))))))))) 0(0(0(1(2(1(2(2(0(2(1(0(2(1(0(3(0(x1))))))))))))))))) (56)
3(0(3(0(2(3(3(2(0(0(0(3(2(x1))))))))))))) 0(2(3(0(2(0(3(0(0(0(2(1(0(0(0(2(2(x1))))))))))))))))) (57)
3(2(3(2(3(0(2(0(2(2(0(3(2(x1))))))))))))) 2(0(0(2(0(0(3(0(0(3(3(0(2(3(0(0(1(x1))))))))))))))))) (58)
3(3(3(0(2(0(2(1(3(1(0(0(3(x1))))))))))))) 3(1(0(0(2(2(2(0(3(0(0(2(1(0(1(0(0(x1))))))))))))))))) (59)
0(3(3(2(2(0(3(1(0(2(2(2(3(x1))))))))))))) 0(0(1(0(0(1(1(2(1(0(3(0(0(1(0(1(1(x1))))))))))))))))) (60)

1.1 Bounds

The given TRS is match-(raise)-bounded by 1. This is shown by the following automaton. The automaton is closed under rewriting as it is compatible.