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(),
                    U11(tt()) -> tt(),
                    U22(tt()) -> tt(),
                    isList(V) -> U11(isNeList(activate(V))),
             isList(n__nil()) -> tt(),
        isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)),
                  activate(X) -> X,
           activate(n__nil()) -> nil(),
      activate(n____(X1, X2)) -> __(X1, X2),
             activate(n__a()) -> a(),
             activate(n__e()) -> e(),
             activate(n__i()) -> i(),
             activate(n__o()) -> o(),
             activate(n__u()) -> u(),
                U21(tt(), V2) -> U22(isList(activate(V2))),
                    U31(tt()) -> tt(),
                    U42(tt()) -> tt(),
                  isNeList(V) -> U31(isQid(activate(V))),
      isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)),
      isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)),
                U41(tt(), V2) -> U42(isNeList(activate(V2))),
                    U52(tt()) -> tt(),
                U51(tt(), V2) -> U52(isList(activate(V2))),
                    U61(tt()) -> tt(),
                    U72(tt()) -> tt(),
                     isPal(V) -> U81(isNePal(activate(V))),
              isPal(n__nil()) -> tt(),
                 U71(tt(), P) -> U72(isPal(activate(P))),
                    U81(tt()) -> tt(),
                isQid(n__a()) -> tt(),
                isQid(n__e()) -> tt(),
                isQid(n__i()) -> tt(),
                isQid(n__o()) -> tt(),
                isQid(n__u()) -> tt(),
                   isNePal(V) -> U61(isQid(activate(V))),
  isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P)),
                          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(),
                      U11(tt()) -> tt(),
                      U22(tt()) -> tt(),
                      isList(V) -> U11(isNeList(activate(V))),
               isList(n__nil()) -> tt(),
          isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)),
                    activate(X) -> X,
             activate(n__nil()) -> nil(),
        activate(n____(X1, X2)) -> __(X1, X2),
               activate(n__a()) -> a(),
               activate(n__e()) -> e(),
               activate(n__i()) -> i(),
               activate(n__o()) -> o(),
               activate(n__u()) -> u(),
                  U21(tt(), V2) -> U22(isList(activate(V2))),
                      U31(tt()) -> tt(),
                      U42(tt()) -> tt(),
                    isNeList(V) -> U31(isQid(activate(V))),
        isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)),
        isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)),
                  U41(tt(), V2) -> U42(isNeList(activate(V2))),
                      U52(tt()) -> tt(),
                  U51(tt(), V2) -> U52(isList(activate(V2))),
                      U61(tt()) -> tt(),
                      U72(tt()) -> tt(),
                       isPal(V) -> U81(isNePal(activate(V))),
                isPal(n__nil()) -> tt(),
                   U71(tt(), P) -> U72(isPal(activate(P))),
                      U81(tt()) -> tt(),
                  isQid(n__a()) -> tt(),
                  isQid(n__e()) -> tt(),
                  isQid(n__i()) -> tt(),
                  isQid(n__o()) -> tt(),
                  isQid(n__u()) -> tt(),
                     isNePal(V) -> U61(isQid(activate(V))),
    isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P)),
                            a() -> n__a(),
                            e() -> n__e(),
                            i() -> n__i(),
                            o() -> n__o(),
                            u() -> n__u()
   }
  Matrix Interpretation:
   Interpretation class: triangular
         [1]
   [u] = [5]
   
         [1]
   [o] = [6]
   
         [1]
   [i] = [5]
   
         [1]
   [e] = [7]
   
         [2]
   [a] = [7]
   
            [0]
   [n__u] = [5]
   
            [0]
   [n__o] = [6]
   
            [0]
   [n__i] = [5]
   
            [0]
   [n__e] = [7]
   
            [1]
   [n__a] = [7]
   
             [X1]    [1 2][X1]   [4]
   [isNePal]([X0]) = [0 1][X0] + [0]
   
           [X1]    [1 1][X1]   [0]
   [isQid]([X0]) = [0 1][X0] + [0]
   
           [X3]  [X1]    [1 7][X3]   [1 0][X1]   [4]
   [n____]([X2], [X0]) = [0 1][X2] + [0 1][X0] + [6]
   
              [1]
   [n__nil] = [5]
   
         [X1]    [1 5][X1]   [0]
   [U81]([X0]) = [0 1][X0] + [0]
   
         [X3]  [X1]    [1 0][X3]   [1 7][X1]   [7]
   [U71]([X2], [X0]) = [0 1][X2] + [0 1][X0] + [3]
   
           [X1]    [1 7][X1]   [7]
   [isPal]([X0]) = [0 1][X0] + [0]
   
         [X1]    [1 0][X1]   [1]
   [U72]([X0]) = [0 0][X0] + [5]
   
         [X1]    [1 1][X1]   [0]
   [U61]([X0]) = [0 1][X0] + [0]
   
         [X3]  [X1]    [1 7][X3]   [1 2][X1]   [0]
   [U51]([X2], [X0]) = [0 0][X2] + [0 0][X0] + [5]
   
         [X1]    [1 0][X1]   [5]
   [U52]([X0]) = [0 0][X0] + [5]
   
         [X3]  [X1]    [1 4][X3]   [1 2][X1]   [2]
   [U41]([X2], [X0]) = [0 0][X2] + [0 1][X0] + [3]
   
              [X1]    [1 2][X1]   [3]
   [isNeList]([X0]) = [0 1][X0] + [0]
   
         [X1]    [1 0][X1]   [4]
   [U42]([X0]) = [0 1][X0] + [2]
   
         [X1]    [1 1][X1]   [0]
   [U31]([X0]) = [0 1][X0] + [0]
   
         [X3]  [X1]    [1 2][X3]   [1 2][X1]   [1]
   [U21]([X2], [X0]) = [0 1][X2] + [0 0][X0] + [2]
   
              [X1]    [1 0][X1]   [2]
   [activate]([X0]) = [0 1][X0] + [0]
   
            [X1]    [1 2][X1]   [7]
   [isList]([X0]) = [0 1][X0] + [0]
   
         [X1]    [1 0][X1]   [1]
   [U22]([X0]) = [0 0][X0] + [6]
   
         [X1]    [1 0][X1]   [1]
   [U11]([X0]) = [0 1][X0] + [0]
   
          [4]
   [tt] = [5]
   
           [2]
   [nil] = [5]
   
        [X3]  [X1]    [1 7][X3]   [1 0][X1]   [5]
   [__]([X2], [X0]) = [0 1][X2] + [0 1][X0] + [6]
   
   
   Qed