YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination w.r.t. Q of the given QTRS could be proven:

(0) QTRS
(1) QTRSRRRProof [EQUIVALENT, 1023 ms]
(2) QTRS
(3) QTRSRRRProof [EQUIVALENT, 303 ms]
(4) QTRS
(5) QTRSRRRProof [EQUIVALENT, 45 ms]
(6) QTRS
(7) RisEmptyProof [EQUIVALENT, 0 ms]
(8) YES


----------------------------------------

(0)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z)))
   active(__(X, nil)) -> mark(X)
   active(__(nil, X)) -> mark(X)
   active(U11(tt, V)) -> mark(U12(isNeList(V)))
   active(U12(tt)) -> mark(tt)
   active(U21(tt, V1, V2)) -> mark(U22(isList(V1), V2))
   active(U22(tt, V2)) -> mark(U23(isList(V2)))
   active(U23(tt)) -> mark(tt)
   active(U31(tt, V)) -> mark(U32(isQid(V)))
   active(U32(tt)) -> mark(tt)
   active(U41(tt, V1, V2)) -> mark(U42(isList(V1), V2))
   active(U42(tt, V2)) -> mark(U43(isNeList(V2)))
   active(U43(tt)) -> mark(tt)
   active(U51(tt, V1, V2)) -> mark(U52(isNeList(V1), V2))
   active(U52(tt, V2)) -> mark(U53(isList(V2)))
   active(U53(tt)) -> mark(tt)
   active(U61(tt, V)) -> mark(U62(isQid(V)))
   active(U62(tt)) -> mark(tt)
   active(U71(tt, V)) -> mark(U72(isNePal(V)))
   active(U72(tt)) -> mark(tt)
   active(and(tt, X)) -> mark(X)
   active(isList(V)) -> mark(U11(isPalListKind(V), V))
   active(isList(nil)) -> mark(tt)
   active(isList(__(V1, V2))) -> mark(U21(and(isPalListKind(V1), isPalListKind(V2)), V1, V2))
   active(isNeList(V)) -> mark(U31(isPalListKind(V), V))
   active(isNeList(__(V1, V2))) -> mark(U41(and(isPalListKind(V1), isPalListKind(V2)), V1, V2))
   active(isNeList(__(V1, V2))) -> mark(U51(and(isPalListKind(V1), isPalListKind(V2)), V1, V2))
   active(isNePal(V)) -> mark(U61(isPalListKind(V), V))
   active(isNePal(__(I, __(P, I)))) -> mark(and(and(isQid(I), isPalListKind(I)), and(isPal(P), isPalListKind(P))))
   active(isPal(V)) -> mark(U71(isPalListKind(V), V))
   active(isPal(nil)) -> mark(tt)
   active(isPalListKind(a)) -> mark(tt)
   active(isPalListKind(e)) -> mark(tt)
   active(isPalListKind(i)) -> mark(tt)
   active(isPalListKind(nil)) -> mark(tt)
   active(isPalListKind(o)) -> mark(tt)
   active(isPalListKind(u)) -> mark(tt)
   active(isPalListKind(__(V1, V2))) -> mark(and(isPalListKind(V1), isPalListKind(V2)))
   active(isQid(a)) -> mark(tt)
   active(isQid(e)) -> mark(tt)
   active(isQid(i)) -> mark(tt)
   active(isQid(o)) -> mark(tt)
   active(isQid(u)) -> mark(tt)
   mark(__(X1, X2)) -> active(__(mark(X1), mark(X2)))
   mark(nil) -> active(nil)
   mark(U11(X1, X2)) -> active(U11(mark(X1), X2))
   mark(tt) -> active(tt)
   mark(U12(X)) -> active(U12(mark(X)))
   mark(isNeList(X)) -> active(isNeList(X))
   mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3))
   mark(U22(X1, X2)) -> active(U22(mark(X1), X2))
   mark(isList(X)) -> active(isList(X))
   mark(U23(X)) -> active(U23(mark(X)))
   mark(U31(X1, X2)) -> active(U31(mark(X1), X2))
   mark(U32(X)) -> active(U32(mark(X)))
   mark(isQid(X)) -> active(isQid(X))
   mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3))
   mark(U42(X1, X2)) -> active(U42(mark(X1), X2))
   mark(U43(X)) -> active(U43(mark(X)))
   mark(U51(X1, X2, X3)) -> active(U51(mark(X1), X2, X3))
   mark(U52(X1, X2)) -> active(U52(mark(X1), X2))
   mark(U53(X)) -> active(U53(mark(X)))
   mark(U61(X1, X2)) -> active(U61(mark(X1), X2))
   mark(U62(X)) -> active(U62(mark(X)))
   mark(U71(X1, X2)) -> active(U71(mark(X1), X2))
   mark(U72(X)) -> active(U72(mark(X)))
   mark(isNePal(X)) -> active(isNePal(X))
   mark(and(X1, X2)) -> active(and(mark(X1), X2))
   mark(isPalListKind(X)) -> active(isPalListKind(X))
   mark(isPal(X)) -> active(isPal(X))
   mark(a) -> active(a)
   mark(e) -> active(e)
   mark(i) -> active(i)
   mark(o) -> active(o)
   mark(u) -> active(u)
   __(mark(X1), X2) -> __(X1, X2)
   __(X1, mark(X2)) -> __(X1, X2)
   __(active(X1), X2) -> __(X1, X2)
   __(X1, active(X2)) -> __(X1, X2)
   U11(mark(X1), X2) -> U11(X1, X2)
   U11(X1, mark(X2)) -> U11(X1, X2)
   U11(active(X1), X2) -> U11(X1, X2)
   U11(X1, active(X2)) -> U11(X1, X2)
   U12(mark(X)) -> U12(X)
   U12(active(X)) -> U12(X)
   isNeList(mark(X)) -> isNeList(X)
   isNeList(active(X)) -> isNeList(X)
   U21(mark(X1), X2, X3) -> U21(X1, X2, X3)
   U21(X1, mark(X2), X3) -> U21(X1, X2, X3)
   U21(X1, X2, mark(X3)) -> U21(X1, X2, X3)
   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
   U22(mark(X1), X2) -> U22(X1, X2)
   U22(X1, mark(X2)) -> U22(X1, X2)
   U22(active(X1), X2) -> U22(X1, X2)
   U22(X1, active(X2)) -> U22(X1, X2)
   isList(mark(X)) -> isList(X)
   isList(active(X)) -> isList(X)
   U23(mark(X)) -> U23(X)
   U23(active(X)) -> U23(X)
   U31(mark(X1), X2) -> U31(X1, X2)
   U31(X1, mark(X2)) -> U31(X1, X2)
   U31(active(X1), X2) -> U31(X1, X2)
   U31(X1, active(X2)) -> U31(X1, X2)
   U32(mark(X)) -> U32(X)
   U32(active(X)) -> U32(X)
   isQid(mark(X)) -> isQid(X)
   isQid(active(X)) -> isQid(X)
   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
   U42(mark(X1), X2) -> U42(X1, X2)
   U42(X1, mark(X2)) -> U42(X1, X2)
   U42(active(X1), X2) -> U42(X1, X2)
   U42(X1, active(X2)) -> U42(X1, X2)
   U43(mark(X)) -> U43(X)
   U43(active(X)) -> U43(X)
   U51(mark(X1), X2, X3) -> U51(X1, X2, X3)
   U51(X1, mark(X2), X3) -> U51(X1, X2, X3)
   U51(X1, X2, mark(X3)) -> U51(X1, X2, X3)
   U51(active(X1), X2, X3) -> U51(X1, X2, X3)
   U51(X1, active(X2), X3) -> U51(X1, X2, X3)
   U51(X1, X2, active(X3)) -> U51(X1, X2, X3)
   U52(mark(X1), X2) -> U52(X1, X2)
   U52(X1, mark(X2)) -> U52(X1, X2)
   U52(active(X1), X2) -> U52(X1, X2)
   U52(X1, active(X2)) -> U52(X1, X2)
   U53(mark(X)) -> U53(X)
   U53(active(X)) -> U53(X)
   U61(mark(X1), X2) -> U61(X1, X2)
   U61(X1, mark(X2)) -> U61(X1, X2)
   U61(active(X1), X2) -> U61(X1, X2)
   U61(X1, active(X2)) -> U61(X1, X2)
   U62(mark(X)) -> U62(X)
   U62(active(X)) -> U62(X)
   U71(mark(X1), X2) -> U71(X1, X2)
   U71(X1, mark(X2)) -> U71(X1, X2)
   U71(active(X1), X2) -> U71(X1, X2)
   U71(X1, active(X2)) -> U71(X1, X2)
   U72(mark(X)) -> U72(X)
   U72(active(X)) -> U72(X)
   isNePal(mark(X)) -> isNePal(X)
   isNePal(active(X)) -> isNePal(X)
   and(mark(X1), X2) -> and(X1, X2)
   and(X1, mark(X2)) -> and(X1, X2)
   and(active(X1), X2) -> and(X1, X2)
   and(X1, active(X2)) -> and(X1, X2)
   isPalListKind(mark(X)) -> isPalListKind(X)
   isPalListKind(active(X)) -> isPalListKind(X)
   isPal(mark(X)) -> isPal(X)
   isPal(active(X)) -> isPal(X)

