Certification Problem

Input (TPDB SRS_Standard/Secret_05_SRS/torpa1)

The rewrite relation of the following TRS is considered.

a(d(x1)) → d(b(c(b(d(x1))))) (1)
a(x1) → b(b(f(b(b(x1))))) (2)
b(d(b(x1))) → a(d(x1)) (3)
d(f(x1)) → b(d(x1)) (4)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by matchbox @ termCOMP 2023)

1 String Reversal

Since only unary symbols occur, one can reverse all terms and obtains the TRS
d(a(x1)) → d(b(c(b(d(x1))))) (5)
a(x1) → b(b(f(b(b(x1))))) (2)
b(d(b(x1))) → d(a(x1)) (6)
f(d(x1)) → d(b(x1)) (7)

1.1 Dependency Pair Transformation

The following set of initial dependency pairs has been identified.
f#(d(x1)) → d#(b(x1)) (8)
f#(d(x1)) → b#(x1) (9)
d#(a(x1)) → d#(x1) (10)
d#(a(x1)) → d#(b(c(b(d(x1))))) (11)
d#(a(x1)) → b#(d(x1)) (12)
d#(a(x1)) → b#(c(b(d(x1)))) (13)
b#(d(b(x1))) → d#(a(x1)) (14)
b#(d(b(x1))) → a#(x1) (15)
a#(x1) → f#(b(b(x1))) (16)
a#(x1) → b#(x1) (17)
a#(x1) → b#(f(b(b(x1)))) (18)
a#(x1) → b#(b(x1)) (19)
a#(x1) → b#(b(f(b(b(x1))))) (20)

1.1.1 Dependency Graph Processor

The dependency pairs are split into 1 component.