YES linear polynomial interpretations on negative integers: isnoc_A(x1) = x1 cons_A(x1,x2) = -1 tp2_A(x1,x2) = -1 nil_A = -2 the condition isnoc(nil()) ->> tp2(x3,x4) is unsatisfiable for all substitutions.