The set Q consists of the following terms:

   active(__(__(x0, x1), x2))
   active(__(x0, nil))
   active(__(nil, x0))
   active(U11(tt, x0))
   active(U12(tt))
   active(U21(tt, x0, x1))
   active(U22(tt, x0))
   active(U23(tt))
   active(U31(tt, x0))
   active(U32(tt))
   active(U41(tt, x0, x1))
   active(U42(tt, x0))
   active(U43(tt))
   active(U51(tt, x0, x1))
   active(U52(tt, x0))
   active(U53(tt))
   active(U61(tt, x0))
   active(U62(tt))
   active(U71(tt, x0))
   active(U72(tt))
   active(and(tt, x0))
   active(isList(x0))
   active(isNeList(x0))
   active(isNePal(x0))
   active(isPal(x0))
   active(isPalListKind(a))
   active(isPalListKind(e))
   active(isPalListKind(i))
   active(isPalListKind(nil))
   active(isPalListKind(o))
   active(isPalListKind(u))
   active(isPalListKind(__(x0, x1)))
   active(isQid(a))
   active(isQid(e))
   active(isQid(i))
   active(isQid(o))
   active(isQid(u))
   mark(__(x0, x1))
   mark(nil)
   mark(U11(x0, x1))
   mark(tt)
   mark(U12(x0))
   mark(isNeList(x0))
   mark(U21(x0, x1, x2))
   mark(U22(x0, x1))
   mark(isList(x0))
   mark(U23(x0))
   mark(U31(x0, x1))
   mark(U32(x0))
   mark(isQid(x0))
   mark(U41(x0, x1, x2))
   mark(U42(x0, x1))
   mark(U43(x0))
   mark(U51(x0, x1, x2))
   mark(U52(x0, x1))
   mark(U53(x0))
   mark(U61(x0, x1))
   mark(U62(x0))
   mark(U71(x0, x1))
   mark(U72(x0))
   mark(isNePal(x0))
   mark(and(x0, x1))
   mark(isPalListKind(x0))
   mark(isPal(x0))
   mark(a)
   mark(e)
   mark(i)
   mark(o)
   mark(u)
   __(mark(x0), x1)
   __(x0, mark(x1))
   __(active(x0), x1)
   __(x0, active(x1))
   U11(mark(x0), x1)
   U11(x0, mark(x1))
   U11(active(x0), x1)
   U11(x0, active(x1))
   U12(mark(x0))
   U12(active(x0))
   isNeList(mark(x0))
   isNeList(active(x0))
   U21(mark(x0), x1, x2)
   U21(x0, mark(x1), x2)
   U21(x0, x1, mark(x2))
   U21(active(x0), x1, x2)
   U21(x0, active(x1), x2)
   U21(x0, x1, active(x2))
   U22(mark(x0), x1)
   U22(x0, mark(x1))
   U22(active(x0), x1)
   U22(x0, active(x1))
   isList(mark(x0))
   isList(active(x0))
   U23(mark(x0))
   U23(active(x0))
   U31(mark(x0), x1)
   U31(x0, mark(x1))
   U31(active(x0), x1)
   U31(x0, active(x1))
   U32(mark(x0))
   U32(active(x0))
   isQid(mark(x0))
   isQid(active(x0))
   U41(mark(x0), x1, x2)
   U41(x0, mark(x1), x2)
   U41(x0, x1, mark(x2))
   U41(active(x0), x1, x2)
   U41(x0, active(x1), x2)
   U41(x0, x1, active(x2))
   U42(mark(x0), x1)
   U42(x0, mark(x1))
   U42(active(x0), x1)
   U42(x0, active(x1))
   U43(mark(x0))
   U43(active(x0))
   U51(mark(x0), x1, x2)
   U51(x0, mark(x1), x2)
   U51(x0, x1, mark(x2))
   U51(active(x0), x1, x2)
   U51(x0, active(x1), x2)
   U51(x0, x1, active(x2))
   U52(mark(x0), x1)
   U52(x0, mark(x1))
   U52(active(x0), x1)
   U52(x0, active(x1))
   U53(mark(x0))
   U53(active(x0))
   U61(mark(x0), x1)
   U61(x0, mark(x1))
   U61(active(x0), x1)
   U61(x0, active(x1))
   U62(mark(x0))
   U62(active(x0))
   U71(mark(x0), x1)
   U71(x0, mark(x1))
   U71(active(x0), x1)
   U71(x0, active(x1))
   U72(mark(x0))
   U72(active(x0))
   isNePal(mark(x0))
   isNePal(active(x0))
   and(mark(x0), x1)
   and(x0, mark(x1))
   and(active(x0), x1)
   and(x0, active(x1))
   isPalListKind(mark(x0))
   isPalListKind(active(x0))
   isPal(mark(x0))
   isPal(active(x0))


