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