NO

Problem 1: 

(VAR v_NonEmpty:S X:S Y:S)
(RULES
adx(cons) -> incr(cons)
hd(cons) -> X:S
incr(cons) -> cons
nats -> adx(zeros)
tl(cons) -> Y:S
zeros -> cons
)

Problem 1: 

Extra Variables Processor:
-> Rules:
 adx(cons) -> incr(cons)
 hd(cons) -> X:S
 incr(cons) -> cons
 nats -> adx(zeros)
 tl(cons) -> Y:S
 zeros -> cons
-> The system has extra variables.

The problem is infinite.