----------------------------------------

(1) QTRSRRRProof (EQUIVALENT)
Used ordering:
active/1)YES(
__/2(YES,YES)
mark/1)YES(
nil/0)
U11/2(YES,YES)
tt/0)
U12/1)YES(
isNeList/1(YES)
U21/3(YES,YES,YES)
U22/2(YES,YES)
isList/1(YES)
U23/1)YES(
U31/2(YES,YES)
U32/1)YES(
isQid/1)YES(
U41/3(YES,YES,YES)
U42/2(YES,YES)
U43/1)YES(
U51/3(YES,YES,YES)
U52/2(YES,YES)
U53/1)YES(
U61/2(YES,YES)
U62/1)YES(
U71/2(YES,YES)
U72/1)YES(
isNePal/1(YES)
and/2(YES,YES)
isPalListKind/1)YES(
isPal/1(YES)
a/0)
e/0)
i/0)
o/0)
u/0)

Quasi precedence:
___2 > U21_3 > U22_2 > [isList_1, U52_2] > [U11_2, isNeList_1, U42_2] > U31_2
___2 > U41_3 > [isList_1, U52_2] > [U11_2, isNeList_1, U42_2] > U31_2
___2 > U51_3 > [isList_1, U52_2] > [U11_2, isNeList_1, U42_2] > U31_2
___2 > and_2
___2 > isPal_1 > U71_2 > isNePal_1 > U61_2
nil > [tt, e, i, u] > U22_2 > [isList_1, U52_2] > [U11_2, isNeList_1, U42_2] > U31_2
nil > [tt, e, i, u] > isNePal_1 > U61_2
a > [tt, e, i, u] > U22_2 > [isList_1, U52_2] > [U11_2, isNeList_1, U42_2] > U31_2
a > [tt, e, i, u] > isNePal_1 > U61_2
o > [tt, e, i, u] > U22_2 > [isList_1, U52_2] > [U11_2, isNeList_1, U42_2] > U31_2
o > [tt, e, i, u] > isNePal_1 > U61_2


Status:
___2: [1,2]
nil: multiset status
U11_2: multiset status
tt: multiset status
isNeList_1: multiset status
U21_3: [1,2,3]
U22_2: multiset status
isList_1: multiset status
U31_2: multiset status
U41_3: [1,3,2]
U42_2: multiset status
U51_3: [1,2,3]
U52_2: multiset status
U61_2: multiset status
U71_2: multiset status
isNePal_1: multiset status
and_2: [2,1]
isPal_1: multiset status
a: multiset status
e: multiset status
i: multiset status
o: multiset status
u: multiset status

With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z)))
   active(__(X, nil)) -> mark(X)
   active(__(nil, X)) -> mark(X)
   active(U11(tt, V)) -> mark(U12(isNeList(V)))
   active(U21(tt, V1, V2)) -> mark(U22(isList(V1), V2))
   active(U22(tt, V2)) -> mark(U23(isList(V2)))
   active(U31(tt, V)) -> mark(U32(isQid(V)))
   active(U41(tt, V1, V2)) -> mark(U42(isList(V1), V2))
   active(U42(tt, V2)) -> mark(U43(isNeList(V2)))
   active(U51(tt, V1, V2)) -> mark(U52(isNeList(V1), V2))
   active(U52(tt, V2)) -> mark(U53(isList(V2)))
   active(U61(tt, V)) -> mark(U62(isQid(V)))
   active(U71(tt, V)) -> mark(U72(isNePal(V)))
   active(and(tt, X)) -> mark(X)
   active(isList(V)) -> mark(U11(isPalListKind(V), V))
   active(isList(nil)) -> mark(tt)
   active(isList(__(V1, V2))) -> mark(U21(and(isPalListKind(V1), isPalListKind(V2)), V1, V2))
   active(isNeList(V)) -> mark(U31(isPalListKind(V), V))
   active(isNeList(__(V1, V2))) -> mark(U41(and(isPalListKind(V1), isPalListKind(V2)), V1, V2))
   active(isNeList(__(V1, V2))) -> mark(U51(and(isPalListKind(V1), isPalListKind(V2)), V1, V2))
   active(isNePal(V)) -> mark(U61(isPalListKind(V), V))
   active(isNePal(__(I, __(P, I)))) -> mark(and(and(isQid(I), isPalListKind(I)), and(isPal(P), isPalListKind(P))))
   active(isPal(V)) -> mark(U71(isPalListKind(V), V))
   active(isPal(nil)) -> mark(tt)
   active(isPalListKind(a)) -> mark(tt)
   active(isPalListKind(nil)) -> mark(tt)
   active(isPalListKind(o)) -> mark(tt)
   active(isPalListKind(__(V1, V2))) -> mark(and(isPalListKind(V1), isPalListKind(V2)))
   active(isQid(a)) -> mark(tt)
   active(isQid(o)) -> mark(tt)




----------------------------------------

