YES

Problem 1: 

(VAR v_NonEmpty:S I:S P:S V:S V1:S V2:S X:S X1:S X2:S Y:S Z:S)
(RULES
__(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
__(nil,X:S) -> X:S
__(X:S,nil) -> X:S
__(X1:S,X2:S) -> n____(X1:S,X2:S)
a -> n__a
activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
activate(n__a) -> a
activate(n__e) -> e
activate(n__i) -> i
activate(n__isList(X:S)) -> isList(X:S)
activate(n__isNeList(X:S)) -> isNeList(X:S)
activate(n__isPal(X:S)) -> isPal(X:S)
activate(n__nil) -> nil
activate(n__o) -> o
activate(n__u) -> u
activate(X:S) -> X:S
and(tt,X:S) -> activate(X:S)
e -> n__e
i -> n__i
isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
isList(n__nil) -> tt
isList(V:S) -> isNeList(activate(V:S))
isList(X:S) -> n__isList(X:S)
isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
isNeList(V:S) -> isQid(activate(V:S))
isNeList(X:S) -> n__isNeList(X:S)
isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
isNePal(V:S) -> isQid(activate(V:S))
isPal(n__nil) -> tt
isPal(V:S) -> isNePal(activate(V:S))
isPal(X:S) -> n__isPal(X:S)
isQid(n__a) -> tt
isQid(n__e) -> tt
isQid(n__i) -> tt
isQid(n__o) -> tt
isQid(n__u) -> tt
nil -> n__nil
o -> n__o
u -> n__u
)

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 __#(__(X:S,Y:S),Z:S) -> __#(X:S,__(Y:S,Z:S))
 __#(__(X:S,Y:S),Z:S) -> __#(Y:S,Z:S)
 ACTIVATE(n____(X1:S,X2:S)) -> __#(X1:S,X2:S)
 ACTIVATE(n__a) -> A
 ACTIVATE(n__e) -> E
 ACTIVATE(n__i) -> I
 ACTIVATE(n__isList(X:S)) -> ISLIST(X:S)
 ACTIVATE(n__isNeList(X:S)) -> ISNELIST(X:S)
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 ACTIVATE(n__nil) -> NIL
 ACTIVATE(n__o) -> O
 ACTIVATE(n__u) -> U
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISLIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isList(activate(V2:S)))
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ACTIVATE(V:S)
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISNELIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> AND(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
 ISNELIST(V:S) -> ACTIVATE(V:S)
 ISNELIST(V:S) -> ISQID(activate(V:S))
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ISQID(activate(I:S))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISNEPAL(V:S) -> ISQID(activate(V:S))
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u

Problem 1: 

SCC Processor:
-> Pairs:
 __#(__(X:S,Y:S),Z:S) -> __#(X:S,__(Y:S,Z:S))
 __#(__(X:S,Y:S),Z:S) -> __#(Y:S,Z:S)
 ACTIVATE(n____(X1:S,X2:S)) -> __#(X1:S,X2:S)
 ACTIVATE(n__a) -> A
 ACTIVATE(n__e) -> E
 ACTIVATE(n__i) -> I
 ACTIVATE(n__isList(X:S)) -> ISLIST(X:S)
 ACTIVATE(n__isNeList(X:S)) -> ISNELIST(X:S)
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 ACTIVATE(n__nil) -> NIL
 ACTIVATE(n__o) -> O
 ACTIVATE(n__u) -> U
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISLIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isList(activate(V2:S)))
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ACTIVATE(V:S)
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISNELIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> AND(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
 ISNELIST(V:S) -> ACTIVATE(V:S)
 ISNELIST(V:S) -> ISQID(activate(V:S))
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ISQID(activate(I:S))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISNEPAL(V:S) -> ISQID(activate(V:S))
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 __#(__(X:S,Y:S),Z:S) -> __#(X:S,__(Y:S,Z:S))
 __#(__(X:S,Y:S),Z:S) -> __#(Y:S,Z:S)
->->-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->->Cycle:
->->-> Pairs:
 ACTIVATE(n__isList(X:S)) -> ISLIST(X:S)
 ACTIVATE(n__isNeList(X:S)) -> ISNELIST(X:S)
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISLIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isList(activate(V2:S)))
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ACTIVATE(V:S)
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISNELIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> AND(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
 ISNELIST(V:S) -> ACTIVATE(V:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
->->-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u


The problem is decomposed in 2 subproblems.

Problem 1.1: 

Subterm Processor:
-> Pairs:
 __#(__(X:S,Y:S),Z:S) -> __#(X:S,__(Y:S,Z:S))
 __#(__(X:S,Y:S),Z:S) -> __#(Y:S,Z:S)
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Projection:
 pi(__#) = 1

Problem 1.1: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Reduction Pair Processor:
-> Pairs:
 ACTIVATE(n__isList(X:S)) -> ISLIST(X:S)
 ACTIVATE(n__isNeList(X:S)) -> ISNELIST(X:S)
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISLIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isList(activate(V2:S)))
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ACTIVATE(V:S)
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISNELIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> AND(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
 ISNELIST(V:S) -> ACTIVATE(V:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
-> Usable rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[__](X1,X2) = 2.X1 + X2 + 2
[a] = 2
[activate](X) = X
[and](X1,X2) = X2 + 1
[e] = 2
[i] = 2
[isList](X) = X + 2
[isNeList](X) = X + 2
[isNePal](X) = X + 2
[isPal](X) = X + 2
[isQid](X) = X
[nil] = 0
[o] = 2
[u] = 2
[n____](X1,X2) = 2.X1 + X2 + 2
[n__a] = 2
[n__e] = 2
[n__i] = 2
[n__isList](X) = X + 2
[n__isNeList](X) = X + 2
[n__isPal](X) = X + 2
[n__nil] = 0
[n__o] = 2
[n__u] = 2
[tt] = 2
[ACTIVATE](X) = 2.X + 1
[AND](X1,X2) = 2.X2 + 2
[ISLIST](X) = 2.X + 2
[ISNELIST](X) = 2.X + 2
[ISNEPAL](X) = 2.X + 1
[ISPAL](X) = 2.X + 2

Problem 1.2: 

SCC Processor:
-> Pairs:
 ACTIVATE(n__isNeList(X:S)) -> ISNELIST(X:S)
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISLIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isList(activate(V2:S)))
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ACTIVATE(V:S)
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISNELIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> AND(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
 ISNELIST(V:S) -> ACTIVATE(V:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 ACTIVATE(n__isNeList(X:S)) -> ISNELIST(X:S)
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISLIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isList(activate(V2:S)))
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ACTIVATE(V:S)
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISNELIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> AND(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
 ISNELIST(V:S) -> ACTIVATE(V:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
->->-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u

Problem 1.2: 

Reduction Pair Processor:
-> Pairs:
 ACTIVATE(n__isNeList(X:S)) -> ISNELIST(X:S)
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISLIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isList(activate(V2:S)))
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ACTIVATE(V:S)
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISNELIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> AND(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
 ISNELIST(V:S) -> ACTIVATE(V:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
-> Usable rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[__](X1,X2) = 2.X1 + X2 + 2
[a] = 2
[activate](X) = X
[and](X1,X2) = 2.X1 + X2 + 1
[e] = 2
[i] = 2
[isList](X) = 2.X + 1
[isNeList](X) = 2.X + 1
[isNePal](X) = 2.X + 1
[isPal](X) = 2.X + 2
[isQid](X) = 2.X
[nil] = 0
[o] = 0
[u] = 2
[n____](X1,X2) = 2.X1 + X2 + 2
[n__a] = 2
[n__e] = 2
[n__i] = 2
[n__isList](X) = 2.X + 1
[n__isNeList](X) = 2.X + 1
[n__isPal](X) = 2.X + 2
[n__nil] = 0
[n__o] = 0
[n__u] = 2
[tt] = 0
[ACTIVATE](X) = X + 2
[AND](X1,X2) = 2.X1 + X2 + 2
[ISLIST](X) = 2.X + 2
[ISNELIST](X) = 2.X + 2
[ISNEPAL](X) = 2.X + 2
[ISPAL](X) = 2.X + 2

Problem 1.2: 

SCC Processor:
-> Pairs:
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISLIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISLIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isList(activate(V2:S)))
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ACTIVATE(V:S)
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V1:S)
 ISNELIST(n____(V1:S,V2:S)) -> ACTIVATE(V2:S)
 ISNELIST(n____(V1:S,V2:S)) -> AND(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> AND(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
 ISNELIST(V:S) -> ACTIVATE(V:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
->->-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->->Cycle:
->->-> Pairs:
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
->->-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u


The problem is decomposed in 2 subproblems.

Problem 1.2.1: 

Reduction Pair Processor:
-> Pairs:
 ACTIVATE(n__isPal(X:S)) -> ISPAL(X:S)
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
-> Usable rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[__](X1,X2) = 2.X1 + X2 + 2
[a] = 2
[activate](X) = X
[and](X1,X2) = 2.X1 + X2
[e] = 2
[i] = 0
[isList](X) = 2.X + 2
[isNeList](X) = 2.X + 2
[isNePal](X) = 2.X + 2
[isPal](X) = 2.X + 2
[isQid](X) = 2.X + 2
[nil] = 2
[o] = 1
[u] = 2
[n____](X1,X2) = 2.X1 + X2 + 2
[n__a] = 2
[n__e] = 2
[n__i] = 0
[n__isList](X) = 2.X + 2
[n__isNeList](X) = 2.X + 2
[n__isPal](X) = 2.X + 2
[n__nil] = 2
[n__o] = 1
[n__u] = 2
[tt] = 2
[ACTIVATE](X) = 2.X
[AND](X1,X2) = X1 + 2.X2 + 2
[ISNEPAL](X) = 2.X + 1
[ISPAL](X) = 2.X + 2

Problem 1.2.1: 

SCC Processor:
-> Pairs:
 AND(tt,X:S) -> ACTIVATE(X:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(I:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> ACTIVATE(P:S)
 ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPal(activate(P:S)))
 ISNEPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ACTIVATE(V:S)
 ISPAL(V:S) -> ISNEPAL(activate(V:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2.2: 

Reduction Pair Processor:
-> Pairs:
 ISLIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
-> Usable rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[__](X1,X2) = 2.X1 + X2 + 2
[a] = 2
[activate](X) = X
[and](X1,X2) = 2.X1 + X2 + 2
[e] = 2
[i] = 2
[isList](X) = 2.X
[isNeList](X) = 2.X
[isNePal](X) = 2.X
[isPal](X) = 2.X
[isQid](X) = 2.X
[nil] = 2
[o] = 1
[u] = 2
[n____](X1,X2) = 2.X1 + X2 + 2
[n__a] = 2
[n__e] = 2
[n__i] = 2
[n__isList](X) = 2.X
[n__isNeList](X) = 2.X
[n__isPal](X) = 2.X
[n__nil] = 2
[n__o] = 1
[n__u] = 2
[tt] = 1
[ISLIST](X) = 2.X + 2
[ISNELIST](X) = 2.X + 2

Problem 1.2.2: 

SCC Processor:
-> Pairs:
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
->->-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u

Problem 1.2.2: 

Reduction Pair Processor:
-> Pairs:
 ISLIST(V:S) -> ISNELIST(activate(V:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
-> Usable rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[__](X1,X2) = 2.X1 + X2 + 2
[a] = 2
[activate](X) = X
[and](X1,X2) = 2.X1 + X2
[e] = 2
[i] = 2
[isList](X) = 2.X + 2
[isNeList](X) = 2.X + 2
[isNePal](X) = 2.X + 2
[isPal](X) = 2.X + 2
[isQid](X) = 2.X + 2
[nil] = 2
[o] = 2
[u] = 2
[n____](X1,X2) = 2.X1 + X2 + 2
[n__a] = 2
[n__e] = 2
[n__i] = 2
[n__isList](X) = 2.X + 2
[n__isNeList](X) = 2.X + 2
[n__isPal](X) = 2.X + 2
[n__nil] = 2
[n__o] = 2
[n__u] = 2
[tt] = 2
[ISLIST](X) = 2.X + 2
[ISNELIST](X) = X + 1

Problem 1.2.2: 

SCC Processor:
-> Pairs:
 ISNELIST(n____(V1:S,V2:S)) -> ISLIST(activate(V1:S))
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
->->-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u

Problem 1.2.2: 

Reduction Pair Processor:
-> Pairs:
 ISNELIST(n____(V1:S,V2:S)) -> ISNELIST(activate(V1:S))
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
-> Usable rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[__](X1,X2) = 2.X1 + X2 + 2
[a] = 2
[activate](X) = 2.X + 1
[and](X1,X2) = 2.X2 + 1
[e] = 1
[i] = 1
[isList](X) = 1
[isNeList](X) = 1
[isNePal](X) = 1
[isPal](X) = 1
[isQid](X) = 1
[nil] = 2
[o] = 0
[u] = 2
[n____](X1,X2) = 2.X1 + X2 + 2
[n__a] = 2
[n__e] = 0
[n__i] = 0
[n__isList](X) = 0
[n__isNeList](X) = 0
[n__isPal](X) = 0
[n__nil] = 2
[n__o] = 0
[n__u] = 1
[tt] = 1
[ISNELIST](X) = X

Problem 1.2.2: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 __(__(X:S,Y:S),Z:S) -> __(X:S,__(Y:S,Z:S))
 __(nil,X:S) -> X:S
 __(X:S,nil) -> X:S
 __(X1:S,X2:S) -> n____(X1:S,X2:S)
 a -> n__a
 activate(n____(X1:S,X2:S)) -> __(X1:S,X2:S)
 activate(n__a) -> a
 activate(n__e) -> e
 activate(n__i) -> i
 activate(n__isList(X:S)) -> isList(X:S)
 activate(n__isNeList(X:S)) -> isNeList(X:S)
 activate(n__isPal(X:S)) -> isPal(X:S)
 activate(n__nil) -> nil
 activate(n__o) -> o
 activate(n__u) -> u
 activate(X:S) -> X:S
 and(tt,X:S) -> activate(X:S)
 e -> n__e
 i -> n__i
 isList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isList(activate(V2:S)))
 isList(n__nil) -> tt
 isList(V:S) -> isNeList(activate(V:S))
 isList(X:S) -> n__isList(X:S)
 isNeList(n____(V1:S,V2:S)) -> and(isList(activate(V1:S)),n__isNeList(activate(V2:S)))
 isNeList(n____(V1:S,V2:S)) -> and(isNeList(activate(V1:S)),n__isList(activate(V2:S)))
 isNeList(V:S) -> isQid(activate(V:S))
 isNeList(X:S) -> n__isNeList(X:S)
 isNePal(n____(I:S,__(P:S,I:S))) -> and(isQid(activate(I:S)),n__isPal(activate(P:S)))
 isNePal(V:S) -> isQid(activate(V:S))
 isPal(n__nil) -> tt
 isPal(V:S) -> isNePal(activate(V:S))
 isPal(X:S) -> n__isPal(X:S)
 isQid(n__a) -> tt
 isQid(n__e) -> tt
 isQid(n__i) -> tt
 isQid(n__o) -> tt
 isQid(n__u) -> tt
 nil -> n__nil
 o -> n__o
 u -> n__u
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.