Certification Problem

Input (TPDB SRS_Standard/Zantema_04/z121)

The rewrite relation of the following TRS is considered.

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

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#(f(x1)) → a#(a(x1)) (8)
c#(d(d(x1))) → f#(x1) (9)
b#(b(x1)) → c#(x1) (10)
c#(c(x1)) → d#(x1) (11)
b#(b(x1)) → c#(a(c(x1))) (12)
b#(b(x1)) → a#(c(x1)) (13)
f#(f(x1)) → b#(b(b(x1))) (14)
c#(c(x1)) → d#(d(d(x1))) (15)
b#(b(x1)) → c#(c(a(c(x1)))) (16)
b#(d(x1)) → b#(x1) (17)
d#(b(x1)) → d#(a(b(x1))) (18)
f#(f(x1)) → b#(x1) (19)
a#(f(x1)) → a#(x1) (20)
a#(f(x1)) → f#(a(a(x1))) (21)
c#(c(x1)) → d#(d(x1)) (22)
f#(f(x1)) → b#(b(x1)) (23)
b#(d(x1)) → d#(b(x1)) (24)
d#(b(x1)) → a#(b(x1)) (25)

1.1 Dependency Graph Processor

The dependency pairs are split into 1 component.