Certification Problem

Input (TPDB SRS_Standard/Zantema_04/z100)

The rewrite relation of the following TRS is considered.

r1(a(x1)) → a(a(a(r1(x1)))) (1)
r2(a(x1)) → a(a(a(r2(x1)))) (2)
a(l1(x1)) → l1(a(a(a(x1)))) (3)
a(a(l2(x1))) → l2(a(a(x1))) (4)
r1(b(x1)) → l1(b(x1)) (5)
r2(b(x1)) → l2(a(b(x1))) (6)
b(l1(x1)) → b(r2(x1)) (7)
b(l2(x1)) → b(r1(x1)) (8)
a(a(x1)) → x1 (9)

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.
r2#(a(x1)) → a#(a(r2(x1))) (10)
b#(l1(x1)) → b#(r2(x1)) (11)
r1#(a(x1)) → a#(r1(x1)) (12)
a#(l1(x1)) → a#(a(x1)) (13)
r1#(a(x1)) → a#(a(a(r1(x1)))) (14)
r1#(a(x1)) → a#(a(r1(x1))) (15)
r1#(a(x1)) → r1#(x1) (16)
b#(l1(x1)) → r2#(x1) (17)
a#(l1(x1)) → a#(x1) (18)
r2#(b(x1)) → a#(b(x1)) (19)
a#(a(l2(x1))) → a#(a(x1)) (20)
b#(l2(x1)) → r1#(x1) (21)
r2#(a(x1)) → a#(r2(x1)) (22)
r2#(a(x1)) → a#(a(a(r2(x1)))) (23)
a#(l1(x1)) → a#(a(a(x1))) (24)
b#(l2(x1)) → b#(r1(x1)) (25)
r2#(a(x1)) → r2#(x1) (26)
a#(a(l2(x1))) → a#(x1) (27)

1.1 Dependency Graph Processor

The dependency pairs are split into 4 components.