Certification Problem

Input (TPDB SRS_Standard/Zantema_06/15)

The rewrite relation of the following TRS is considered.

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

1.1 Dependency Graph Processor

The dependency pairs are split into 1 component.