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 U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U11#(tt,V:S) -> U12#(isNeList(activate(V:S))) U11#(tt,V:S) -> ACTIVATE(V:S) U11#(tt,V:S) -> ISNELIST(activate(V:S)) U21#(tt,V1:S,V2:S) -> U22#(isList(activate(V1:S)),activate(V2:S)) U21#(tt,V1:S,V2:S) -> ACTIVATE(V1:S) U21#(tt,V1:S,V2:S) -> ACTIVATE(V2:S) U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U22#(tt,V2:S) -> U23#(isList(activate(V2:S))) U22#(tt,V2:S) -> ACTIVATE(V2:S) U22#(tt,V2:S) -> ISLIST(activate(V2:S)) U31#(tt,V:S) -> U32#(isQid(activate(V:S))) U31#(tt,V:S) -> ACTIVATE(V:S) U31#(tt,V:S) -> ISQID(activate(V:S)) U41#(tt,V1:S,V2:S) -> U42#(isList(activate(V1:S)),activate(V2:S)) U41#(tt,V1:S,V2:S) -> ACTIVATE(V1:S) U41#(tt,V1:S,V2:S) -> ACTIVATE(V2:S) U41#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U42#(tt,V2:S) -> U43#(isNeList(activate(V2:S))) U42#(tt,V2:S) -> ACTIVATE(V2:S) U42#(tt,V2:S) -> ISNELIST(activate(V2:S)) U51#(tt,V1:S,V2:S) -> U52#(isNeList(activate(V1:S)),activate(V2:S)) U51#(tt,V1:S,V2:S) -> ACTIVATE(V1:S) U51#(tt,V1:S,V2:S) -> ACTIVATE(V2:S) U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) U52#(tt,V2:S) -> U53#(isList(activate(V2:S))) U52#(tt,V2:S) -> ACTIVATE(V2:S) U52#(tt,V2:S) -> ISLIST(activate(V2:S)) U61#(tt,V:S) -> U62#(isQid(activate(V:S))) U61#(tt,V:S) -> ACTIVATE(V:S) U61#(tt,V:S) -> ISQID(activate(V:S)) U71#(tt,V:S) -> U72#(isNePal(activate(V:S))) U71#(tt,V:S) -> ACTIVATE(V:S) U71#(tt,V:S) -> ISNEPAL(activate(V:S)) __#(__(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__and(X1:S,X2:S)) -> AND(X1:S,X2:S) ACTIVATE(n__e) -> E ACTIVATE(n__i) -> I ACTIVATE(n__isPalListKind(X:S)) -> ISPALLISTKIND(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)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2: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(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISLIST(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) ISLIST(V:S) -> U11#(isPalListKind(activate(V:S)),activate(V:S)) ISLIST(V:S) -> ACTIVATE(V:S) ISLIST(V:S) -> ISPALLISTKIND(activate(V:S)) ISNELIST(n____(V1:S,V2:S)) -> U41#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2: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(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISNELIST(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) ISNELIST(V:S) -> U31#(isPalListKind(activate(V:S)),activate(V:S)) ISNELIST(V:S) -> ACTIVATE(V:S) ISNELIST(V:S) -> ISPALLISTKIND(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(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPalListKind(activate(I:S))) ISNEPAL(n____(I:S,__(P:S,I:S))) -> ISPAL(activate(P:S)) ISNEPAL(n____(I:S,__(P:S,I:S))) -> ISQID(activate(I:S)) ISNEPAL(V:S) -> U61#(isPalListKind(activate(V:S)),activate(V:S)) ISNEPAL(V:S) -> ACTIVATE(V:S) ISNEPAL(V:S) -> ISPALLISTKIND(activate(V:S)) ISPAL(V:S) -> U71#(isPalListKind(activate(V:S)),activate(V:S)) ISPAL(V:S) -> ACTIVATE(V:S) ISPAL(V:S) -> ISPALLISTKIND(activate(V:S)) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V1:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V2:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> AND(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U11#(tt,V:S) -> U12#(isNeList(activate(V:S))) U11#(tt,V:S) -> ACTIVATE(V:S) U11#(tt,V:S) -> ISNELIST(activate(V:S)) U21#(tt,V1:S,V2:S) -> U22#(isList(activate(V1:S)),activate(V2:S)) U21#(tt,V1:S,V2:S) -> ACTIVATE(V1:S) U21#(tt,V1:S,V2:S) -> ACTIVATE(V2:S) U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U22#(tt,V2:S) -> U23#(isList(activate(V2:S))) U22#(tt,V2:S) -> ACTIVATE(V2:S) U22#(tt,V2:S) -> ISLIST(activate(V2:S)) U31#(tt,V:S) -> U32#(isQid(activate(V:S))) U31#(tt,V:S) -> ACTIVATE(V:S) U31#(tt,V:S) -> ISQID(activate(V:S)) U41#(tt,V1:S,V2:S) -> U42#(isList(activate(V1:S)),activate(V2:S)) U41#(tt,V1:S,V2:S) -> ACTIVATE(V1:S) U41#(tt,V1:S,V2:S) -> ACTIVATE(V2:S) U41#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U42#(tt,V2:S) -> U43#(isNeList(activate(V2:S))) U42#(tt,V2:S) -> ACTIVATE(V2:S) U42#(tt,V2:S) -> ISNELIST(activate(V2:S)) U51#(tt,V1:S,V2:S) -> U52#(isNeList(activate(V1:S)),activate(V2:S)) U51#(tt,V1:S,V2:S) -> ACTIVATE(V1:S) U51#(tt,V1:S,V2:S) -> ACTIVATE(V2:S) U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) U52#(tt,V2:S) -> U53#(isList(activate(V2:S))) U52#(tt,V2:S) -> ACTIVATE(V2:S) U52#(tt,V2:S) -> ISLIST(activate(V2:S)) U61#(tt,V:S) -> U62#(isQid(activate(V:S))) U61#(tt,V:S) -> ACTIVATE(V:S) U61#(tt,V:S) -> ISQID(activate(V:S)) U71#(tt,V:S) -> U72#(isNePal(activate(V:S))) U71#(tt,V:S) -> ACTIVATE(V:S) U71#(tt,V:S) -> ISNEPAL(activate(V:S)) __#(__(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__and(X1:S,X2:S)) -> AND(X1:S,X2:S) ACTIVATE(n__e) -> E ACTIVATE(n__i) -> I ACTIVATE(n__isPalListKind(X:S)) -> ISPALLISTKIND(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)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2: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(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISLIST(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) ISLIST(V:S) -> U11#(isPalListKind(activate(V:S)),activate(V:S)) ISLIST(V:S) -> ACTIVATE(V:S) ISLIST(V:S) -> ISPALLISTKIND(activate(V:S)) ISNELIST(n____(V1:S,V2:S)) -> U41#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2: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(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISNELIST(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) ISNELIST(V:S) -> U31#(isPalListKind(activate(V:S)),activate(V:S)) ISNELIST(V:S) -> ACTIVATE(V:S) ISNELIST(V:S) -> ISPALLISTKIND(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(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) ISNEPAL(n____(I:S,__(P:S,I:S))) -> AND(isQid(activate(I:S)),n__isPalListKind(activate(I:S))) ISNEPAL(n____(I:S,__(P:S,I:S))) -> ISPAL(activate(P:S)) ISNEPAL(n____(I:S,__(P:S,I:S))) -> ISQID(activate(I:S)) ISNEPAL(V:S) -> U61#(isPalListKind(activate(V:S)),activate(V:S)) ISNEPAL(V:S) -> ACTIVATE(V:S) ISNEPAL(V:S) -> ISPALLISTKIND(activate(V:S)) ISPAL(V:S) -> U71#(isPalListKind(activate(V:S)),activate(V:S)) ISPAL(V:S) -> ACTIVATE(V:S) ISPAL(V:S) -> ISPALLISTKIND(activate(V:S)) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V1:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V2:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> AND(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__and(X1:S,X2:S)) -> AND(X1:S,X2:S) ACTIVATE(n__isPalListKind(X:S)) -> ISPALLISTKIND(X:S) AND(tt,X:S) -> ACTIVATE(X:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V1:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V2:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> AND(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) ->->-> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U71#(tt,V:S) -> ISNEPAL(activate(V:S)) ISNEPAL(n____(I:S,__(P:S,I:S))) -> ISPAL(activate(P:S)) ISPAL(V:S) -> U71#(isPalListKind(activate(V:S)),activate(V:S)) ->->-> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U11#(tt,V:S) -> ISNELIST(activate(V:S)) U21#(tt,V1:S,V2:S) -> U22#(isList(activate(V1:S)),activate(V2:S)) U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U22#(tt,V2:S) -> ISLIST(activate(V2:S)) U41#(tt,V1:S,V2:S) -> U42#(isList(activate(V1:S)),activate(V2:S)) U41#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U42#(tt,V2:S) -> ISNELIST(activate(V2:S)) U51#(tt,V1:S,V2:S) -> U52#(isNeList(activate(V1:S)),activate(V2:S)) U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) U52#(tt,V2:S) -> ISLIST(activate(V2:S)) ISLIST(n____(V1:S,V2:S)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISLIST(V:S) -> U11#(isPalListKind(activate(V:S)),activate(V:S)) ISNELIST(n____(V1:S,V2:S)) -> U41#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ->->-> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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 4 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: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__and(X1:S,X2:S)) -> AND(X1:S,X2:S) ACTIVATE(n__isPalListKind(X:S)) -> ISPALLISTKIND(X:S) AND(tt,X:S) -> ACTIVATE(X:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V1:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V2:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> AND(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(X:S) 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 + 2 [and](X1,X2) = X2 + 2 [e] = 2 [i] = 2 [isPalListKind](X) = X + 2 [nil] = 2 [o] = 2 [u] = 2 [n____](X1,X2) = 2.X1 + X2 + 2 [n__a] = 2 [n__and](X1,X2) = X2 + 2 [n__e] = 0 [n__i] = 2 [n__isPalListKind](X) = X [n__nil] = 2 [n__o] = 0 [n__u] = 2 [tt] = 2 [ACTIVATE](X) = 2.X [AND](X1,X2) = 2.X2 [ISPALLISTKIND](X) = 2.X Problem 1.2: SCC Processor: -> Pairs: ACTIVATE(n__isPalListKind(X:S)) -> ISPALLISTKIND(X:S) AND(tt,X:S) -> ACTIVATE(X:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V1:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V2:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> AND(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__isPalListKind(X:S)) -> ISPALLISTKIND(X:S) AND(tt,X:S) -> ACTIVATE(X:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V1:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V2:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> AND(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) ->->-> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__isPalListKind(X:S)) -> ISPALLISTKIND(X:S) AND(tt,X:S) -> ACTIVATE(X:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V1:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V2:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> AND(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(X:S) 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 + 1 [and](X1,X2) = X2 + 1 [e] = 2 [i] = 2 [isPalListKind](X) = X + 1 [nil] = 1 [o] = 1 [u] = 2 [n____](X1,X2) = 2.X1 + X2 + 2 [n__a] = 2 [n__and](X1,X2) = X2 + 1 [n__e] = 2 [n__i] = 2 [n__isPalListKind](X) = X + 1 [n__nil] = 1 [n__o] = 1 [n__u] = 2 [tt] = 1 [ACTIVATE](X) = 2.X + 1 [AND](X1,X2) = X1 + 2.X2 [ISPALLISTKIND](X) = 2.X + 2 Problem 1.2: SCC Processor: -> Pairs: AND(tt,X:S) -> ACTIVATE(X:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V1:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> ACTIVATE(V2:S) ISPALLISTKIND(n____(V1:S,V2:S)) -> AND(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) ->->-> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: ISPALLISTKIND(n____(V1:S,V2:S)) -> ISPALLISTKIND(activate(V1:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(X:S) nil -> n__nil o -> n__o u -> n__u ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [__](X1,X2) = X1 + X2 + 2 [a] = 2 [activate](X) = X + 1 [and](X1,X2) = X2 + 1 [e] = 1 [i] = 2 [isPalListKind](X) = 2.X + 2 [nil] = 2 [o] = 2 [u] = 2 [n____](X1,X2) = X1 + X2 + 2 [n__a] = 1 [n__and](X1,X2) = X2 + 1 [n__e] = 1 [n__i] = 2 [n__isPalListKind](X) = 2.X + 1 [n__nil] = 1 [n__o] = 1 [n__u] = 2 [tt] = 0 [ISPALLISTKIND](X) = X Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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.3: Reduction Pair Processor: -> Pairs: U71#(tt,V:S) -> ISNEPAL(activate(V:S)) ISNEPAL(n____(I:S,__(P:S,I:S))) -> ISPAL(activate(P:S)) ISPAL(V:S) -> U71#(isPalListKind(activate(V:S)),activate(V:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(X:S) 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 + 1 [and](X1,X2) = X1 + X2 [e] = 2 [i] = 2 [isPalListKind](X) = X [nil] = 2 [o] = 2 [u] = 2 [n____](X1,X2) = 2.X1 + X2 + 2 [n__a] = 2 [n__and](X1,X2) = X1 + X2 [n__e] = 2 [n__i] = 2 [n__isPalListKind](X) = X [n__nil] = 2 [n__o] = 2 [n__u] = 2 [tt] = 2 [U71#](X1,X2) = X1 + X2 [ISNEPAL](X) = X [ISPAL](X) = 2.X + 2 Problem 1.3: SCC Processor: -> Pairs: ISNEPAL(n____(I:S,__(P:S,I:S))) -> ISPAL(activate(P:S)) ISPAL(V:S) -> U71#(isPalListKind(activate(V:S)),activate(V:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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.4: Reduction Pair Processor: -> Pairs: U11#(tt,V:S) -> ISNELIST(activate(V:S)) U21#(tt,V1:S,V2:S) -> U22#(isList(activate(V1:S)),activate(V2:S)) U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U22#(tt,V2:S) -> ISLIST(activate(V2:S)) U41#(tt,V1:S,V2:S) -> U42#(isList(activate(V1:S)),activate(V2:S)) U41#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U42#(tt,V2:S) -> ISNELIST(activate(V2:S)) U51#(tt,V1:S,V2:S) -> U52#(isNeList(activate(V1:S)),activate(V2:S)) U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) U52#(tt,V2:S) -> ISLIST(activate(V2:S)) ISLIST(n____(V1:S,V2:S)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISLIST(V:S) -> U11#(isPalListKind(activate(V:S)),activate(V:S)) ISNELIST(n____(V1:S,V2:S)) -> U41#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: [U11](X1,X2) = X2 [U12](X) = 0 [U21](X1,X2,X3) = X3 + 1 [U22](X1,X2) = X2 + 1 [U23](X) = X + 1 [U31](X1,X2) = 0 [U32](X) = 0 [U41](X1,X2,X3) = 0 [U42](X1,X2) = 0 [U43](X) = 2.X [U51](X1,X2,X3) = 0 [U52](X1,X2) = 2.X1 [U53](X) = 0 [__](X1,X2) = X1 + X2 + 2 [a] = 1 [activate](X) = X [and](X1,X2) = X2 + 2 [e] = 0 [i] = 2 [isList](X) = X [isNeList](X) = 0 [isPalListKind](X) = 2.X + 2 [isQid](X) = 2 [nil] = 2 [o] = 2 [u] = 1 [n____](X1,X2) = X1 + X2 + 2 [n__a] = 1 [n__and](X1,X2) = X2 + 2 [n__e] = 0 [n__i] = 2 [n__isPalListKind](X) = 2.X + 2 [n__nil] = 2 [n__o] = 2 [n__u] = 1 [tt] = 0 [U11#](X1,X2) = 2.X2 + 2 [U21#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U22#](X1,X2) = 2.X1 + 2.X2 + 2 [U41#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U42#](X1,X2) = 2.X1 + 2.X2 + 2 [U51#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U52#](X1,X2) = 2.X1 + 2.X2 + 2 [ISLIST](X) = 2.X + 2 [ISNELIST](X) = 2.X + 1 Problem 1.4: SCC Processor: -> Pairs: U21#(tt,V1:S,V2:S) -> U22#(isList(activate(V1:S)),activate(V2:S)) U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U22#(tt,V2:S) -> ISLIST(activate(V2:S)) U41#(tt,V1:S,V2:S) -> U42#(isList(activate(V1:S)),activate(V2:S)) U41#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U42#(tt,V2:S) -> ISNELIST(activate(V2:S)) U51#(tt,V1:S,V2:S) -> U52#(isNeList(activate(V1:S)),activate(V2:S)) U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) U52#(tt,V2:S) -> ISLIST(activate(V2:S)) ISLIST(n____(V1:S,V2:S)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISLIST(V:S) -> U11#(isPalListKind(activate(V:S)),activate(V:S)) ISNELIST(n____(V1:S,V2:S)) -> U41#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U21#(tt,V1:S,V2:S) -> U22#(isList(activate(V1:S)),activate(V2:S)) U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U22#(tt,V2:S) -> ISLIST(activate(V2:S)) ISLIST(n____(V1:S,V2:S)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ->->-> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U41#(tt,V1:S,V2:S) -> U42#(isList(activate(V1:S)),activate(V2:S)) U42#(tt,V2:S) -> ISNELIST(activate(V2:S)) U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) ISNELIST(n____(V1:S,V2:S)) -> U41#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ->->-> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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.4.1: Reduction Pair Processor: -> Pairs: U21#(tt,V1:S,V2:S) -> U22#(isList(activate(V1:S)),activate(V2:S)) U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U22#(tt,V2:S) -> ISLIST(activate(V2:S)) ISLIST(n____(V1:S,V2:S)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: [U11](X1,X2) = 2.X2 + 2 [U12](X) = 2 [U21](X1,X2,X3) = 2.X1 + 2.X2 [U22](X1,X2) = X1 + 1 [U23](X) = 2 [U31](X1,X2) = 2.X2 + 1 [U32](X) = X [U41](X1,X2,X3) = 2.X1 + 2.X2 [U42](X1,X2) = X1 + 2 [U43](X) = 2 [U51](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U52](X1,X2) = 2.X2 + 2 [U53](X) = 2 [__](X1,X2) = 2.X1 + X2 + 2 [a] = 2 [activate](X) = X [and](X1,X2) = X2 + 1 [e] = 2 [i] = 2 [isList](X) = 2.X + 2 [isNeList](X) = 2.X + 2 [isPalListKind](X) = X + 2 [isQid](X) = X + 1 [nil] = 2 [o] = 2 [u] = 1 [n____](X1,X2) = 2.X1 + X2 + 2 [n__a] = 2 [n__and](X1,X2) = X2 + 1 [n__e] = 2 [n__i] = 2 [n__isPalListKind](X) = X + 2 [n__nil] = 2 [n__o] = 2 [n__u] = 1 [tt] = 2 [U21#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U22#](X1,X2) = 2.X2 + 1 [ISLIST](X) = 2.X + 1 Problem 1.4.1: SCC Processor: -> Pairs: U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) U22#(tt,V2:S) -> ISLIST(activate(V2:S)) ISLIST(n____(V1:S,V2:S)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) ISLIST(n____(V1:S,V2:S)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ->->-> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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.4.1: Reduction Pair Processor: -> Pairs: U21#(tt,V1:S,V2:S) -> ISLIST(activate(V1:S)) ISLIST(n____(V1:S,V2:S)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(X:S) 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] = 0 [activate](X) = X [and](X1,X2) = X2 [e] = 2 [i] = 2 [isPalListKind](X) = 2 [nil] = 2 [o] = 2 [u] = 2 [n____](X1,X2) = 2.X1 + X2 + 2 [n__a] = 0 [n__and](X1,X2) = X2 [n__e] = 2 [n__i] = 2 [n__isPalListKind](X) = 2 [n__nil] = 2 [n__o] = 2 [n__u] = 2 [tt] = 2 [U21#](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 1 [ISLIST](X) = 2.X + 1 Problem 1.4.1: SCC Processor: -> Pairs: ISLIST(n____(V1:S,V2:S)) -> U21#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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.4.2: Reduction Pair Processor: -> Pairs: U41#(tt,V1:S,V2:S) -> U42#(isList(activate(V1:S)),activate(V2:S)) U42#(tt,V2:S) -> ISNELIST(activate(V2:S)) U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) ISNELIST(n____(V1:S,V2:S)) -> U41#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: [U11](X1,X2) = 2.X2 + 1 [U12](X) = X [U21](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U22](X1,X2) = 2.X2 + 2 [U23](X) = 2 [U31](X1,X2) = 2.X2 + 1 [U32](X) = X [U41](X1,X2,X3) = X2 + 2.X3 + 2 [U42](X1,X2) = 2.X2 + 2 [U43](X) = 2 [U51](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U52](X1,X2) = 2 [U53](X) = 2 [__](X1,X2) = X1 + X2 + 2 [a] = 1 [activate](X) = X [and](X1,X2) = X2 + 2 [e] = 2 [i] = 2 [isList](X) = 2.X + 1 [isNeList](X) = 2.X + 1 [isPalListKind](X) = 2.X + 2 [isQid](X) = 2.X + 1 [nil] = 2 [o] = 2 [u] = 2 [n____](X1,X2) = X1 + X2 + 2 [n__a] = 1 [n__and](X1,X2) = X2 + 2 [n__e] = 2 [n__i] = 2 [n__isPalListKind](X) = 2.X + 2 [n__nil] = 2 [n__o] = 2 [n__u] = 2 [tt] = 2 [U41#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U42#](X1,X2) = X1 + 2.X2 [U51#](X1,X2,X3) = X1 + 2.X2 + 2 [ISNELIST](X) = 2.X + 2 Problem 1.4.2: SCC Processor: -> Pairs: U42#(tt,V2:S) -> ISNELIST(activate(V2:S)) U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) ISNELIST(n____(V1:S,V2:S)) -> U41#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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: U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) ->->-> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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.4.2: Reduction Pair Processor: -> Pairs: U51#(tt,V1:S,V2:S) -> ISNELIST(activate(V1:S)) ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(X:S) 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] = 0 [activate](X) = X [and](X1,X2) = X2 [e] = 2 [i] = 2 [isPalListKind](X) = 2 [nil] = 2 [o] = 2 [u] = 2 [n____](X1,X2) = 2.X1 + X2 + 2 [n__a] = 0 [n__and](X1,X2) = X2 [n__e] = 2 [n__i] = 2 [n__isPalListKind](X) = 2 [n__nil] = 2 [n__o] = 2 [n__u] = 2 [tt] = 2 [U51#](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 1 [ISNELIST](X) = 2.X + 1 Problem 1.4.2: SCC Processor: -> Pairs: ISNELIST(n____(V1:S,V2:S)) -> U51#(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) -> Rules: U11(tt,V:S) -> U12(isNeList(activate(V:S))) U12(tt) -> tt U21(tt,V1:S,V2:S) -> U22(isList(activate(V1:S)),activate(V2:S)) U22(tt,V2:S) -> U23(isList(activate(V2:S))) U23(tt) -> tt U31(tt,V:S) -> U32(isQid(activate(V:S))) U32(tt) -> tt U41(tt,V1:S,V2:S) -> U42(isList(activate(V1:S)),activate(V2:S)) U42(tt,V2:S) -> U43(isNeList(activate(V2:S))) U43(tt) -> tt U51(tt,V1:S,V2:S) -> U52(isNeList(activate(V1:S)),activate(V2:S)) U52(tt,V2:S) -> U53(isList(activate(V2:S))) U53(tt) -> tt U61(tt,V:S) -> U62(isQid(activate(V:S))) U62(tt) -> tt U71(tt,V:S) -> U72(isNePal(activate(V:S))) U72(tt) -> tt __(__(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__and(X1:S,X2:S)) -> and(X1:S,X2:S) activate(n__e) -> e activate(n__i) -> i activate(n__isPalListKind(X:S)) -> isPalListKind(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) and(X1:S,X2:S) -> n__and(X1:S,X2:S) e -> n__e i -> n__i isList(n____(V1:S,V2:S)) -> U21(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isList(n__nil) -> tt isList(V:S) -> U11(isPalListKind(activate(V:S)),activate(V:S)) isNeList(n____(V1:S,V2:S)) -> U41(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(n____(V1:S,V2:S)) -> U51(and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))),activate(V1:S),activate(V2:S)) isNeList(V:S) -> U31(isPalListKind(activate(V:S)),activate(V:S)) isNePal(n____(I:S,__(P:S,I:S))) -> and(and(isQid(activate(I:S)),n__isPalListKind(activate(I:S))),n__and(isPal(activate(P:S)),n__isPalListKind(activate(P:S)))) isNePal(V:S) -> U61(isPalListKind(activate(V:S)),activate(V:S)) isPal(n__nil) -> tt isPal(V:S) -> U71(isPalListKind(activate(V:S)),activate(V:S)) isPalListKind(n____(V1:S,V2:S)) -> and(isPalListKind(activate(V1:S)),n__isPalListKind(activate(V2:S))) isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(X:S) -> n__isPalListKind(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.