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