Runtime Complexity TRS:
The TRS R consists of the following rules:

__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt, V) → U12(isNeList(activate(V)))
U12(tt) → tt
U21(tt, V1, V2) → U22(isList(activate(V1)), activate(V2))
U22(tt, V2) → U23(isList(activate(V2)))
U23(tt) → tt
U31(tt, V) → U32(isQid(activate(V)))
U32(tt) → tt
U41(tt, V1, V2) → U42(isList(activate(V1)), activate(V2))
U42(tt, V2) → U43(isNeList(activate(V2)))
U43(tt) → tt
U51(tt, V1, V2) → U52(isNeList(activate(V1)), activate(V2))
U52(tt, V2) → U53(isList(activate(V2)))
U53(tt) → tt
U61(tt, V) → U62(isQid(activate(V)))
U62(tt) → tt
U71(tt, V) → U72(isNePal(activate(V)))
U72(tt) → tt
and(tt, X) → activate(X)
isList(V) → U11(isPalListKind(activate(V)), activate(V))
isList(n__nil) → tt
isList(n____(V1, V2)) → U21(and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))), activate(V1), activate(V2))
isNeList(V) → U31(isPalListKind(activate(V)), activate(V))
isNeList(n____(V1, V2)) → U41(and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))), activate(V1), activate(V2))
isNeList(n____(V1, V2)) → U51(and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))), activate(V1), activate(V2))
isNePal(V) → U61(isPalListKind(activate(V)), activate(V))
isNePal(n____(I, __(P, I))) → and(and(isQid(activate(I)), n__isPalListKind(activate(I))), n__and(isPal(activate(P)), n__isPalListKind(activate(P))))
isPal(V) → U71(isPalListKind(activate(V)), activate(V))
isPal(n__nil) → tt
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(n____(V1, V2)) → and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2)))
isQid(n__a) → tt
isQid(n__e) → tt
isQid(n__i) → tt
isQid(n__o) → tt
isQid(n__u) → tt
nil → n__nil
__(X1, X2) → n____(X1, X2)
isPalListKind(X) → n__isPalListKind(X)
and(X1, X2) → n__and(X1, X2)
a → n__a
e → n__e
i → n__i
o → n__o
u → n__u
activate(n__nil) → nil
activate(n____(X1, X2)) → __(X1, X2)
activate(n__isPalListKind(X)) → isPalListKind(X)
activate(n__and(X1, X2)) → and(X1, X2)
activate(n__a) → a
activate(n__e) → e
activate(n__i) → i
activate(n__o) → o
activate(n__u) → u
activate(X) → X

Rewrite Strategy: INNERMOST

Renamed function symbols to avoid clashes with predefined symbol.

Runtime Complexity TRS:
The TRS R consists of the following rules:

