NO

Problem 1: 

(VAR v_NonEmpty:S L:S X:S)
(RULES
adx(cons(X:S)) -> incr(cons(X:S))
adx(nil) -> nil
head(cons(X:S)) -> X:S
incr(cons(X:S)) -> cons(s(X:S))
incr(nil) -> nil
nats -> adx(zeros)
tail(cons(X:S)) -> L:S
zeros -> cons(0)
)

Problem 1: 

Extra Variables Processor:
-> Rules:
 adx(cons(X:S)) -> incr(cons(X:S))
 adx(nil) -> nil
 head(cons(X:S)) -> X:S
 incr(cons(X:S)) -> cons(s(X:S))
 incr(nil) -> nil
 nats -> adx(zeros)
 tail(cons(X:S)) -> L:S
 zeros -> cons(0)
-> The system has extra variables.

The problem is infinite.