YES
O(n^2)
TRS:
 {
                 __(X, nil()) -> X,
                   __(X1, X2) -> n____(X1, X2),
              __(__(X, Y), Z) -> __(X, __(Y, Z)),
                 __(nil(), X) -> X,
                        nil() -> n__nil(),
                  activate(X) -> X,
           activate(n__nil()) -> nil(),
       activate(n__isList(X)) -> isList(X),
      activate(n____(X1, X2)) -> __(X1, X2),
     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(),
                 and(tt(), X) -> activate(X),
                  isNeList(X) -> n__isNeList(X),
                  isNeList(V) -> isQid(activate(V)),
      isNeList(n____(V1, V2)) ->
  and(isNeList(activate(V1)), n__isList(activate(V2))),
      isNeList(n____(V1, V2)) ->
  and(isList(activate(V1)), n__isNeList(activate(V2))),
                    isList(X) -> n__isList(X),
                    isList(V) -> isNeList(activate(V)),
             isList(n__nil()) -> tt(),
        isList(n____(V1, V2)) ->
  and(isList(activate(V1)), n__isList(activate(V2))),
                isQid(n__a()) -> tt(),
                isQid(n__e()) -> tt(),
                isQid(n__i()) -> tt(),
                isQid(n__o()) -> tt(),
                isQid(n__u()) -> tt(),
                   isNePal(V) -> isQid(activate(V)),
  isNePal(n____(I, __(P, I))) ->
  and(isQid(activate(I)), n__isPal(activate(P))),
                     isPal(X) -> n__isPal(X),
                     isPal(V) -> isNePal(activate(V)),
              isPal(n__nil()) -> tt(),
                          a() -> n__a(),
                          e() -> n__e(),
                          i() -> n__i(),
                          o() -> n__o(),
                          u() -> n__u()
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
                   __(X, nil()) -> X,
                     __(X1, X2) -> n____(X1, X2),
                __(__(X, Y), Z) -> __(X, __(Y, Z)),
                   __(nil(), X) -> X,
                          nil() -> n__nil(),
                    activate(X) -> X,
             activate(n__nil()) -> nil(),
         activate(n__isList(X)) -> isList(X),
        activate(n____(X1, X2)) -> __(X1, X2),
       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(),
                   and(tt(), X) -> activate(X),
                    isNeList(X) -> n__isNeList(X),
                    isNeList(V) -> isQid(activate(V)),
        isNeList(n____(V1, V2)) ->
    and(isNeList(activate(V1)), n__isList(activate(V2))),
        isNeList(n____(V1, V2)) ->
    and(isList(activate(V1)), n__isNeList(activate(V2))),
                      isList(X) -> n__isList(X),
                      isList(V) -> isNeList(activate(V)),
               isList(n__nil()) -> tt(),
          isList(n____(V1, V2)) ->
    and(isList(activate(V1)), n__isList(activate(V2))),
                  isQid(n__a()) -> tt(),
                  isQid(n__e()) -> tt(),
                  isQid(n__i()) -> tt(),
                  isQid(n__o()) -> tt(),
                  isQid(n__u()) -> tt(),
                     isNePal(V) -> isQid(activate(V)),
    isNePal(n____(I, __(P, I))) ->
    and(isQid(activate(I)), n__isPal(activate(P))),
                       isPal(X) -> n__isPal(X),
                       isPal(V) -> isNePal(activate(V)),
                isPal(n__nil()) -> tt(),
                            a() -> n__a(),
                            e() -> n__e(),
                            i() -> n__i(),
                            o() -> n__o(),
                            u() -> n__u()
   }
  Matrix Interpretation:
   Interpretation class: triangular
         [1]
   [u] = [4]
   
         [4]
   [o] = [2]
   
         [2]
   [i] = [4]
   
         [1]
   [e] = [1]
   
         [1]
   [a] = [4]
   
            [0]
   [n__u] = [4]
   
            [3]
   [n__o] = [2]
   
            [1]
   [n__i] = [4]
   
            [0]
   [n__e] = [1]
   
            [0]
   [n__a] = [4]
   
           [X1]    [1 4][X1]   [7]
   [isPal]([X0]) = [0 1][X0] + [1]
   
              [X1]    [1 4][X1]   [6]
   [n__isPal]([X0]) = [0 1][X0] + [1]
   
             [X1]    [1 4][X1]   [4]
   [isNePal]([X0]) = [0 1][X0] + [0]
   
                 [X1]    [1 4][X1]   [2]
   [n__isNeList]([X0]) = [0 1][X0] + [0]
   
           [X1]    [1 2][X1]   [0]
   [isQid]([X0]) = [0 1][X0] + [0]
   
           [X3]  [X1]    [1 6][X3]   [1 0][X1]   [4]
   [n____]([X2], [X0]) = [0 1][X2] + [0 1][X0] + [4]
   
               [X1]    [1 4][X1]   [5]
   [n__isList]([X0]) = [0 1][X0] + [1]
   
              [0]
   [n__nil] = [0]
   
            [X1]    [1 4][X1]   [6]
   [isList]([X0]) = [0 1][X0] + [1]
   
              [X1]    [1 4][X1]   [3]
   [isNeList]([X0]) = [0 1][X0] + [0]
   
          [0]
   [tt] = [1]
   
         [X3]  [X1]    [1 6][X3]   [1 0][X1]   [1]
   [and]([X2], [X0]) = [0 0][X2] + [0 1][X0] + [0]
   
              [X1]    [1 0][X1]   [2]
   [activate]([X0]) = [0 1][X0] + [0]
   
           [1]
   [nil] = [0]
   
        [X3]  [X1]    [1 6][X3]   [1 0][X1]   [5]
   [__]([X2], [X0]) = [0 1][X2] + [0 1][X0] + [4]
   
   
   Qed