Certification Problem

Input (TPDB TRS_Standard/Transformed_CSR_04/ExIntrod_GM01_FR)

The rewrite relation of the following TRS is considered.

incr(nil) → nil (1)
incr(cons(X,L)) → cons(s(X),n__incr(activate(L))) (2)
adx(nil) → nil (3)
adx(cons(X,L)) → incr(cons(X,n__adx(activate(L)))) (4)
nats → adx(zeros) (5)
zeros → cons(0,n__zeros) (6)
head(cons(X,L)) → X (7)
tail(cons(X,L)) → activate(L) (8)
incr(X) → n__incr(X) (9)
adx(X) → n__adx(X) (10)
zeros → n__zeros (11)
activate(n__incr(X)) → incr(activate(X)) (12)
activate(n__adx(X)) → adx(activate(X)) (13)
activate(n__zeros) → zeros (14)
activate(X) → X (15)

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__adx(n__zeros)))
→ cons(s(X),n__incr(activate(n__adx(n__zeros))))
→ cons(s(X),n__incr(adx(activate(n__zeros))))
→ cons(s(X),n__incr(adx(zeros)))
→ cons(s(X),n__incr(adx(cons(0,n__zeros))))
→ cons(s(X),n__incr(incr(cons(0,n__adx(activate(n__zeros))))))
→ cons(s(X),n__incr(incr(cons(0,n__adx(n__zeros)))))
= t6
where t6 = C[t0σ] and σ = {X/0} and C = cons(s(X),n__incr(☐))