(2)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   active(U12(tt)) -> mark(tt)
   active(U23(tt)) -> mark(tt)
   active(U32(tt)) -> mark(tt)
   active(U43(tt)) -> mark(tt)
   active(U53(tt)) -> mark(tt)
   active(U62(tt)) -> mark(tt)
   active(U72(tt)) -> mark(tt)
   active(isPalListKind(e)) -> mark(tt)
   active(isPalListKind(i)) -> mark(tt)
   active(isPalListKind(u)) -> mark(tt)
   active(isQid(e)) -> mark(tt)
   active(isQid(i)) -> mark(tt)
   active(isQid(u)) -> mark(tt)
   mark(__(X1, X2)) -> active(__(mark(X1), mark(X2)))
   mark(nil) -> active(nil)
   mark(U11(X1, X2)) -> active(U11(mark(X1), X2))
   mark(tt) -> active(tt)
   mark(U12(X)) -> active(U12(mark(X)))
   mark(isNeList(X)) -> active(isNeList(X))
   mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3))
   mark(U22(X1, X2)) -> active(U22(mark(X1), X2))
   mark(isList(X)) -> active(isList(X))
   mark(U23(X)) -> active(U23(mark(X)))
   mark(U31(X1, X2)) -> active(U31(mark(X1), X2))
   mark(U32(X)) -> active(U32(mark(X)))
   mark(isQid(X)) -> active(isQid(X))
   mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3))
   mark(U42(X1, X2)) -> active(U42(mark(X1), X2))
   mark(U43(X)) -> active(U43(mark(X)))
   mark(U51(X1, X2, X3)) -> active(U51(mark(X1), X2, X3))
   mark(U52(X1, X2)) -> active(U52(mark(X1), X2))
   mark(U53(X)) -> active(U53(mark(X)))
   mark(U61(X1, X2)) -> active(U61(mark(X1), X2))
   mark(U62(X)) -> active(U62(mark(X)))
   mark(U71(X1, X2)) -> active(U71(mark(X1), X2))
   mark(U72(X)) -> active(U72(mark(X)))
   mark(isNePal(X)) -> active(isNePal(X))
   mark(and(X1, X2)) -> active(and(mark(X1), X2))
   mark(isPalListKind(X)) -> active(isPalListKind(X))
   mark(isPal(X)) -> active(isPal(X))
   mark(a) -> active(a)
   mark(e) -> active(e)
   mark(i) -> active(i)
   mark(o) -> active(o)
   mark(u) -> active(u)
   __(mark(X1), X2) -> __(X1, X2)
   __(X1, mark(X2)) -> __(X1, X2)
   __(active(X1), X2) -> __(X1, X2)
   __(X1, active(X2)) -> __(X1, X2)
   U11(mark(X1), X2) -> U11(X1, X2)
   U11(X1, mark(X2)) -> U11(X1, X2)
   U11(active(X1), X2) -> U11(X1, X2)
   U11(X1, active(X2)) -> U11(X1, X2)
   U12(mark(X)) -> U12(X)
   U12(active(X)) -> U12(X)
   isNeList(mark(X)) -> isNeList(X)
   isNeList(active(X)) -> isNeList(X)
   U21(mark(X1), X2, X3) -> U21(X1, X2, X3)
   U21(X1, mark(X2), X3) -> U21(X1, X2, X3)
   U21(X1, X2, mark(X3)) -> U21(X1, X2, X3)
   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
   U22(mark(X1), X2) -> U22(X1, X2)
   U22(X1, mark(X2)) -> U22(X1, X2)
   U22(active(X1), X2) -> U22(X1, X2)
   U22(X1, active(X2)) -> U22(X1, X2)
   isList(mark(X)) -> isList(X)
   isList(active(X)) -> isList(X)
   U23(mark(X)) -> U23(X)
   U23(active(X)) -> U23(X)
   U31(mark(X1), X2) -> U31(X1, X2)
   U31(X1, mark(X2)) -> U31(X1, X2)
   U31(active(X1), X2) -> U31(X1, X2)
   U31(X1, active(X2)) -> U31(X1, X2)
   U32(mark(X)) -> U32(X)
   U32(active(X)) -> U32(X)
   isQid(mark(X)) -> isQid(X)
   isQid(active(X)) -> isQid(X)
   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
   U42(mark(X1), X2) -> U42(X1, X2)
   U42(X1, mark(X2)) -> U42(X1, X2)
   U42(active(X1), X2) -> U42(X1, X2)
   U42(X1, active(X2)) -> U42(X1, X2)
   U43(mark(X)) -> U43(X)
   U43(active(X)) -> U43(X)
   U51(mark(X1), X2, X3) -> U51(X1, X2, X3)
   U51(X1, mark(X2), X3) -> U51(X1, X2, X3)
   U51(X1, X2, mark(X3)) -> U51(X1, X2, X3)
   U51(active(X1), X2, X3) -> U51(X1, X2, X3)
   U51(X1, active(X2), X3) -> U51(X1, X2, X3)
   U51(X1, X2, active(X3)) -> U51(X1, X2, X3)
   U52(mark(X1), X2) -> U52(X1, X2)
   U52(X1, mark(X2)) -> U52(X1, X2)
   U52(active(X1), X2) -> U52(X1, X2)
   U52(X1, active(X2)) -> U52(X1, X2)
   U53(mark(X)) -> U53(X)
   U53(active(X)) -> U53(X)
   U61(mark(X1), X2) -> U61(X1, X2)
   U61(X1, mark(X2)) -> U61(X1, X2)
   U61(active(X1), X2) -> U61(X1, X2)
   U61(X1, active(X2)) -> U61(X1, X2)
   U62(mark(X)) -> U62(X)
   U62(active(X)) -> U62(X)
   U71(mark(X1), X2) -> U71(X1, X2)
   U71(X1, mark(X2)) -> U71(X1, X2)
   U71(active(X1), X2) -> U71(X1, X2)
   U71(X1, active(X2)) -> U71(X1, X2)
   U72(mark(X)) -> U72(X)
   U72(active(X)) -> U72(X)
   isNePal(mark(X)) -> isNePal(X)
   isNePal(active(X)) -> isNePal(X)
   and(mark(X1), X2) -> and(X1, X2)
   and(X1, mark(X2)) -> and(X1, X2)
   and(active(X1), X2) -> and(X1, X2)
   and(X1, active(X2)) -> and(X1, X2)
   isPalListKind(mark(X)) -> isPalListKind(X)
   isPalListKind(active(X)) -> isPalListKind(X)
   isPal(mark(X)) -> isPal(X)
   isPal(active(X)) -> isPal(X)

