Certification Problem

Input (TPDB SRS_Standard/Zantema_06/18)

The rewrite relation of the following TRS is considered.

a(a(x1)) → b(a(b(x1))) (1)
a(a(a(x1))) → a(b(a(b(a(x1))))) (2)
a(b(a(x1))) → b(b(a(b(b(x1))))) (3)
a(a(a(a(x1)))) → a(a(b(a(b(a(a(x1))))))) (4)
a(a(b(a(x1)))) → a(b(b(a(b(a(b(x1))))))) (5)
a(b(a(a(x1)))) → b(a(b(a(b(b(a(x1))))))) (6)
a(b(b(a(x1)))) → b(b(b(a(b(b(b(x1))))))) (7)
a(a(a(a(a(x1))))) → a(a(a(b(a(b(a(a(a(x1))))))))) (8)
a(a(a(b(a(x1))))) → a(a(b(b(a(b(a(a(b(x1))))))))) (9)
a(a(b(a(a(x1))))) → a(b(a(b(a(b(a(b(a(x1))))))))) (10)
a(a(b(b(a(x1))))) → a(b(b(b(a(b(a(b(b(x1))))))))) (11)
a(b(a(a(a(x1))))) → b(a(a(b(a(b(b(a(a(x1))))))))) (12)
a(b(a(b(a(x1))))) → b(a(b(b(a(b(b(a(b(x1))))))))) (13)
a(b(b(a(a(x1))))) → b(b(a(b(a(b(b(b(a(x1))))))))) (14)
a(b(b(b(a(x1))))) → b(b(b(b(a(b(b(b(b(x1))))))))) (15)

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.
a#(a(a(x1))) → a#(b(a(x1))) (16)
a#(b(a(x1))) → a#(b(b(x1))) (17)
a#(b(b(b(a(x1))))) → a#(b(b(b(b(x1))))) (18)
a#(a(a(a(x1)))) → a#(b(a(b(a(a(x1)))))) (19)
a#(a(a(a(x1)))) → a#(b(a(a(x1)))) (20)
a#(b(a(b(a(x1))))) → a#(b(b(a(b(x1))))) (21)
a#(a(b(b(a(x1))))) → a#(b(b(b(a(b(a(b(b(x1))))))))) (22)
a#(a(a(b(a(x1))))) → a#(b(b(a(b(a(a(b(x1)))))))) (23)
a#(a(a(b(a(x1))))) → a#(a(b(x1))) (24)
a#(a(b(a(a(x1))))) → a#(b(a(b(a(x1))))) (25)
a#(a(b(a(a(x1))))) → a#(b(a(b(a(b(a(x1))))))) (26)
a#(a(a(b(a(x1))))) → a#(b(x1)) (27)
a#(a(a(a(a(x1))))) → a#(a(a(b(a(b(a(a(a(x1))))))))) (28)
a#(a(b(b(a(x1))))) → a#(b(a(b(b(x1))))) (29)
a#(a(x1)) → a#(b(x1)) (30)
a#(a(b(a(a(x1))))) → a#(b(a(x1))) (31)
a#(b(b(a(a(x1))))) → a#(b(b(b(a(x1))))) (32)
a#(b(a(b(a(x1))))) → a#(b(x1)) (33)
a#(a(a(b(a(x1))))) → a#(b(a(a(b(x1))))) (34)
a#(a(a(a(a(x1))))) → a#(b(a(b(a(a(a(x1))))))) (35)
a#(b(a(b(a(x1))))) → a#(b(b(a(b(b(a(b(x1)))))))) (36)
a#(a(b(a(x1)))) → a#(b(x1)) (37)
a#(a(b(a(a(x1))))) → a#(b(a(b(a(b(a(b(a(x1))))))))) (38)
a#(a(a(a(a(x1))))) → a#(b(a(a(a(x1))))) (39)
a#(a(b(a(x1)))) → a#(b(a(b(x1)))) (40)
a#(b(a(a(a(x1))))) → a#(b(a(b(b(a(a(x1))))))) (41)
a#(a(a(a(a(x1))))) → a#(a(b(a(b(a(a(a(x1)))))))) (42)
a#(b(b(a(a(x1))))) → a#(b(a(b(b(b(a(x1))))))) (43)
a#(a(b(a(x1)))) → a#(b(b(a(b(a(b(x1))))))) (44)
a#(a(a(a(x1)))) → a#(a(b(a(b(a(a(x1))))))) (45)
a#(b(b(a(x1)))) → a#(b(b(b(x1)))) (46)
a#(b(a(a(a(x1))))) → a#(a(b(a(b(b(a(a(x1)))))))) (47)
a#(b(a(a(x1)))) → a#(b(a(b(b(a(x1)))))) (48)
a#(a(a(x1))) → a#(b(a(b(a(x1))))) (49)
a#(a(a(b(a(x1))))) → a#(a(b(b(a(b(a(a(b(x1))))))))) (50)
a#(a(b(b(a(x1))))) → a#(b(b(x1))) (51)
a#(b(a(a(x1)))) → a#(b(b(a(x1)))) (52)
a#(b(a(a(a(x1))))) → a#(b(b(a(a(x1))))) (53)

1.1 Dependency Graph Processor

The dependency pairs are split into 1 component.