Certification Problem

Input (TPDB SRS_Standard/Zantema_06/17)

The rewrite relation of the following TRS is considered.

a(a(x1)) → b(x1) (1)
a(a(a(x1))) → a(b(a(x1))) (2)
a(b(a(x1))) → b(b(b(x1))) (3)
a(a(a(a(x1)))) → a(a(b(a(a(x1))))) (4)
a(a(b(a(x1)))) → a(b(b(a(b(x1))))) (5)
a(b(a(a(x1)))) → b(a(b(b(a(x1))))) (6)
a(b(b(a(x1)))) → b(b(b(b(b(x1))))) (7)
a(a(a(a(a(x1))))) → a(a(a(b(a(a(a(x1))))))) (8)
a(a(a(b(a(x1))))) → a(a(b(b(a(a(b(x1))))))) (9)
a(a(b(a(a(x1))))) → a(b(a(b(a(b(a(x1))))))) (10)
a(a(b(b(a(x1))))) → a(b(b(b(a(b(b(x1))))))) (11)
a(b(a(a(a(x1))))) → b(a(a(b(b(a(a(x1))))))) (12)
a(b(a(b(a(x1))))) → b(a(b(b(b(a(b(x1))))))) (13)
a(b(b(a(a(x1))))) → b(b(a(b(b(b(a(x1))))))) (14)
a(b(b(b(a(x1))))) → b(b(b(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#(b(a(a(x1)))) → a#(b(b(a(x1)))) (16)
a#(a(a(b(a(x1))))) → a#(b(b(a(a(b(x1)))))) (17)
a#(b(b(a(a(x1))))) → a#(b(b(b(a(x1))))) (18)
a#(a(b(b(a(x1))))) → a#(b(b(b(a(b(b(x1))))))) (19)
a#(b(a(a(a(x1))))) → a#(a(b(b(a(a(x1)))))) (20)
a#(a(a(a(x1)))) → a#(b(a(a(x1)))) (21)
a#(b(a(a(a(x1))))) → a#(b(b(a(a(x1))))) (22)
a#(a(b(a(a(x1))))) → a#(b(a(b(a(b(a(x1))))))) (23)
a#(a(a(a(a(x1))))) → a#(a(b(a(a(a(x1)))))) (24)
a#(a(a(b(a(x1))))) → a#(a(b(x1))) (25)
a#(a(b(b(a(x1))))) → a#(b(b(x1))) (26)
a#(a(a(b(a(x1))))) → a#(a(b(b(a(a(b(x1))))))) (27)
a#(a(a(a(x1)))) → a#(a(b(a(a(x1))))) (28)
a#(a(b(a(x1)))) → a#(b(b(a(b(x1))))) (29)
a#(a(a(a(a(x1))))) → a#(a(a(b(a(a(a(x1))))))) (30)
a#(a(a(a(a(x1))))) → a#(b(a(a(a(x1))))) (31)
a#(a(b(a(a(x1))))) → a#(b(a(x1))) (32)
a#(b(a(b(a(x1))))) → a#(b(b(b(a(b(x1)))))) (33)
a#(a(a(x1))) → a#(b(a(x1))) (34)
a#(a(a(b(a(x1))))) → a#(b(x1)) (35)
a#(a(b(a(a(x1))))) → a#(b(a(b(a(x1))))) (36)
a#(b(a(b(a(x1))))) → a#(b(x1)) (37)
a#(a(b(a(x1)))) → a#(b(x1)) (38)

1.1 Dependency Graph Processor

The dependency pairs are split into 1 component.