Certification Problem

Input (TPDB TRS_Outermost/Strategy_outermost_added_08/Ex1_Luc04b_Z)

The rewrite relation of the following TRS is considered.

nats → cons(0,n__incr(nats)) (1)
pairs → cons(0,n__incr(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)
activate(n__incr(X)) → incr(X) (8)
activate(X) → X (9)
The evaluation strategy is outermost

Property / Task

Prove or disprove termination.

Answer / Result

No.

Proof (by AProVE @ termCOMP 2023)

1 Loop

The following loop proves nontermination.

t0 = nats
→ cons(0,n__incr(nats))
= t1
where t1 = C[t0] and C = cons(0,n__incr(☐))