YES

TRS:

  a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z)))
  a____(X,nil()) -> mark(X)
  a____(nil(),X) -> mark(X)
  a__U11(tt(),V) -> a__U12(a__isPalListKind(V),V)
  a__U12(tt(),V) -> a__U13(a__isNeList(V))
  a__U13(tt()) -> tt()
  a__U21(tt(),V1,V2) -> a__U22(a__isPalListKind(V1),V1,V2)
  a__U22(tt(),V1,V2) -> a__U23(a__isPalListKind(V2),V1,V2)
  a__U23(tt(),V1,V2) -> a__U24(a__isPalListKind(V2),V1,V2)
  a__U24(tt(),V1,V2) -> a__U25(a__isList(V1),V2)
  a__U25(tt(),V2) -> a__U26(a__isList(V2))
  a__U26(tt()) -> tt()
  a__U31(tt(),V) -> a__U32(a__isPalListKind(V),V)
  a__U32(tt(),V) -> a__U33(a__isQid(V))
  a__U33(tt()) -> tt()
  a__U41(tt(),V1,V2) -> a__U42(a__isPalListKind(V1),V1,V2)
  a__U42(tt(),V1,V2) -> a__U43(a__isPalListKind(V2),V1,V2)
  a__U43(tt(),V1,V2) -> a__U44(a__isPalListKind(V2),V1,V2)
  a__U44(tt(),V1,V2) -> a__U45(a__isList(V1),V2)
  a__U45(tt(),V2) -> a__U46(a__isNeList(V2))
  a__U46(tt()) -> tt()
  a__U51(tt(),V1,V2) -> a__U52(a__isPalListKind(V1),V1,V2)
  a__U52(tt(),V1,V2) -> a__U53(a__isPalListKind(V2),V1,V2)
  a__U53(tt(),V1,V2) -> a__U54(a__isPalListKind(V2),V1,V2)
  a__U54(tt(),V1,V2) -> a__U55(a__isNeList(V1),V2)
  a__U55(tt(),V2) -> a__U56(a__isList(V2))
  a__U56(tt()) -> tt()
  a__U61(tt(),V) -> a__U62(a__isPalListKind(V),V)
  a__U62(tt(),V) -> a__U63(a__isQid(V))
  a__U63(tt()) -> tt()
  a__U71(tt(),I,P) -> a__U72(a__isPalListKind(I),P)
  a__U72(tt(),P) -> a__U73(a__isPal(P),P)
  a__U73(tt(),P) -> a__U74(a__isPalListKind(P))
  a__U74(tt()) -> tt()
  a__U81(tt(),V) -> a__U82(a__isPalListKind(V),V)
  a__U82(tt(),V) -> a__U83(a__isNePal(V))
  a__U83(tt()) -> tt()
  a__U91(tt(),V2) -> a__U92(a__isPalListKind(V2))
  a__U92(tt()) -> tt()
  a__isList(V) -> a__U11(a__isPalListKind(V),V)
  a__isList(nil()) -> tt()
  a__isList(__(V1,V2)) -> a__U21(a__isPalListKind(V1),V1,V2)
  a__isNeList(V) -> a__U31(a__isPalListKind(V),V)
  a__isNeList(__(V1,V2)) -> a__U41(a__isPalListKind(V1),V1,V2)
  a__isNeList(__(V1,V2)) -> a__U51(a__isPalListKind(V1),V1,V2)
  a__isNePal(V) -> a__U61(a__isPalListKind(V),V)
  a__isNePal(__(I,__(P,I))) -> a__U71(a__isQid(I),I,P)
  a__isPal(V) -> a__U81(a__isPalListKind(V),V)
  a__isPal(nil()) -> tt()
  a__isPalListKind(a()) -> tt()
  a__isPalListKind(e()) -> tt()
  a__isPalListKind(i()) -> tt()
  a__isPalListKind(nil()) -> tt()
  a__isPalListKind(o()) -> tt()
  a__isPalListKind(u()) -> tt()
  a__isPalListKind(__(V1,V2)) -> a__U91(a__isPalListKind(V1),V2)
  a__isQid(a()) -> tt()
  a__isQid(e()) -> tt()
  a__isQid(i()) -> tt()
  a__isQid(o()) -> tt()
  a__isQid(u()) -> tt()
  mark(__(X1,X2)) -> a____(mark(X1),mark(X2))
  mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
  mark(U12(X1,X2)) -> a__U12(mark(X1),X2)
  mark(isPalListKind(X)) -> a__isPalListKind(X)
  mark(U13(X)) -> a__U13(mark(X))
  mark(isNeList(X)) -> a__isNeList(X)
  mark(U21(X1,X2,X3)) -> a__U21(mark(X1),X2,X3)
  mark(U22(X1,X2,X3)) -> a__U22(mark(X1),X2,X3)
  mark(U23(X1,X2,X3)) -> a__U23(mark(X1),X2,X3)
  mark(U24(X1,X2,X3)) -> a__U24(mark(X1),X2,X3)
  mark(U25(X1,X2)) -> a__U25(mark(X1),X2)
  mark(isList(X)) -> a__isList(X)
  mark(U26(X)) -> a__U26(mark(X))
  mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
  mark(U32(X1,X2)) -> a__U32(mark(X1),X2)
  mark(U33(X)) -> a__U33(mark(X))
  mark(isQid(X)) -> a__isQid(X)
  mark(U41(X1,X2,X3)) -> a__U41(mark(X1),X2,X3)
  mark(U42(X1,X2,X3)) -> a__U42(mark(X1),X2,X3)
  mark(U43(X1,X2,X3)) -> a__U43(mark(X1),X2,X3)
  mark(U44(X1,X2,X3)) -> a__U44(mark(X1),X2,X3)
  mark(U45(X1,X2)) -> a__U45(mark(X1),X2)
  mark(U46(X)) -> a__U46(mark(X))
  mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
  mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
  mark(U53(X1,X2,X3)) -> a__U53(mark(X1),X2,X3)
  mark(U54(X1,X2,X3)) -> a__U54(mark(X1),X2,X3)
  mark(U55(X1,X2)) -> a__U55(mark(X1),X2)
  mark(U56(X)) -> a__U56(mark(X))
  mark(U61(X1,X2)) -> a__U61(mark(X1),X2)
  mark(U62(X1,X2)) -> a__U62(mark(X1),X2)
  mark(U63(X)) -> a__U63(mark(X))
  mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
  mark(U72(X1,X2)) -> a__U72(mark(X1),X2)
  mark(U73(X1,X2)) -> a__U73(mark(X1),X2)
  mark(isPal(X)) -> a__isPal(X)
  mark(U74(X)) -> a__U74(mark(X))
  mark(U81(X1,X2)) -> a__U81(mark(X1),X2)
  mark(U82(X1,X2)) -> a__U82(mark(X1),X2)
  mark(U83(X)) -> a__U83(mark(X))
  mark(isNePal(X)) -> a__isNePal(X)
  mark(U91(X1,X2)) -> a__U91(mark(X1),X2)
  mark(U92(X)) -> a__U92(mark(X))
  mark(nil()) -> nil()
  mark(tt()) -> tt()
  mark(a()) -> a()
  mark(e()) -> e()
  mark(i()) -> i()
  mark(o()) -> o()
  mark(u()) -> u()
  a____(X1,X2) -> __(X1,X2)
  a__U11(X1,X2) -> U11(X1,X2)
  a__U12(X1,X2) -> U12(X1,X2)
  a__isPalListKind(X) -> isPalListKind(X)
  a__U13(X) -> U13(X)
  a__isNeList(X) -> isNeList(X)
  a__U21(X1,X2,X3) -> U21(X1,X2,X3)
  a__U22(X1,X2,X3) -> U22(X1,X2,X3)
  a__U23(X1,X2,X3) -> U23(X1,X2,X3)
  a__U24(X1,X2,X3) -> U24(X1,X2,X3)
  a__U25(X1,X2) -> U25(X1,X2)
  a__isList(X) -> isList(X)
  a__U26(X) -> U26(X)
  a__U31(X1,X2) -> U31(X1,X2)
  a__U32(X1,X2) -> U32(X1,X2)
  a__U33(X) -> U33(X)
  a__isQid(X) -> isQid(X)
  a__U41(X1,X2,X3) -> U41(X1,X2,X3)
  a__U42(X1,X2,X3) -> U42(X1,X2,X3)
  a__U43(X1,X2,X3) -> U43(X1,X2,X3)
  a__U44(X1,X2,X3) -> U44(X1,X2,X3)
  a__U45(X1,X2) -> U45(X1,X2)
  a__U46(X) -> U46(X)
  a__U51(X1,X2,X3) -> U51(X1,X2,X3)
  a__U52(X1,X2,X3) -> U52(X1,X2,X3)
  a__U53(X1,X2,X3) -> U53(X1,X2,X3)
  a__U54(X1,X2,X3) -> U54(X1,X2,X3)
  a__U55(X1,X2) -> U55(X1,X2)
  a__U56(X) -> U56(X)
  a__U61(X1,X2) -> U61(X1,X2)
  a__U62(X1,X2) -> U62(X1,X2)
  a__U63(X) -> U63(X)
  a__U71(X1,X2,X3) -> U71(X1,X2,X3)
  a__U72(X1,X2) -> U72(X1,X2)
  a__U73(X1,X2) -> U73(X1,X2)
  a__isPal(X) -> isPal(X)
  a__U74(X) -> U74(X)
  a__U81(X1,X2) -> U81(X1,X2)
  a__U82(X1,X2) -> U82(X1,X2)
  a__U83(X) -> U83(X)
  a__isNePal(X) -> isNePal(X)
  a__U91(X1,X2) -> U91(X1,X2)
  a__U92(X) -> U92(X)

