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

__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
and(tt, X) → activate(X)
isList(V) → isNeList(activate(V))
isList(n__nil) → tt
isList(n____(V1, V2)) → and(isList(activate(V1)), n__isList(activate(V2)))
isNeList(V) → isQid(activate(V))
isNeList(n____(V1, V2)) → and(isList(activate(V1)), n__isNeList(activate(V2)))
isNeList(n____(V1, V2)) → and(isNeList(activate(V1)), n__isList(activate(V2)))
isNePal(V) → isQid(activate(V))
isNePal(n____(I, n____(P, I))) → and(isQid(activate(I)), n__isPal(activate(P)))
isPal(V) → isNePal(activate(V))
isPal(n__nil) → tt
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)
isList(X) → n__isList(X)
isNeList(X) → n__isNeList(X)
isPal(X) → n__isPal(X)
a → n__a
e → n__e
i → n__i
o → n__o
u → n__u
activate(n__nil) → nil
activate(n____(X1, X2)) → __(activate(X1), activate(X2))
activate(n__isList(X)) → isList(X)
activate(n__isNeList(X)) → isNeList(X)
activate(n__isPal(X)) → isPal(X)
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
and'(tt', X) → activate'(X)
isList'(V) → isNeList'(activate'(V))
isList'(n__nil') → tt'
isList'(n____'(V1, V2)) → and'(isList'(activate'(V1)), n__isList'(activate'(V2)))
isNeList'(V) → isQid'(activate'(V))
isNeList'(n____'(V1, V2)) → and'(isList'(activate'(V1)), n__isNeList'(activate'(V2)))
isNeList'(n____'(V1, V2)) → and'(isNeList'(activate'(V1)), n__isList'(activate'(V2)))
isNePal'(V) → isQid'(activate'(V))
isNePal'(n____'(I, n____'(P, I))) → and'(isQid'(activate'(I)), n__isPal'(activate'(P)))
isPal'(V) → isNePal'(activate'(V))
isPal'(n__nil') → tt'
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)
isList'(X) → n__isList'(X)
isNeList'(X) → n__isNeList'(X)
isPal'(X) → n__isPal'(X)
a' → n__a'
e' → n__e'
i' → n__i'
o' → n__o'
u' → n__u'
activate'(n__nil') → nil'
activate'(n____'(X1, X2)) → __'(activate'(X1), activate'(X2))
activate'(n__isList'(X)) → isList'(X)
activate'(n__isNeList'(X)) → isNeList'(X)
activate'(n__isPal'(X)) → isPal'(X)
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
and'(tt', X) → activate'(X)
isList'(V) → isNeList'(activate'(V))
isList'(n__nil') → tt'
isList'(n____'(V1, V2)) → and'(isList'(activate'(V1)), n__isList'(activate'(V2)))
isNeList'(V) → isQid'(activate'(V))
isNeList'(n____'(V1, V2)) → and'(isList'(activate'(V1)), n__isNeList'(activate'(V2)))
isNeList'(n____'(V1, V2)) → and'(isNeList'(activate'(V1)), n__isList'(activate'(V2)))
isNePal'(V) → isQid'(activate'(V))
isNePal'(n____'(I, n____'(P, I))) → and'(isQid'(activate'(I)), n__isPal'(activate'(P)))
isPal'(V) → isNePal'(activate'(V))
isPal'(n__nil') → tt'
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)
isList'(X) → n__isList'(X)
isNeList'(X) → n__isNeList'(X)
isPal'(X) → n__isPal'(X)
a' → n__a'
e' → n__e'
i' → n__i'
o' → n__o'
u' → n__u'
activate'(n__nil') → nil'
activate'(n____'(X1, X2)) → __'(activate'(X1), activate'(X2))
activate'(n__isList'(X)) → isList'(X)
activate'(n__isNeList'(X)) → isNeList'(X)
activate'(n__isPal'(X)) → isPal'(X)
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__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
nil' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
and' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
tt' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
activate' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
isList' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
isNeList' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n__nil' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n____' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n__isList' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
isQid' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n__isNeList' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
isNePal' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n__isPal' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
isPal' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u' → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n__a' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n__e' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n__i' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n__o' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
n__u' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
a' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
e' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
i' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
o' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
u' :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
___hole_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'1 :: tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'
___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2 :: Nat → tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'

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

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

Generator Equations:
___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(0) ⇔ n__nil'
___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(+(x, 1)) ⇔ n____'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(x), n__nil')

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

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

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

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

Proved the following rewrite lemma:
activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n48)) → ___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n48), rt ∈ Ω(1 + _{__n48})

Induction Base:
activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(0)) →_R^Ω(1)
___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(0)

Induction Step:
activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(+(___$n49, 1))) →_R^Ω(1)
__'(activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n49)), activate'(n__nil')) →_IH
__'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n49), activate'(n__nil')) →_R^Ω(1)
__'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n49), n__nil') →_R^Ω(1)
n____'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n49), n__nil')

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

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

Proved the following rewrite lemma:
isList'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n43066)) → ___*3, rt ∈ Ω(_{__n43066} + _{__n43066}²)

Induction Base:
isList'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(0))

Induction Step:
isList'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(+(___$n43067, 1))) →_R^Ω(1)
and'(isList'(activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n43067))), n__isList'(activate'(n__nil'))) →_L^{Ω(1 + _{__$n43067})}
and'(isList'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n43067)), n__isList'(activate'(n__nil'))) →_IH
and'(___*3, n__isList'(activate'(n__nil'))) →_L^Ω(1)
and'(___*3, n__isList'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(0)))

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

Lemmas:
activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n48)) → ___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n48), rt ∈ Ω(1 + _{__n48})
isList'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n43066)) → ___*3, rt ∈ Ω(_{__n43066} + _{__n43066}²)

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

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

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

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

The following defined symbols remain to be analysed:
isPal', activate', isNePal'

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

The following defined symbols remain to be analysed:
isNePal', activate'

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

The following defined symbols remain to be analysed:
activate'

Proved the following rewrite lemma:
activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n373864)) → ___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n373864), rt ∈ Ω(1 + _{__n373864})

Induction Step:
activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(+(___$n373865, 1))) →_R^Ω(1)
__'(activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n373865)), activate'(n__nil')) →_IH
__'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n373865), activate'(n__nil')) →_R^Ω(1)
__'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n373865), n__nil') →_R^Ω(1)
n____'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___$n373865), n__nil')

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

Lemmas:
activate'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n373864)) → ___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n373864), rt ∈ Ω(1 + _{__n373864})
isList'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n43066)) → ___*3, rt ∈ Ω(_{__n43066} + _{__n43066}²)

No more defined symbols left to analyse.

The lowerbound Ω(n²) was proven with the following lemma:
isList'(___gen_tt':n__nil':n____':n__isList':n__isNeList':n__isPal':n__a':n__e':n__i':n__o':n__u'2(___n43066)) → ___*3, rt ∈ Ω(_{__n43066} + _{__n43066}²)