The set Q consists of the following terms:

   active(__(__(x0, x1), x2))
   active(__(x0, nil))
   active(__(nil, x0))
   active(U11(tt, x0))
   active(U12(tt))
   active(U21(tt, x0, x1))
   active(U22(tt, x0))
   active(U23(tt))
   active(U31(tt, x0))
   active(U32(tt))
   active(U41(tt, x0, x1))
   active(U42(tt, x0))
   active(U43(tt))
   active(U51(tt, x0, x1))
   active(U52(tt, x0))
   active(U53(tt))
   active(U61(tt, x0))
   active(U62(tt))
   active(U71(tt, x0))
   active(U72(tt))
   active(and(tt, x0))
   active(isList(x0))
   active(isNeList(x0))
   active(isNePal(x0))
   active(isPal(x0))
   active(isPalListKind(a))
   active(isPalListKind(e))
   active(isPalListKind(i))
   active(isPalListKind(nil))
   active(isPalListKind(o))
   active(isPalListKind(u))
   active(isPalListKind(__(x0, x1)))
   active(isQid(a))
   active(isQid(e))
   active(isQid(i))
   active(isQid(o))
   active(isQid(u))
   mark(__(x0, x1))
   mark(nil)
   mark(U11(x0, x1))
   mark(tt)
   mark(U12(x0))
   mark(isNeList(x0))
   mark(U21(x0, x1, x2))
   mark(U22(x0, x1))
   mark(isList(x0))
   mark(U23(x0))
   mark(U31(x0, x1))
   mark(U32(x0))
   mark(isQid(x0))
   mark(U41(x0, x1, x2))
   mark(U42(x0, x1))
   mark(U43(x0))
   mark(U51(x0, x1, x2))
   mark(U52(x0, x1))
   mark(U53(x0))
   mark(U61(x0, x1))
   mark(U62(x0))
   mark(U71(x0, x1))
   mark(U72(x0))
   mark(isNePal(x0))
   mark(and(x0, x1))
   mark(isPalListKind(x0))
   mark(isPal(x0))
   mark(a)
   mark(e)
   mark(i)
   mark(o)
   mark(u)
   __(mark(x0), x1)
   __(x0, mark(x1))
   __(active(x0), x1)
   __(x0, active(x1))
   U11(mark(x0), x1)
   U11(x0, mark(x1))
   U11(active(x0), x1)
   U11(x0, active(x1))
   U12(mark(x0))
   U12(active(x0))
   isNeList(mark(x0))
   isNeList(active(x0))
   U21(mark(x0), x1, x2)
   U21(x0, mark(x1), x2)
   U21(x0, x1, mark(x2))
   U21(active(x0), x1, x2)
   U21(x0, active(x1), x2)
   U21(x0, x1, active(x2))
   U22(mark(x0), x1)
   U22(x0, mark(x1))
   U22(active(x0), x1)
   U22(x0, active(x1))
   isList(mark(x0))
   isList(active(x0))
   U23(mark(x0))
   U23(active(x0))
   U31(mark(x0), x1)
   U31(x0, mark(x1))
   U31(active(x0), x1)
   U31(x0, active(x1))
   U32(mark(x0))
   U32(active(x0))
   isQid(mark(x0))
   isQid(active(x0))
   U41(mark(x0), x1, x2)
   U41(x0, mark(x1), x2)
   U41(x0, x1, mark(x2))
   U41(active(x0), x1, x2)
   U41(x0, active(x1), x2)
   U41(x0, x1, active(x2))
   U42(mark(x0), x1)
   U42(x0, mark(x1))
   U42(active(x0), x1)
   U42(x0, active(x1))
   U43(mark(x0))
   U43(active(x0))
   U51(mark(x0), x1, x2)
   U51(x0, mark(x1), x2)
   U51(x0, x1, mark(x2))
   U51(active(x0), x1, x2)
   U51(x0, active(x1), x2)
   U51(x0, x1, active(x2))
   U52(mark(x0), x1)
   U52(x0, mark(x1))
   U52(active(x0), x1)
   U52(x0, active(x1))
   U53(mark(x0))
   U53(active(x0))
   U61(mark(x0), x1)
   U61(x0, mark(x1))
   U61(active(x0), x1)
   U61(x0, active(x1))
   U62(mark(x0))
   U62(active(x0))
   U71(mark(x0), x1)
   U71(x0, mark(x1))
   U71(active(x0), x1)
   U71(x0, active(x1))
   U72(mark(x0))
   U72(active(x0))
   isNePal(mark(x0))
   isNePal(active(x0))
   and(mark(x0), x1)
   and(x0, mark(x1))
   and(active(x0), x1)
   and(x0, active(x1))
   isPalListKind(mark(x0))
   isPalListKind(active(x0))
   isPal(mark(x0))
   isPal(active(x0))


----------------------------------------

