Certification Problem

Input (TPDB SRS_Standard/Secret_07_SRS/x04)

The rewrite relation of the following TRS is considered.

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

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by AProVE @ termCOMP 2023)

1 Rule Removal

Using the linear polynomial interpretation over the naturals
[a(x1)] = 1 · x1
[b(x1)] = 1 · x1
[c(x1)] = 1 · x1 + 1
[d(x1)] = 1 · x1
all of the following rules can be deleted.
c(b(x1)) → b(a(d(x1))) (5)

1.1 Dependency Pair Transformation

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

1.1.1 Dependency Graph Processor

The dependency pairs are split into 3 components.