Certification Problem

Input (TPDB SRS_Standard/Secret_05_SRS/jambox1)

The rewrite relation of the following TRS is considered.

a(c(x1)) → a(x1) (1)
a(c(b(c(x1)))) → c(b(c(c(x1)))) (2)
c(x1) → b(a(a(x1))) (3)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by AProVE @ termCOMP 2023)

1 String Reversal

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

1.1 Closure Under Flat Contexts

Using the flat contexts

{c(☐), a(☐), b(☐)}

We obtain the transformed TRS
c(b(c(a(x1)))) → c(c(b(c(x1)))) (5)
c(c(a(x1))) → c(a(x1)) (7)
a(c(a(x1))) → a(a(x1)) (8)
b(c(a(x1))) → b(a(x1)) (9)
c(c(x1)) → c(a(a(b(x1)))) (10)
a(c(x1)) → a(a(a(b(x1)))) (11)
b(c(x1)) → b(a(a(b(x1)))) (12)

1.1.1 Semantic Labeling

Root-labeling is applied.

We obtain the labeled TRS
cb(bc(ca(ac(x1)))) → cc(cb(bc(cc(x1)))) (13)
cb(bc(ca(ab(x1)))) → cc(cb(bc(cb(x1)))) (14)
cb(bc(ca(aa(x1)))) → cc(cb(bc(ca(x1)))) (15)
cc(ca(ac(x1))) → ca(ac(x1)) (16)
cc(ca(ab(x1))) → ca(ab(x1)) (17)
cc(ca(aa(x1))) → ca(aa(x1)) (18)
ac(ca(ac(x1))) → aa(ac(x1)) (19)
ac(ca(ab(x1))) → aa(ab(x1)) (20)
ac(ca(aa(x1))) → aa(aa(x1)) (21)
bc(ca(ac(x1))) → ba(ac(x1)) (22)
bc(ca(ab(x1))) → ba(ab(x1)) (23)
bc(ca(aa(x1))) → ba(aa(x1)) (24)
cc(cc(x1)) → ca(aa(ab(bc(x1)))) (25)
cc(cb(x1)) → ca(aa(ab(bb(x1)))) (26)
cc(ca(x1)) → ca(aa(ab(ba(x1)))) (27)
ac(cc(x1)) → aa(aa(ab(bc(x1)))) (28)
ac(cb(x1)) → aa(aa(ab(bb(x1)))) (29)
ac(ca(x1)) → aa(aa(ab(ba(x1)))) (30)
bc(cc(x1)) → ba(aa(ab(bc(x1)))) (31)
bc(cb(x1)) → ba(aa(ab(bb(x1)))) (32)
bc(ca(x1)) → ba(aa(ab(ba(x1)))) (33)

1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[cb(x1)] = 1 · x1
[bc(x1)] = 1 · x1
[ca(x1)] = 1 · x1
[ac(x1)] = 1 · x1 + 1
[cc(x1)] = 1 · x1
[ab(x1)] = 1 · x1
[aa(x1)] = 1 · x1
[ba(x1)] = 1 · x1
[bb(x1)] = 1 · x1
all of the following rules can be deleted.
cb(bc(ca(ac(x1)))) → cc(cb(bc(cc(x1)))) (13)
ac(ca(ac(x1))) → aa(ac(x1)) (19)
ac(ca(ab(x1))) → aa(ab(x1)) (20)
ac(ca(aa(x1))) → aa(aa(x1)) (21)
ac(cc(x1)) → aa(aa(ab(bc(x1)))) (28)
ac(cb(x1)) → aa(aa(ab(bb(x1)))) (29)
ac(ca(x1)) → aa(aa(ab(ba(x1)))) (30)

1.1.1.1.1 Dependency Pair Transformation

The following set of initial dependency pairs has been identified.
cb#(bc(ca(ab(x1)))) → cc#(cb(bc(cb(x1)))) (34)
cb#(bc(ca(ab(x1)))) → cb#(bc(cb(x1))) (35)
cb#(bc(ca(ab(x1)))) → bc#(cb(x1)) (36)
cb#(bc(ca(ab(x1)))) → cb#(x1) (37)
cb#(bc(ca(aa(x1)))) → cc#(cb(bc(ca(x1)))) (38)
cb#(bc(ca(aa(x1)))) → cb#(bc(ca(x1))) (39)
cb#(bc(ca(aa(x1)))) → bc#(ca(x1)) (40)
cc#(cc(x1)) → bc#(x1) (41)
bc#(cc(x1)) → bc#(x1) (42)

1.1.1.1.1.1 Dependency Graph Processor

The dependency pairs are split into 2 components.