(3) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(U11(x_1, x_2)) = 1 + x_1 + x_2
   POL(U12(x_1)) = 1 + x_1
   POL(U21(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3
   POL(U22(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(U23(x_1)) = 1 + 2*x_1
   POL(U31(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(U32(x_1)) = 1 + 2*x_1
   POL(U41(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3
   POL(U42(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(U43(x_1)) = 1 + x_1
   POL(U51(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3
   POL(U52(x_1, x_2)) = 2 + x_1 + 2*x_2
   POL(U53(x_1)) = 1 + 2*x_1
   POL(U61(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(U62(x_1)) = 1 + 2*x_1
   POL(U71(x_1, x_2)) = 1 + x_1 + 2*x_2
   POL(U72(x_1)) = 1 + 2*x_1
   POL(__(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(a) = 1
   POL(active(x_1)) = x_1
   POL(and(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(e) = 1
   POL(i) = 1
   POL(isList(x_1)) = 1 + 2*x_1
   POL(isNeList(x_1)) = 1 + 2*x_1
   POL(isNePal(x_1)) = 1 + 2*x_1
   POL(isPal(x_1)) = 1 + 2*x_1
   POL(isPalListKind(x_1)) = 1 + 2*x_1
   POL(isQid(x_1)) = 1 + 2*x_1
   POL(mark(x_1)) = 2*x_1
   POL(nil) = 2
   POL(o) = 1
   POL(tt) = 1
   POL(u) = 1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   active(U23(tt)) -> mark(tt)
   active(U32(tt)) -> mark(tt)
   active(U53(tt)) -> mark(tt)
   active(U62(tt)) -> mark(tt)
   active(U72(tt)) -> mark(tt)
   active(isPalListKind(e)) -> mark(tt)
   active(isPalListKind(i)) -> mark(tt)
   active(isPalListKind(u)) -> mark(tt)
   active(isQid(e)) -> mark(tt)
   active(isQid(i)) -> mark(tt)
   active(isQid(u)) -> mark(tt)
   mark(__(X1, X2)) -> active(__(mark(X1), mark(X2)))
   mark(nil) -> active(nil)
   mark(U11(X1, X2)) -> active(U11(mark(X1), X2))
   mark(tt) -> active(tt)
   mark(U12(X)) -> active(U12(mark(X)))
   mark(isNeList(X)) -> active(isNeList(X))
   mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3))
   mark(U22(X1, X2)) -> active(U22(mark(X1), X2))
   mark(isList(X)) -> active(isList(X))
   mark(U23(X)) -> active(U23(mark(X)))
   mark(U31(X1, X2)) -> active(U31(mark(X1), X2))
   mark(U32(X)) -> active(U32(mark(X)))
   mark(isQid(X)) -> active(isQid(X))
   mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3))
   mark(U42(X1, X2)) -> active(U42(mark(X1), X2))
   mark(U43(X)) -> active(U43(mark(X)))
   mark(U51(X1, X2, X3)) -> active(U51(mark(X1), X2, X3))
   mark(U52(X1, X2)) -> active(U52(mark(X1), X2))
   mark(U53(X)) -> active(U53(mark(X)))
   mark(U61(X1, X2)) -> active(U61(mark(X1), X2))
   mark(U62(X)) -> active(U62(mark(X)))
   mark(U71(X1, X2)) -> active(U71(mark(X1), X2))
   mark(U72(X)) -> active(U72(mark(X)))
   mark(isNePal(X)) -> active(isNePal(X))
   mark(and(X1, X2)) -> active(and(mark(X1), X2))
   mark(isPalListKind(X)) -> active(isPalListKind(X))
   mark(isPal(X)) -> active(isPal(X))
   mark(a) -> active(a)
   mark(e) -> active(e)
   mark(i) -> active(i)
   mark(o) -> active(o)
   mark(u) -> active(u)




----------------------------------------

(4)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   active(U12(tt)) -> mark(tt)
   active(U43(tt)) -> mark(tt)
   __(mark(X1), X2) -> __(X1, X2)
   __(X1, mark(X2)) -> __(X1, X2)
   __(active(X1), X2) -> __(X1, X2)
   __(X1, active(X2)) -> __(X1, X2)
   U11(mark(X1), X2) -> U11(X1, X2)
   U11(X1, mark(X2)) -> U11(X1, X2)
   U11(active(X1), X2) -> U11(X1, X2)
   U11(X1, active(X2)) -> U11(X1, X2)
   U12(mark(X)) -> U12(X)
   U12(active(X)) -> U12(X)
   isNeList(mark(X)) -> isNeList(X)
   isNeList(active(X)) -> isNeList(X)
   U21(mark(X1), X2, X3) -> U21(X1, X2, X3)
   U21(X1, mark(X2), X3) -> U21(X1, X2, X3)
   U21(X1, X2, mark(X3)) -> U21(X1, X2, X3)
   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
   U22(mark(X1), X2) -> U22(X1, X2)
   U22(X1, mark(X2)) -> U22(X1, X2)
   U22(active(X1), X2) -> U22(X1, X2)
   U22(X1, active(X2)) -> U22(X1, X2)
   isList(mark(X)) -> isList(X)
   isList(active(X)) -> isList(X)
   U23(mark(X)) -> U23(X)
   U23(active(X)) -> U23(X)
   U31(mark(X1), X2) -> U31(X1, X2)
   U31(X1, mark(X2)) -> U31(X1, X2)
   U31(active(X1), X2) -> U31(X1, X2)
   U31(X1, active(X2)) -> U31(X1, X2)
   U32(mark(X)) -> U32(X)
   U32(active(X)) -> U32(X)
   isQid(mark(X)) -> isQid(X)
   isQid(active(X)) -> isQid(X)
   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
   U42(mark(X1), X2) -> U42(X1, X2)
   U42(X1, mark(X2)) -> U42(X1, X2)
   U42(active(X1), X2) -> U42(X1, X2)
   U42(X1, active(X2)) -> U42(X1, X2)
   U43(mark(X)) -> U43(X)
   U43(active(X)) -> U43(X)
   U51(mark(X1), X2, X3) -> U51(X1, X2, X3)
   U51(X1, mark(X2), X3) -> U51(X1, X2, X3)
   U51(X1, X2, mark(X3)) -> U51(X1, X2, X3)
   U51(active(X1), X2, X3) -> U51(X1, X2, X3)
   U51(X1, active(X2), X3) -> U51(X1, X2, X3)
   U51(X1, X2, active(X3)) -> U51(X1, X2, X3)
   U52(mark(X1), X2) -> U52(X1, X2)
   U52(X1, mark(X2)) -> U52(X1, X2)
   U52(active(X1), X2) -> U52(X1, X2)
   U52(X1, active(X2)) -> U52(X1, X2)
   U53(mark(X)) -> U53(X)
   U53(active(X)) -> U53(X)
   U61(mark(X1), X2) -> U61(X1, X2)
   U61(X1, mark(X2)) -> U61(X1, X2)
   U61(active(X1), X2) -> U61(X1, X2)
   U61(X1, active(X2)) -> U61(X1, X2)
   U62(mark(X)) -> U62(X)
   U62(active(X)) -> U62(X)
   U71(mark(X1), X2) -> U71(X1, X2)
   U71(X1, mark(X2)) -> U71(X1, X2)
   U71(active(X1), X2) -> U71(X1, X2)
   U71(X1, active(X2)) -> U71(X1, X2)
   U72(mark(X)) -> U72(X)
   U72(active(X)) -> U72(X)
   isNePal(mark(X)) -> isNePal(X)
   isNePal(active(X)) -> isNePal(X)
   and(mark(X1), X2) -> and(X1, X2)
   and(X1, mark(X2)) -> and(X1, X2)
   and(active(X1), X2) -> and(X1, X2)
   and(X1, active(X2)) -> and(X1, X2)
   isPalListKind(mark(X)) -> isPalListKind(X)
   isPalListKind(active(X)) -> isPalListKind(X)
   isPal(mark(X)) -> isPal(X)
   isPal(active(X)) -> isPal(X)

The set Q consists of the following terms:

   active(__(__(x0, x1), x2))
   active(__(x0, nil))
   active(__(nil, x0))
   active(U11(tt, x0))
   active(U12(tt))
   active(U21(tt, x0, x1))
   active(U22(tt, x0))
   active(U23(tt))
   active(U31(tt, x0))
   active(U32(tt))
   active(U41(tt, x0, x1))
   active(U42(tt, x0))
   active(U43(tt))
   active(U51(tt, x0, x1))
   active(U52(tt, x0))
   active(U53(tt))
   active(U61(tt, x0))
   active(U62(tt))
   active(U71(tt, x0))
   active(U72(tt))
   active(and(tt, x0))
   active(isList(x0))
   active(isNeList(x0))
   active(isNePal(x0))
   active(isPal(x0))
   active(isPalListKind(a))
   active(isPalListKind(e))
   active(isPalListKind(i))
   active(isPalListKind(nil))
   active(isPalListKind(o))
   active(isPalListKind(u))
   active(isPalListKind(__(x0, x1)))
   active(isQid(a))
   active(isQid(e))
   active(isQid(i))
   active(isQid(o))
   active(isQid(u))
   mark(__(x0, x1))
   mark(nil)
   mark(U11(x0, x1))
   mark(tt)
   mark(U12(x0))
   mark(isNeList(x0))
   mark(U21(x0, x1, x2))
   mark(U22(x0, x1))
   mark(isList(x0))
   mark(U23(x0))
   mark(U31(x0, x1))
   mark(U32(x0))
   mark(isQid(x0))
   mark(U41(x0, x1, x2))
   mark(U42(x0, x1))
   mark(U43(x0))
   mark(U51(x0, x1, x2))
   mark(U52(x0, x1))
   mark(U53(x0))
   mark(U61(x0, x1))
   mark(U62(x0))
   mark(U71(x0, x1))
   mark(U72(x0))
   mark(isNePal(x0))
   mark(and(x0, x1))
   mark(isPalListKind(x0))
   mark(isPal(x0))
   mark(a)
   mark(e)
   mark(i)
   mark(o)
   mark(u)
   __(mark(x0), x1)
   __(x0, mark(x1))
   __(active(x0), x1)
   __(x0, active(x1))
   U11(mark(x0), x1)
   U11(x0, mark(x1))
   U11(active(x0), x1)
   U11(x0, active(x1))
   U12(mark(x0))
   U12(active(x0))
   isNeList(mark(x0))
   isNeList(active(x0))
   U21(mark(x0), x1, x2)
   U21(x0, mark(x1), x2)
   U21(x0, x1, mark(x2))
   U21(active(x0), x1, x2)
   U21(x0, active(x1), x2)
   U21(x0, x1, active(x2))
   U22(mark(x0), x1)
   U22(x0, mark(x1))
   U22(active(x0), x1)
   U22(x0, active(x1))
   isList(mark(x0))
   isList(active(x0))
   U23(mark(x0))
   U23(active(x0))
   U31(mark(x0), x1)
   U31(x0, mark(x1))
   U31(active(x0), x1)
   U31(x0, active(x1))
   U32(mark(x0))
   U32(active(x0))
   isQid(mark(x0))
   isQid(active(x0))
   U41(mark(x0), x1, x2)
   U41(x0, mark(x1), x2)
   U41(x0, x1, mark(x2))
   U41(active(x0), x1, x2)
   U41(x0, active(x1), x2)
   U41(x0, x1, active(x2))
   U42(mark(x0), x1)
   U42(x0, mark(x1))
   U42(active(x0), x1)
   U42(x0, active(x1))
   U43(mark(x0))
   U43(active(x0))
   U51(mark(x0), x1, x2)
   U51(x0, mark(x1), x2)
   U51(x0, x1, mark(x2))
   U51(active(x0), x1, x2)
   U51(x0, active(x1), x2)
   U51(x0, x1, active(x2))
   U52(mark(x0), x1)
   U52(x0, mark(x1))
   U52(active(x0), x1)
   U52(x0, active(x1))
   U53(mark(x0))
   U53(active(x0))
   U61(mark(x0), x1)
   U61(x0, mark(x1))
   U61(active(x0), x1)
   U61(x0, active(x1))
   U62(mark(x0))
   U62(active(x0))
   U71(mark(x0), x1)
   U71(x0, mark(x1))
   U71(active(x0), x1)
   U71(x0, active(x1))
   U72(mark(x0))
   U72(active(x0))
   isNePal(mark(x0))
   isNePal(active(x0))
   and(mark(x0), x1)
   and(x0, mark(x1))
   and(active(x0), x1)
   and(x0, active(x1))
   isPalListKind(mark(x0))
   isPalListKind(active(x0))
   isPal(mark(x0))
   isPal(active(x0))


----------------------------------------

(5) QTRSRRRProof (EQUIVALENT)
Used ordering:
Knuth-Bendix order [KBO] with precedence:active_1 > isPal_1 > isPalListKind_1 > and_2 > isNePal_1 > U72_1 > U71_2 > U62_1 > U61_2 > U53_1 > U52_2 > U51_3 > U42_2 > U41_3 > isQid_1 > U32_1 > U31_2 > U23_1 > isList_1 > U22_2 > U21_3 > isNeList_1 > U11_2 > ___2 > U43_1 > mark_1 > tt > U12_1

and weight map:

   tt=1
   active_1=0
   U12_1=1
   mark_1=1
   U43_1=1
   isNeList_1=1
   isList_1=1
   U23_1=1
   U32_1=1
   isQid_1=1
   U53_1=1
   U62_1=1
   U72_1=1
   isNePal_1=1
   isPalListKind_1=1
   isPal_1=1
   ___2=0
   U11_2=0
   U21_3=0
   U22_2=0
   U31_2=0
   U41_3=0
   U42_2=0
   U51_3=0
   U52_2=0
   U61_2=0
   U71_2=0
   and_2=0

The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   active(U12(tt)) -> mark(tt)
   active(U43(tt)) -> mark(tt)
   __(mark(X1), X2) -> __(X1, X2)
   __(X1, mark(X2)) -> __(X1, X2)
   __(active(X1), X2) -> __(X1, X2)
   __(X1, active(X2)) -> __(X1, X2)
   U11(mark(X1), X2) -> U11(X1, X2)
   U11(X1, mark(X2)) -> U11(X1, X2)
   U11(active(X1), X2) -> U11(X1, X2)
   U11(X1, active(X2)) -> U11(X1, X2)
   U12(mark(X)) -> U12(X)
   U12(active(X)) -> U12(X)
   isNeList(mark(X)) -> isNeList(X)
   isNeList(active(X)) -> isNeList(X)
   U21(mark(X1), X2, X3) -> U21(X1, X2, X3)
   U21(X1, mark(X2), X3) -> U21(X1, X2, X3)
   U21(X1, X2, mark(X3)) -> U21(X1, X2, X3)
   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
   U22(mark(X1), X2) -> U22(X1, X2)
   U22(X1, mark(X2)) -> U22(X1, X2)
   U22(active(X1), X2) -> U22(X1, X2)
   U22(X1, active(X2)) -> U22(X1, X2)
   isList(mark(X)) -> isList(X)
   isList(active(X)) -> isList(X)
   U23(mark(X)) -> U23(X)
   U23(active(X)) -> U23(X)
   U31(mark(X1), X2) -> U31(X1, X2)
   U31(X1, mark(X2)) -> U31(X1, X2)
   U31(active(X1), X2) -> U31(X1, X2)
   U31(X1, active(X2)) -> U31(X1, X2)
   U32(mark(X)) -> U32(X)
   U32(active(X)) -> U32(X)
   isQid(mark(X)) -> isQid(X)
   isQid(active(X)) -> isQid(X)
   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
   U42(mark(X1), X2) -> U42(X1, X2)
   U42(X1, mark(X2)) -> U42(X1, X2)
   U42(active(X1), X2) -> U42(X1, X2)
   U42(X1, active(X2)) -> U42(X1, X2)
   U43(mark(X)) -> U43(X)
   U43(active(X)) -> U43(X)
   U51(mark(X1), X2, X3) -> U51(X1, X2, X3)
   U51(X1, mark(X2), X3) -> U51(X1, X2, X3)
   U51(X1, X2, mark(X3)) -> U51(X1, X2, X3)
   U51(active(X1), X2, X3) -> U51(X1, X2, X3)
   U51(X1, active(X2), X3) -> U51(X1, X2, X3)
   U51(X1, X2, active(X3)) -> U51(X1, X2, X3)
   U52(mark(X1), X2) -> U52(X1, X2)
   U52(X1, mark(X2)) -> U52(X1, X2)
   U52(active(X1), X2) -> U52(X1, X2)
   U52(X1, active(X2)) -> U52(X1, X2)
   U53(mark(X)) -> U53(X)
   U53(active(X)) -> U53(X)
   U61(mark(X1), X2) -> U61(X1, X2)
   U61(X1, mark(X2)) -> U61(X1, X2)
   U61(active(X1), X2) -> U61(X1, X2)
   U61(X1, active(X2)) -> U61(X1, X2)
   U62(mark(X)) -> U62(X)
   U62(active(X)) -> U62(X)
   U71(mark(X1), X2) -> U71(X1, X2)
   U71(X1, mark(X2)) -> U71(X1, X2)
   U71(active(X1), X2) -> U71(X1, X2)
   U71(X1, active(X2)) -> U71(X1, X2)
   U72(mark(X)) -> U72(X)
   U72(active(X)) -> U72(X)
   isNePal(mark(X)) -> isNePal(X)
   isNePal(active(X)) -> isNePal(X)
   and(mark(X1), X2) -> and(X1, X2)
   and(X1, mark(X2)) -> and(X1, X2)
   and(active(X1), X2) -> and(X1, X2)
   and(X1, active(X2)) -> and(X1, X2)
   isPalListKind(mark(X)) -> isPalListKind(X)
   isPalListKind(active(X)) -> isPalListKind(X)
   isPal(mark(X)) -> isPal(X)
   isPal(active(X)) -> isPal(X)




----------------------------------------

(6)
Obligation:
Q restricted rewrite system:
R is empty.
The set Q consists of the following terms:

   active(__(__(x0, x1), x2))
   active(__(x0, nil))
   active(__(nil, x0))
   active(U11(tt, x0))
   active(U12(tt))
   active(U21(tt, x0, x1))
   active(U22(tt, x0))
   active(U23(tt))
   active(U31(tt, x0))
   active(U32(tt))
   active(U41(tt, x0, x1))
   active(U42(tt, x0))
   active(U43(tt))
   active(U51(tt, x0, x1))
   active(U52(tt, x0))
   active(U53(tt))
   active(U61(tt, x0))
   active(U62(tt))
   active(U71(tt, x0))
   active(U72(tt))
   active(and(tt, x0))
   active(isList(x0))
   active(isNeList(x0))
   active(isNePal(x0))
   active(isPal(x0))
   active(isPalListKind(a))
   active(isPalListKind(e))
   active(isPalListKind(i))
   active(isPalListKind(nil))
   active(isPalListKind(o))
   active(isPalListKind(u))
   active(isPalListKind(__(x0, x1)))
   active(isQid(a))
   active(isQid(e))
   active(isQid(i))
   active(isQid(o))
   active(isQid(u))
   mark(__(x0, x1))
   mark(nil)
   mark(U11(x0, x1))
   mark(tt)
   mark(U12(x0))
   mark(isNeList(x0))
   mark(U21(x0, x1, x2))
   mark(U22(x0, x1))
   mark(isList(x0))
   mark(U23(x0))
   mark(U31(x0, x1))
   mark(U32(x0))
   mark(isQid(x0))
   mark(U41(x0, x1, x2))
   mark(U42(x0, x1))
   mark(U43(x0))
   mark(U51(x0, x1, x2))
   mark(U52(x0, x1))
   mark(U53(x0))
   mark(U61(x0, x1))
   mark(U62(x0))
   mark(U71(x0, x1))
   mark(U72(x0))
   mark(isNePal(x0))
   mark(and(x0, x1))
   mark(isPalListKind(x0))
   mark(isPal(x0))
   mark(a)
   mark(e)
   mark(i)
   mark(o)
   mark(u)
   __(mark(x0), x1)
   __(x0, mark(x1))
   __(active(x0), x1)
   __(x0, active(x1))
   U11(mark(x0), x1)
   U11(x0, mark(x1))
   U11(active(x0), x1)
   U11(x0, active(x1))
   U12(mark(x0))
   U12(active(x0))
   isNeList(mark(x0))
   isNeList(active(x0))
   U21(mark(x0), x1, x2)
   U21(x0, mark(x1), x2)
   U21(x0, x1, mark(x2))
   U21(active(x0), x1, x2)
   U21(x0, active(x1), x2)
   U21(x0, x1, active(x2))
   U22(mark(x0), x1)
   U22(x0, mark(x1))
   U22(active(x0), x1)
   U22(x0, active(x1))
   isList(mark(x0))
   isList(active(x0))
   U23(mark(x0))
   U23(active(x0))
   U31(mark(x0), x1)
   U31(x0, mark(x1))
   U31(active(x0), x1)
   U31(x0, active(x1))
   U32(mark(x0))
   U32(active(x0))
   isQid(mark(x0))
   isQid(active(x0))
   U41(mark(x0), x1, x2)
   U41(x0, mark(x1), x2)
   U41(x0, x1, mark(x2))
   U41(active(x0), x1, x2)
   U41(x0, active(x1), x2)
   U41(x0, x1, active(x2))
   U42(mark(x0), x1)
   U42(x0, mark(x1))
   U42(active(x0), x1)
   U42(x0, active(x1))
   U43(mark(x0))
   U43(active(x0))
   U51(mark(x0), x1, x2)
   U51(x0, mark(x1), x2)
   U51(x0, x1, mark(x2))
   U51(active(x0), x1, x2)
   U51(x0, active(x1), x2)
   U51(x0, x1, active(x2))
   U52(mark(x0), x1)
   U52(x0, mark(x1))
   U52(active(x0), x1)
   U52(x0, active(x1))
   U53(mark(x0))
   U53(active(x0))
   U61(mark(x0), x1)
   U61(x0, mark(x1))
   U61(active(x0), x1)
   U61(x0, active(x1))
   U62(mark(x0))
   U62(active(x0))
   U71(mark(x0), x1)
   U71(x0, mark(x1))
   U71(active(x0), x1)
   U71(x0, active(x1))
   U72(mark(x0))
   U72(active(x0))
   isNePal(mark(x0))
   isNePal(active(x0))
   and(mark(x0), x1)
   and(x0, mark(x1))
   and(active(x0), x1)
   and(x0, active(x1))
   isPalListKind(mark(x0))
   isPalListKind(active(x0))
   isPal(mark(x0))
   isPal(active(x0))


----------------------------------------

(7) RisEmptyProof (EQUIVALENT)
The TRS R is empty. Hence, termination is trivially proven.
----------------------------------------

(8)
YES