Certification Problem

Input (TPDB SRS_Standard/Zantema_04/z092)

The rewrite relation of the following TRS is considered.

q0(0(x1)) → 0'(q1(x1)) (1)
q1(0(x1)) → 0(q1(x1)) (2)
q1(1'(x1)) → 1'(q1(x1)) (3)
0(q1(1(x1))) → q2(0(1'(x1))) (4)
0'(q1(1(x1))) → q2(0'(1'(x1))) (5)
1'(q1(1(x1))) → q2(1'(1'(x1))) (6)
0(q2(0(x1))) → q2(0(0(x1))) (7)
0'(q2(0(x1))) → q2(0'(0(x1))) (8)
1'(q2(0(x1))) → q2(1'(0(x1))) (9)
0(q2(1'(x1))) → q2(0(1'(x1))) (10)
0'(q2(1'(x1))) → q2(0'(1'(x1))) (11)
1'(q2(1'(x1))) → q2(1'(1'(x1))) (12)
q2(0'(x1)) → 0'(q0(x1)) (13)
q0(1'(x1)) → 1'(q3(x1)) (14)
q3(1'(x1)) → 1'(q3(x1)) (15)
q3(b(x1)) → b(q4(x1)) (16)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by NaTT @ termCOMP 2023)

1 Dependency Pair Transformation

The following set of initial dependency pairs has been identified.
q1#(0(x1)) → q1#(x1) (17)
q3#(1'(x1)) → 1'#(q3(x1)) (18)
q2#(0'(x1)) → 0'#(q0(x1)) (19)
1'#(q2(1'(x1))) → 1'#(1'(x1)) (20)
1'#(q2(0(x1))) → 1'#(0(x1)) (21)
0'#(q2(1'(x1))) → 0'#(1'(x1)) (22)
q1#(1'(x1)) → q1#(x1) (23)
q1#(1'(x1)) → 1'#(q1(x1)) (24)
1'#(q2(1'(x1))) → q2#(1'(1'(x1))) (25)
0#(q1(1(x1))) → q2#(0(1'(x1))) (26)
q0#(1'(x1)) → 1'#(q3(x1)) (27)
q3#(1'(x1)) → q3#(x1) (28)
q0#(0(x1)) → 0'#(q1(x1)) (29)
0'#(q1(1(x1))) → q2#(0'(1'(x1))) (30)
q2#(0'(x1)) → q0#(x1) (31)
0'#(q2(1'(x1))) → q2#(0'(1'(x1))) (32)
0#(q1(1(x1))) → 1'#(x1) (33)
1'#(q1(1(x1))) → 1'#(x1) (34)
0'#(q2(0(x1))) → 0'#(0(x1)) (35)
0'#(q1(1(x1))) → 1'#(x1) (36)
0'#(q2(0(x1))) → q2#(0'(0(x1))) (37)
0#(q2(0(x1))) → 0#(0(x1)) (38)
0#(q1(1(x1))) → 0#(1'(x1)) (39)
0#(q2(1'(x1))) → 0#(1'(x1)) (40)
q0#(0(x1)) → q1#(x1) (41)
0'#(q1(1(x1))) → 0'#(1'(x1)) (42)
0#(q2(0(x1))) → q2#(0(0(x1))) (43)
1'#(q1(1(x1))) → q2#(1'(1'(x1))) (44)
q1#(0(x1)) → 0#(q1(x1)) (45)
1'#(q2(0(x1))) → q2#(1'(0(x1))) (46)
q0#(1'(x1)) → q3#(x1) (47)
1'#(q1(1(x1))) → 1'#(1'(x1)) (48)
0#(q2(1'(x1))) → q2#(0(1'(x1))) (49)

1.1 Dependency Graph Processor

The dependency pairs are split into 1 component.