linear polynomial interpretations on N:

  a_____A(x1,x2) = x1 + x2 + 29
  a____#_A(x1,x2) = x1 + x2 + 19
  ___A(x1,x2) = x1 + x2 + 29
  __#_A(x1,x2) = x1 + x2 + 18
  mark_A(x1) = x1
  mark#_A(x1) = x1 + 17
  nil_A = 1
  nil#_A = 13
  a__U11_A(x1,x2) = x1 + x2 + 9
  a__U11#_A(x1,x2) = x2 + 24
  tt_A = 16
  tt#_A = 14
  a__U12_A(x1,x2) = x1 + x2 + 9
  a__U12#_A(x1,x2) = x2 + 23
  a__isPalListKind_A(x1) = 16
  a__isPalListKind#_A(x1) = 15
  a__U13_A(x1) = x1 + 3
  a__U13#_A(x1) = 19
  a__isNeList_A(x1) = x1 + 22
  a__isNeList#_A(x1) = x1 + 22
  a__U21_A(x1,x2,x3) = x1 + x2 + x3 + 36
  a__U21#_A(x1,x2,x3) = x2 + x3 + 52
  a__U22_A(x1,x2,x3) = x1 + x2 + x3 + 36
  a__U22#_A(x1,x2,x3) = x1 + x2 + x3 + 30
  a__U23_A(x1,x2,x3) = x1 + x2 + x3 + 36
  a__U23#_A(x1,x2,x3) = x2 + x3 + 45
  a__U24_A(x1,x2,x3) = x1 + x2 + x3 + 36
  a__U24#_A(x1,x2,x3) = x2 + x3 + 44
  a__U25_A(x1,x2) = x1 + x2 + 27
  a__U25#_A(x1,x2) = x2 + 43
  a__isList_A(x1) = x1 + 25
  a__isList#_A(x1) = x1 + 42
  a__U26_A(x1) = x1 + 2
  a__U26#_A(x1) = 19
  a__U31_A(x1,x2) = x1 + x2 + 5
  a__U31#_A(x1,x2) = 21
  a__U32_A(x1,x2) = x1 + x2 + 4
  a__U32#_A(x1,x2) = 20
  a__U33_A(x1) = x1 + 1
  a__U33#_A(x1) = 15
  a__isQid_A(x1) = x1 + 3
  a__isQid#_A(x1) = 19
  a__U41_A(x1,x2,x3) = x1 + x2 + x3 + 30
  a__U41#_A(x1,x2,x3) = x2 + x3 + 46
  a__U42_A(x1,x2,x3) = x1 + x2 + x3 + 28
  a__U42#_A(x1,x2,x3) = x1 + x2 + x3 + 29
  a__U43_A(x1,x2,x3) = x1 + x2 + x3 + 28
  a__U43#_A(x1,x2,x3) = x2 + x3 + 44
  a__U44_A(x1,x2,x3) = x1 + x2 + x3 + 27
  a__U44#_A(x1,x2,x3) = x2 + x3 + 43
  a__U45_A(x1,x2) = x1 + x2 + 7
  a__U45#_A(x1,x2) = x2 + 23
  a__U46_A(x1) = x1 + 1
  a__U46#_A(x1) = 15
  a__U51_A(x1,x2,x3) = x1 + x2 + x3 + 35
  a__U51#_A(x1,x2,x3) = x2 + x3 + 51
  a__U52_A(x1,x2,x3) = x1 + x2 + x3 + 35
  a__U52#_A(x1,x2,x3) = x1 + x2 + x3 + 35
  a__U53_A(x1,x2,x3) = x1 + x2 + x3 + 35
  a__U53#_A(x1,x2,x3) = x1 + x2 + x3 + 31
  a__U54_A(x1,x2,x3) = x1 + x2 + x3 + 35
  a__U54#_A(x1,x2,x3) = x1 + x2 + x3 + 30
  a__U55_A(x1,x2) = x1 + x2 + 29
  a__U55#_A(x1,x2) = x2 + 45
  a__U56_A(x1) = x1 + 3
  a__U56#_A(x1) = x1 + 19
  a__U61_A(x1,x2) = x1 + x2 + 8
  a__U61#_A(x1,x2) = x2 + 24
  a__U62_A(x1,x2) = x1 + x2 + 8
  a__U62#_A(x1,x2) = x1 + x2 + 7
  a__U63_A(x1) = x1 + 3
  a__U63#_A(x1) = x1 + 19
  a__U71_A(x1,x2,x3) = x1 + x2 + x3 + 13
  a__U71#_A(x1,x2,x3) = x1 + x3 + 14
  a__U72_A(x1,x2) = x1 + x2 + 13
  a__U72#_A(x1,x2) = x2 + 29
  a__U73_A(x1,x2) = x1
  a__U73#_A(x1,x2) = 16
  a__isPal_A(x1) = x1 + 27
  a__isPal#_A(x1) = x1 + 28
  a__U74_A(x1) = x1
  a__U74#_A(x1) = 15
  a__U81_A(x1,x2) = x1 + x2 + 11
  a__U81#_A(x1,x2) = x2 + 27
  a__U82_A(x1,x2) = x1 + x2 + 10
  a__U82#_A(x1,x2) = x2 + 26
  a__U83_A(x1) = x1
  a__U83#_A(x1) = 1
  a__isNePal_A(x1) = x1 + 24
  a__isNePal#_A(x1) = x1 + 25
  a__U91_A(x1,x2) = x1
  a__U91#_A(x1,x2) = x1 + 1
  a__U92_A(x1) = x1
  a__U92#_A(x1) = 15
  a_A = 13
  a#_A = 0
  e_A = 13
  e#_A = 31
  i_A = 13
  i#_A = 15
  o_A = 13
  o#_A = 15
  u_A = 13
  u#_A = 15
  U11_A(x1,x2) = x1 + x2 + 9
  U11#_A(x1,x2) = 23
  U12_A(x1,x2) = x1 + x2 + 9
  U12#_A(x1,x2) = x2 + 16
  isPalListKind_A(x1) = 16
  isPalListKind#_A(x1) = 0
  U13_A(x1) = x1 + 3
  U13#_A(x1) = 18
  isNeList_A(x1) = x1 + 22
  isNeList#_A(x1) = 0
  U21_A(x1,x2,x3) = x1 + x2 + x3 + 36
  U21#_A(x1,x2,x3) = x2 + x3 + 16
  U22_A(x1,x2,x3) = x1 + x2 + x3 + 36
  U22#_A(x1,x2,x3) = x2 + x3 + 29
  U23_A(x1,x2,x3) = x1 + x2 + x3 + 36
  U23#_A(x1,x2,x3) = x2 + x3 + 44
  U24_A(x1,x2,x3) = x1 + x2 + x3 + 36
  U24#_A(x1,x2,x3) = 16
  U25_A(x1,x2) = x1 + x2 + 27
  U25#_A(x1,x2) = 0
  isList_A(x1) = x1 + 25
  isList#_A(x1) = 0
  U26_A(x1) = x1 + 2
  U26#_A(x1) = 18
  U31_A(x1,x2) = x1 + x2 + 5
  U31#_A(x1,x2) = 18
  U32_A(x1,x2) = x1 + x2 + 4
  U32#_A(x1,x2) = 0
  U33_A(x1) = x1 + 1
  U33#_A(x1) = 0
  isQid_A(x1) = x1 + 3
  isQid#_A(x1) = 0
  U41_A(x1,x2,x3) = x1 + x2 + x3 + 30
  U41#_A(x1,x2,x3) = x2 + 18
  U42_A(x1,x2,x3) = x1 + x2 + x3 + 28
  U42#_A(x1,x2,x3) = 0
  U43_A(x1,x2,x3) = x1 + x2 + x3 + 28
  U43#_A(x1,x2,x3) = 43
  U44_A(x1,x2,x3) = x1 + x2 + x3 + 27
  U44#_A(x1,x2,x3) = 42
  U45_A(x1,x2) = x1 + x2 + 7
  U45#_A(x1,x2) = 0
  U46_A(x1) = x1 + 1
  U46#_A(x1) = 14
  U51_A(x1,x2,x3) = x1 + x2 + x3 + 35
  U51#_A(x1,x2,x3) = x3 + 16
  U52_A(x1,x2,x3) = x1 + x2 + x3 + 35
  U52#_A(x1,x2,x3) = 0
  U53_A(x1,x2,x3) = x1 + x2 + x3 + 35
  U53#_A(x1,x2,x3) = 16
  U54_A(x1,x2,x3) = x1 + x2 + x3 + 35
  U54#_A(x1,x2,x3) = 29
  U55_A(x1,x2) = x1 + x2 + 29
  U55#_A(x1,x2) = 16
  U56_A(x1) = x1 + 3
  U56#_A(x1) = x1 + 18
  U61_A(x1,x2) = x1 + x2 + 8
  U61#_A(x1,x2) = 0
  U62_A(x1,x2) = x1 + x2 + 8
  U62#_A(x1,x2) = 6
  U63_A(x1) = x1 + 3
  U63#_A(x1) = 18
  U71_A(x1,x2,x3) = x1 + x2 + x3 + 13
  U71#_A(x1,x2,x3) = x3 + 13
  U72_A(x1,x2) = x1 + x2 + 13
  U72#_A(x1,x2) = 0
  U73_A(x1,x2) = x1
  U73#_A(x1,x2) = 15
  isPal_A(x1) = x1 + 27
  isPal#_A(x1) = 0
  U74_A(x1) = x1
  U74#_A(x1) = 14
  U81_A(x1,x2) = x1 + x2 + 11
  U81#_A(x1,x2) = 18
  U82_A(x1,x2) = x1 + x2 + 10
  U82#_A(x1,x2) = x2 + 18
  U83_A(x1) = x1
  U83#_A(x1) = 0
  isNePal_A(x1) = x1 + 24
  isNePal#_A(x1) = 0
  U91_A(x1,x2) = x1
  U91#_A(x1,x2) = x1
  U92_A(x1) = x1
  U92#_A(x1) = 14

precedence:

  __ = U71 > a__U71 = U72 > a__U22 = a__U72 = U23 = U73 > a__U23 = a__U73 = U24 = U42 > a__U24 = a__U41 = a__U42 = a__U44 = a__U74 > a__U25 = e = U11 = U13 = U41 = U43 = U44 = U52 = U54 = U56 = U63 = U74 = U91 > mark > a____ = nil = a__U26 = a__U43 = a__isNePal = a__U91 = U22 = U25 = U32 = U45 = U61 > a__U45 = a__U61 = a__U92 = U26 = U46 = U62 = isNePal > a__isNeList = a__U46 = a__U62 = U92 > a__U31 = a__U51 = a__U63 = isNeList > a__U32 = a__U52 = U31 = isQid = U51 > a__U33 = a__isQid = a__U53 > a__U54 = U33 = U53 > a__U55 > a__isList = a__U56 = U21 = U55 > a__U11 = a__U21 = U12 = isList > a__U12 > a__U13 = i = o = u > tt = isPal > a__isPal = a > a__U81 > a__isPalListKind = a__U82 = U81 > a__U83 = isPalListKind = U82 > U83