Certification Problem

Input (TPDB SRS_Standard/Secret_06_SRS/secr9)

The rewrite relation of the following TRS is considered.

a(c(x1)) → c(b(c(c(a(x1))))) (1)
b(b(b(x1))) → c(b(x1)) (2)
d(d(x1)) → d(b(d(b(d(x1))))) (3)
a(a(x1)) → a(d(a(x1))) (4)
a(b(x1)) → c(c(a(x1))) (5)
c(c(x1)) → c(b(c(b(c(x1))))) (6)
c(c(c(x1))) → c(b(b(x1))) (7)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by AProVE @ termCOMP 2023)

1 Dependency Pair Transformation

The following set of initial dependency pairs has been identified.
a#(c(x1)) → c#(b(c(c(a(x1))))) (8)
a#(c(x1)) → b#(c(c(a(x1)))) (9)
a#(c(x1)) → c#(c(a(x1))) (10)
a#(c(x1)) → c#(a(x1)) (11)
a#(c(x1)) → a#(x1) (12)
b#(b(b(x1))) → c#(b(x1)) (13)
d#(d(x1)) → d#(b(d(b(d(x1))))) (14)
d#(d(x1)) → b#(d(b(d(x1)))) (15)
d#(d(x1)) → d#(b(d(x1))) (16)
d#(d(x1)) → b#(d(x1)) (17)
a#(a(x1)) → a#(d(a(x1))) (18)
a#(a(x1)) → d#(a(x1)) (19)
a#(b(x1)) → c#(c(a(x1))) (20)
a#(b(x1)) → c#(a(x1)) (21)
a#(b(x1)) → a#(x1) (22)
c#(c(x1)) → c#(b(c(b(c(x1))))) (23)
c#(c(x1)) → b#(c(b(c(x1)))) (24)
c#(c(x1)) → c#(b(c(x1))) (25)
c#(c(x1)) → b#(c(x1)) (26)
c#(c(c(x1))) → c#(b(b(x1))) (27)
c#(c(c(x1))) → b#(b(x1)) (28)
c#(c(c(x1))) → b#(x1) (29)

1.1 Dependency Graph Processor

The dependency pairs are split into 3 components.