YES

TRS:

  __(__(X,Y),Z) -> __(X,__(Y,Z))
  __(X,nil()) -> X
  __(nil(),X) -> X
  and(tt(),X) -> activate(X)
  isList(V) -> isNeList(activate(V))
  isList(n__nil()) -> tt()
  isList(n____(V1,V2)) -> and(isList(activate(V1)),n__isList(activate(V2)))
  isNeList(V) -> isQid(activate(V))
  isNeList(n____(V1,V2)) -> and(isList(activate(V1)),n__isNeList(activate(V2)))
  isNeList(n____(V1,V2)) -> and(isNeList(activate(V1)),n__isList(activate(V2)))
  isNePal(V) -> isQid(activate(V))
  isNePal(n____(I,__(P,I))) -> and(isQid(activate(I)),n__isPal(activate(P)))
  isPal(V) -> isNePal(activate(V))
  isPal(n__nil()) -> tt()
  isQid(n__a()) -> tt()
  isQid(n__e()) -> tt()
  isQid(n__i()) -> tt()
  isQid(n__o()) -> tt()
  isQid(n__u()) -> tt()
  nil() -> n__nil()
  __(X1,X2) -> n____(X1,X2)
  isList(X) -> n__isList(X)
  isNeList(X) -> n__isNeList(X)
  isPal(X) -> n__isPal(X)
  a() -> n__a()
  e() -> n__e()
  i() -> n__i()
  o() -> n__o()
  u() -> n__u()
  activate(n__nil()) -> nil()
  activate(n____(X1,X2)) -> __(X1,X2)
  activate(n__isList(X)) -> isList(X)
  activate(n__isNeList(X)) -> isNeList(X)
  activate(n__isPal(X)) -> isPal(X)
  activate(n__a()) -> a()
  activate(n__e()) -> e()
  activate(n__i()) -> i()
  activate(n__o()) -> o()
  activate(n__u()) -> u()
  activate(X) -> X

linear polynomial interpretations on N:

  ___A(x1,x2) = x1 + x2 + 19
  __#_A(x1,x2) = x1 + x2 + 19
  nil_A = 5
  nil#_A = 5
  and_A(x1,x2) = x1 + x2
  and#_A(x1,x2) = x1 + x2
  tt_A = 3
  tt#_A = 3
  activate_A(x1) = x1 + 2
  activate#_A(x1) = x1 + 2
  isList_A(x1) = x1 + 7
  isList#_A(x1) = x1 + 7
  isNeList_A(x1) = x1 + 4
  isNeList#_A(x1) = x1 + 4
  n__nil_A = 4
  n__nil#_A = 4
  n_____A(x1,x2) = x1 + x2 + 18
  n____#_A(x1,x2) = x1 + x2 + 18
  n__isList_A(x1) = x1 + 6
  n__isList#_A(x1) = x1 + 6
  isQid_A(x1) = x1 + 1
  isQid#_A(x1) = x1 + 1
  n__isNeList_A(x1) = x1 + 3
  n__isNeList#_A(x1) = x1 + 3
  isNePal_A(x1) = x1 + 4
  isNePal#_A(x1) = x1 + 4
  n__isPal_A(x1) = x1 + 13
  n__isPal#_A(x1) = x1 + 13
  isPal_A(x1) = x1 + 14
  isPal#_A(x1) = x1 + 14
  n__a_A = 4
  n__a#_A = 4
  n__e_A = 4
  n__e#_A = 4
  n__i_A = 4
  n__i#_A = 4
  n__o_A = 4
  n__o#_A = 4
  n__u_A = 4
  n__u#_A = 4
  a_A = 5
  a#_A = 5
  e_A = 5
  e#_A = 5
  i_A = 5
  i#_A = 5
  o_A = 5
  o#_A = 5
  u_A = 5
  u#_A = 5

precedence:

  __ = a = i = u > n__nil = n____ = n__a = n__e = n__i = n__o = n__u > nil = and = tt = e = o > activate = isList = isNeList > n__isList > isQid > n__isNeList > isNePal > n__isPal > isPal