Certification Problem

Input (TPDB TRS_Standard/Transformed_CSR_04/ExIntrod_GM01_Z)

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