__'(__'(X, Y), Z) → __'(X, __'(Y, Z))
__'(X, nil') → X
__'(nil', X) → X
U11'(tt', V) → U12'(isNeList'(activate'(V)))
U12'(tt') → tt'
U21'(tt', V1, V2) → U22'(isList'(activate'(V1)), activate'(V2))
U22'(tt', V2) → U23'(isList'(activate'(V2)))
U23'(tt') → tt'
U31'(tt', V) → U32'(isQid'(activate'(V)))
U32'(tt') → tt'
U41'(tt', V1, V2) → U42'(isList'(activate'(V1)), activate'(V2))
U42'(tt', V2) → U43'(isNeList'(activate'(V2)))
U43'(tt') → tt'
U51'(tt', V1, V2) → U52'(isNeList'(activate'(V1)), activate'(V2))
U52'(tt', V2) → U53'(isList'(activate'(V2)))
U53'(tt') → tt'
U61'(tt', V) → U62'(isQid'(activate'(V)))
U62'(tt') → tt'
U71'(tt', V) → U72'(isNePal'(activate'(V)))
U72'(tt') → tt'
and'(tt', X) → activate'(X)
isList'(V) → U11'(isPalListKind'(activate'(V)), activate'(V))
isList'(n__nil') → tt'
isList'(n____'(V1, V2)) → U21'(and'(isPalListKind'(activate'(V1)), n__isPalListKind'(activate'(V2))), activate'(V1), activate'(V2))
isNeList'(V) → U31'(isPalListKind'(activate'(V)), activate'(V))
isNeList'(n____'(V1, V2)) → U41'(and'(isPalListKind'(activate'(V1)), n__isPalListKind'(activate'(V2))), activate'(V1), activate'(V2))
isNeList'(n____'(V1, V2)) → U51'(and'(isPalListKind'(activate'(V1)), n__isPalListKind'(activate'(V2))), activate'(V1), activate'(V2))
isNePal'(V) → U61'(isPalListKind'(activate'(V)), activate'(V))
isNePal'(n____'(I, __'(P, I))) → and'(and'(isQid'(activate'(I)), n__isPalListKind'(activate'(I))), n__and'(isPal'(activate'(P)), n__isPalListKind'(activate'(P))))
isPal'(V) → U71'(isPalListKind'(activate'(V)), activate'(V))
isPal'(n__nil') → tt'
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'(n____'(V1, V2)) → and'(isPalListKind'(activate'(V1)), n__isPalListKind'(activate'(V2)))
isQid'(n__a') → tt'
isQid'(n__e') → tt'
isQid'(n__i') → tt'
isQid'(n__o') → tt'
isQid'(n__u') → tt'
nil' → n__nil'
__'(X1, X2) → n____'(X1, X2)
isPalListKind'(X) → n__isPalListKind'(X)
and'(X1, X2) → n__and'(X1, X2)
a' → n__a'
e' → n__e'
i' → n__i'
o' → n__o'
u' → n__u'
activate'(n__nil') → nil'
activate'(n____'(X1, X2)) → __'(X1, X2)
activate'(n__isPalListKind'(X)) → isPalListKind'(X)
activate'(n__and'(X1, X2)) → and'(X1, X2)
activate'(n__a') → a'
activate'(n__e') → e'
activate'(n__i') → i'
activate'(n__o') → o'
activate'(n__u') → u'
activate'(X) → X

Rewrite Strategy: INNERMOST

Infered types.

Rules:
__'(__'(X, Y), Z) → __'(X, __'(Y, Z))
__'(X, nil') → X
__'(nil', X) → X
U11'(tt', V) → U12'(isNeList'(activate'(V)))
U12'(tt') → tt'
U21'(tt', V1, V2) → U22'(isList'(activate'(V1)), activate'(V2))
U22'(tt', V2) → U23'(isList'(activate'(V2)))
U23'(tt') → tt'
U31'(tt', V) → U32'(isQid'(activate'(V)))
U32'(tt') → tt'
U41'(tt', V1, V2) → U42'(isList'(activate'(V1)), activate'(V2))
U42'(tt', V2) → U43'(isNeList'(activate'(V2)))
U43'(tt') → tt'
U51'(tt', V1, V2) → U52'(isNeList'(activate'(V1)), activate'(V2))
U52'(tt', V2) → U53'(isList'(activate'(V2)))
U53'(tt') → tt'
U61'(tt', V) → U62'(isQid'(activate'(V)))
U62'(tt') → tt'
U71'(tt', V) → U72'(isNePal'(activate'(V)))
U72'(tt') → tt'
and'(tt', X) → activate'(X)
isList'(V) → U11'(isPalListKind'(activate'(V)), activate'(V))
isList'(n__nil') → tt'
isList'(n____'(V1, V2)) → U21'(and'(isPalListKind'(activate'(V1)), n__isPalListKind'(activate'(V2))), activate'(V1), activate'(V2))
isNeList'(V) → U31'(isPalListKind'(activate'(V)), activate'(V))
isNeList'(n____'(V1, V2)) → U41'(and'(isPalListKind'(activate'(V1)), n__isPalListKind'(activate'(V2))), activate'(V1), activate'(V2))
isNeList'(n____'(V1, V2)) → U51'(and'(isPalListKind'(activate'(V1)), n__isPalListKind'(activate'(V2))), activate'(V1), activate'(V2))
isNePal'(V) → U61'(isPalListKind'(activate'(V)), activate'(V))
isNePal'(n____'(I, __'(P, I))) → and'(and'(isQid'(activate'(I)), n__isPalListKind'(activate'(I))), n__and'(isPal'(activate'(P)), n__isPalListKind'(activate'(P))))
isPal'(V) → U71'(isPalListKind'(activate'(V)), activate'(V))
isPal'(n__nil') → tt'
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'(n____'(V1, V2)) → and'(isPalListKind'(activate'(V1)), n__isPalListKind'(activate'(V2)))
isQid'(n__a') → tt'
isQid'(n__e') → tt'
isQid'(n__i') → tt'
isQid'(n__o') → tt'
isQid'(n__u') → tt'
nil' → n__nil'
__'(X1, X2) → n____'(X1, X2)
isPalListKind'(X) → n__isPalListKind'(X)
and'(X1, X2) → n__and'(X1, X2)
a' → n__a'
e' → n__e'
i' → n__i'
o' → n__o'
u' → n__u'
activate'(n__nil') → nil'
activate'(n____'(X1, X2)) → __'(X1, X2)
activate'(n__isPalListKind'(X)) → isPalListKind'(X)
activate'(n__and'(X1, X2)) → and'(X1, X2)
activate'(n__a') → a'
activate'(n__e') → e'
activate'(n__i') → i'
activate'(n__o') → o'
activate'(n__u') → u'
activate'(X) → X

