YES
O(n^3)
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
         [2]
   [u] = [0]
         [3]
   
         [1]
   [o] = [2]
         [6]
   
         [1]
   [i] = [2]
         [6]
   
         [1]
   [e] = [1]
         [3]
   
         [1]
   [a] = [0]
         [3]
   
            [1]
   [n__u] = [0]
            [3]
   
            [0]
   [n__o] = [2]
            [6]
   
            [0]
   [n__i] = [0]
            [6]
   
            [0]
   [n__e] = [0]
            [3]
   
            [0]
   [n__a] = [0]
            [3]
   
           [X2]    [1 0 4][X2]   [6]
   [isPal]([X1]) = [0 0 3][X1] + [0]
           [X0]    [0 0 0][X0]   [0]
   
              [X2]    [1 0 4][X2]   [5]
   [n__isPal]([X1]) = [0 0 3][X1] + [0]
              [X0]    [0 0 0][X0]   [0]
   
             [X2]    [1 0 4][X2]   [3]
   [isNePal]([X1]) = [0 0 3][X1] + [0]
             [X0]    [0 0 0][X0]   [0]
   
                 [X2]    [1 0 4][X2]   [2]
   [n__isNeList]([X1]) = [0 0 3][X1] + [0]
                 [X0]    [0 0 0][X0]   [0]
   
           [X2]    [1 0 4][X2]   [0]
   [isQid]([X1]) = [0 0 3][X1] + [0]
           [X0]    [0 0 0][X0]   [0]
   
           [X5]  [X2]    [1 0 6][X5]   [1 0 0][X2]   [0]
   [n____]([X4], [X1]) = [0 1 7][X4] + [0 1 0][X1] + [2]
           [X3]  [X0]    [0 0 1][X3]   [0 0 1][X0]   [4]
   
               [X2]    [1 0 4][X2]   [5]
   [n__isList]([X1]) = [0 0 3][X1] + [0]
               [X0]    [0 0 0][X0]   [0]
   
              [0]
   [n__nil] = [0]
              [7]
   
            [X2]    [1 0 4][X2]   [6]
   [isList]([X1]) = [0 0 3][X1] + [0]
            [X0]    [0 0 0][X0]   [0]
   
              [X2]    [1 0 4][X2]   [3]
   [isNeList]([X1]) = [0 0 3][X1] + [0]
              [X0]    [0 0 0][X0]   [0]
   
          [0]
   [tt] = [7]
          [0]
   
         [X5]  [X2]    [1 2 0][X5]   [1 0 0][X2]   [0]
   [and]([X4], [X1]) = [0 1 0][X4] + [0 1 1][X1] + [1]
         [X3]  [X0]    [0 0 0][X3]   [0 0 1][X0]   [0]
   
              [X2]    [1 0 0][X2]   [2]
   [activate]([X1]) = [0 1 1][X1] + [0]
              [X0]    [0 0 1][X0]   [0]
   
           [1]
   [nil] = [0]
           [7]
   
        [X5]  [X2]    [1 0 6][X5]   [1 0 0][X2]   [1]
   [__]([X4], [X1]) = [0 1 7][X4] + [0 1 0][X1] + [4]
        [X3]  [X0]    [0 0 1][X3]   [0 0 1][X0]   [4]
   
   
   Qed