Certification Problem

Input (TPDB TRS_Standard/Transformed_CSR_04/Ex1_Luc04b_FR)

The rewrite relation of the following TRS is considered.

nats → cons(0,n__incr(n__nats)) (1)
pairs → cons(0,n__incr(n__odds)) (2)
odds → incr(pairs) (3)
incr(cons(X,XS)) → cons(s(X),n__incr(activate(XS))) (4)
head(cons(X,XS)) → X (5)
tail(cons(X,XS)) → activate(XS) (6)
incr(X) → n__incr(X) (7)
nats → n__nats (8)
odds → n__odds (9)
activate(n__incr(X)) → incr(activate(X)) (10)
activate(n__nats) → nats (11)
activate(n__odds) → odds (12)
activate(X) → X (13)

Property / Task

Prove or disprove termination.

Answer / Result

No.

Proof (by ttt2 @ termCOMP 2023)

1 Loop

The following loop proves nontermination.

t0 = incr(cons(X,n__incr(n__nats)))
→ cons(s(X),n__incr(activate(n__incr(n__nats))))
→ cons(s(X),n__incr(incr(activate(n__nats))))
→ cons(s(X),n__incr(incr(nats)))
→ cons(s(X),n__incr(incr(cons(0,n__incr(n__nats)))))
= t4
where t4 = C[t0σ] and σ = {X/0} and C = cons(s(X),n__incr(☐))