Types:
__' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
nil' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U11' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
tt' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U12' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
isNeList' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
activate' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U21' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U22' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
isList' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U23' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U31' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U32' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
isQid' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U41' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U42' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U43' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U51' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U52' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U53' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U61' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U62' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U71' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
U72' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
isNePal' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
and' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
isPalListKind' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
n__nil' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
n____' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
n__isPalListKind' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
n__and' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
isPal' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
n__a' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
n__e' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
n__i' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
n__o' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
n__u' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
a' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
e' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
i' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
o' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
u' :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
___hole_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'1 :: tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'
___gen_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'2 :: Nat → tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'

Heuristically decided to analyse the following defined symbols:
__', isNeList', activate', isList', isNePal', and', isPalListKind', isPal'

They will be analysed ascendingly in the following order:
__' < activate'
activate' < isNeList'
isNeList' = isList'
and' < isNeList'
isPalListKind' < isNeList'
activate' < isList'
activate' < isNePal'
activate' = and'
activate' = isPalListKind'
activate' < isPal'
and' < isList'
isPalListKind' < isList'
and' < isNePal'
isPalListKind' < isNePal'
isNePal' = isPal'
and' = isPalListKind'
isPalListKind' < isPal'

Generator Equations:
___gen_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'2(0) ⇔ tt'
___gen_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'2(+(x, 1)) ⇔ n____'(___gen_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'2(x), tt')

The following defined symbols remain to be analysed:
__', isNeList', activate', isList', isNePal', and', isPalListKind', isPal'

Could not prove a rewrite lemma for the defined symbol __'.

The following defined symbols remain to be analysed:
isPalListKind', isNeList', activate', isList', isNePal', and', isPal'

They will be analysed ascendingly in the following order:
activate' < isNeList'
isNeList' = isList'
and' < isNeList'
isPalListKind' < isNeList'
activate' < isList'
activate' < isNePal'
activate' = and'
activate' = isPalListKind'
activate' < isPal'
and' < isList'
isPalListKind' < isList'
and' < isNePal'
isPalListKind' < isNePal'
isNePal' = isPal'
and' = isPalListKind'
isPalListKind' < isPal'

Proved the following rewrite lemma:
isPalListKind'(___gen_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'2(+(1, ___n48))) → ___*3, rt ∈ Ω(_{__n48})

Induction Base:
isPalListKind'(___gen_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'2(+(1, 0)))

Induction Step:
isPalListKind'(___gen_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'2(+(1, +(___$n49, 1)))) →_R^Ω(1)
and'(isPalListKind'(activate'(___gen_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'2(+(1, ___$n49)))), n__isPalListKind'(activate'(tt'))) →_R^Ω(1)
and'(isPalListKind'(___gen_tt':n__nil':n____':n__isPalListKind':n__and':n__a':n__e':n__i':n__o':n__u'2(+(1, ___$n49))), n__isPalListKind'(activate'(tt'))) →_IH
and'(___*3, n__isPalListKind'(activate'(tt'))) →_R^Ω(1)
and'(___*3, n__isPalListKind'(tt'))

We have rt ∈ Ω(n) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).