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

a____(__(X, Y), Z) → a____(mark(X), a____(mark(Y), mark(Z)))
a____(X, nil) → mark(X)
a____(nil, X) → mark(X)
a__U11(tt) → tt
a__U21(tt, V2) → a__U22(a__isList(V2))
a__U22(tt) → tt
a__U31(tt) → tt
a__U41(tt, V2) → a__U42(a__isNeList(V2))
a__U42(tt) → tt
a__U51(tt, V2) → a__U52(a__isList(V2))
a__U52(tt) → tt
a__U61(tt) → tt
a__U71(tt, P) → a__U72(a__isPal(P))
a__U72(tt) → tt
a__U81(tt) → tt
a__isList(V) → a__U11(a__isNeList(V))
a__isList(nil) → tt
a__isList(__(V1, V2)) → a__U21(a__isList(V1), V2)
a__isNeList(V) → a__U31(a__isQid(V))
a__isNeList(__(V1, V2)) → a__U41(a__isList(V1), V2)
a__isNeList(__(V1, V2)) → a__U51(a__isNeList(V1), V2)
a__isNePal(V) → a__U61(a__isQid(V))
a__isNePal(__(I, __(P, I))) → a__U71(a__isQid(I), P)
a__isPal(V) → a__U81(a__isNePal(V))
a__isPal(nil) → tt
a__isQid(a) → tt
a__isQid(e) → tt
a__isQid(i) → tt
a__isQid(o) → tt
a__isQid(u) → tt
mark(__(X1, X2)) → a____(mark(X1), mark(X2))
mark(U11(X)) → a__U11(mark(X))
mark(U21(X1, X2)) → a__U21(mark(X1), X2)
mark(U22(X)) → a__U22(mark(X))
mark(isList(X)) → a__isList(X)
mark(U31(X)) → a__U31(mark(X))
mark(U41(X1, X2)) → a__U41(mark(X1), X2)
mark(U42(X)) → a__U42(mark(X))
mark(isNeList(X)) → a__isNeList(X)
mark(U51(X1, X2)) → a__U51(mark(X1), X2)
mark(U52(X)) → a__U52(mark(X))
mark(U61(X)) → a__U61(mark(X))
mark(U71(X1, X2)) → a__U71(mark(X1), X2)
mark(U72(X)) → a__U72(mark(X))
mark(isPal(X)) → a__isPal(X)
mark(U81(X)) → a__U81(mark(X))
mark(isQid(X)) → a__isQid(X)
mark(isNePal(X)) → a__isNePal(X)
mark(nil) → nil
mark(tt) → tt
mark(a) → a
mark(e) → e
mark(i) → i
mark(o) → o
mark(u) → u
a____(X1, X2) → __(X1, X2)
a__U11(X) → U11(X)
a__U21(X1, X2) → U21(X1, X2)
a__U22(X) → U22(X)
a__isList(X) → isList(X)
a__U31(X) → U31(X)
a__U41(X1, X2) → U41(X1, X2)
a__U42(X) → U42(X)
a__isNeList(X) → isNeList(X)
a__U51(X1, X2) → U51(X1, X2)
a__U52(X) → U52(X)
a__U61(X) → U61(X)
a__U71(X1, X2) → U71(X1, X2)
a__U72(X) → U72(X)
a__isPal(X) → isPal(X)
a__U81(X) → U81(X)
a__isQid(X) → isQid(X)
a__isNePal(X) → isNePal(X)

Rewrite Strategy: INNERMOST

Renamed function symbols to avoid clashes with predefined symbol.

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

a____'(__'(X, Y), Z) → a____'(mark'(X), a____'(mark'(Y), mark'(Z)))
a____'(X, nil') → mark'(X)
a____'(nil', X) → mark'(X)
a__U11'(tt') → tt'
a__U21'(tt', V2) → a__U22'(a__isList'(V2))
a__U22'(tt') → tt'
a__U31'(tt') → tt'
a__U41'(tt', V2) → a__U42'(a__isNeList'(V2))
a__U42'(tt') → tt'
a__U51'(tt', V2) → a__U52'(a__isList'(V2))
a__U52'(tt') → tt'
a__U61'(tt') → tt'
a__U71'(tt', P) → a__U72'(a__isPal'(P))
a__U72'(tt') → tt'
a__U81'(tt') → tt'
a__isList'(V) → a__U11'(a__isNeList'(V))
a__isList'(nil') → tt'
a__isList'(__'(V1, V2)) → a__U21'(a__isList'(V1), V2)
a__isNeList'(V) → a__U31'(a__isQid'(V))
a__isNeList'(__'(V1, V2)) → a__U41'(a__isList'(V1), V2)
a__isNeList'(__'(V1, V2)) → a__U51'(a__isNeList'(V1), V2)
a__isNePal'(V) → a__U61'(a__isQid'(V))
a__isNePal'(__'(I, __'(P, I))) → a__U71'(a__isQid'(I), P)
a__isPal'(V) → a__U81'(a__isNePal'(V))
a__isPal'(nil') → tt'
a__isQid'(a') → tt'
a__isQid'(e') → tt'
a__isQid'(i') → tt'
a__isQid'(o') → tt'
a__isQid'(u') → tt'
mark'(__'(X1, X2)) → a____'(mark'(X1), mark'(X2))
mark'(U11'(X)) → a__U11'(mark'(X))
mark'(U21'(X1, X2)) → a__U21'(mark'(X1), X2)
mark'(U22'(X)) → a__U22'(mark'(X))
mark'(isList'(X)) → a__isList'(X)
mark'(U31'(X)) → a__U31'(mark'(X))
mark'(U41'(X1, X2)) → a__U41'(mark'(X1), X2)
mark'(U42'(X)) → a__U42'(mark'(X))
mark'(isNeList'(X)) → a__isNeList'(X)
mark'(U51'(X1, X2)) → a__U51'(mark'(X1), X2)
mark'(U52'(X)) → a__U52'(mark'(X))
mark'(U61'(X)) → a__U61'(mark'(X))
mark'(U71'(X1, X2)) → a__U71'(mark'(X1), X2)
mark'(U72'(X)) → a__U72'(mark'(X))
mark'(isPal'(X)) → a__isPal'(X)
mark'(U81'(X)) → a__U81'(mark'(X))
mark'(isQid'(X)) → a__isQid'(X)
mark'(isNePal'(X)) → a__isNePal'(X)
mark'(nil') → nil'
mark'(tt') → tt'
mark'(a') → a'
mark'(e') → e'
mark'(i') → i'
mark'(o') → o'
mark'(u') → u'
a____'(X1, X2) → __'(X1, X2)
a__U11'(X) → U11'(X)
a__U21'(X1, X2) → U21'(X1, X2)
a__U22'(X) → U22'(X)
a__isList'(X) → isList'(X)
a__U31'(X) → U31'(X)
a__U41'(X1, X2) → U41'(X1, X2)
a__U42'(X) → U42'(X)
a__isNeList'(X) → isNeList'(X)
a__U51'(X1, X2) → U51'(X1, X2)
a__U52'(X) → U52'(X)
a__U61'(X) → U61'(X)
a__U71'(X1, X2) → U71'(X1, X2)
a__U72'(X) → U72'(X)
a__isPal'(X) → isPal'(X)
a__U81'(X) → U81'(X)
a__isQid'(X) → isQid'(X)
a__isNePal'(X) → isNePal'(X)

Rewrite Strategy: INNERMOST

Infered types.

Rules:
a____'(__'(X, Y), Z) → a____'(mark'(X), a____'(mark'(Y), mark'(Z)))
a____'(X, nil') → mark'(X)
a____'(nil', X) → mark'(X)
a__U11'(tt') → tt'
a__U21'(tt', V2) → a__U22'(a__isList'(V2))
a__U22'(tt') → tt'
a__U31'(tt') → tt'
a__U41'(tt', V2) → a__U42'(a__isNeList'(V2))
a__U42'(tt') → tt'
a__U51'(tt', V2) → a__U52'(a__isList'(V2))
a__U52'(tt') → tt'
a__U61'(tt') → tt'
a__U71'(tt', P) → a__U72'(a__isPal'(P))
a__U72'(tt') → tt'
a__U81'(tt') → tt'
a__isList'(V) → a__U11'(a__isNeList'(V))
a__isList'(nil') → tt'
a__isList'(__'(V1, V2)) → a__U21'(a__isList'(V1), V2)
a__isNeList'(V) → a__U31'(a__isQid'(V))
a__isNeList'(__'(V1, V2)) → a__U41'(a__isList'(V1), V2)
a__isNeList'(__'(V1, V2)) → a__U51'(a__isNeList'(V1), V2)
a__isNePal'(V) → a__U61'(a__isQid'(V))
a__isNePal'(__'(I, __'(P, I))) → a__U71'(a__isQid'(I), P)
a__isPal'(V) → a__U81'(a__isNePal'(V))
a__isPal'(nil') → tt'
a__isQid'(a') → tt'
a__isQid'(e') → tt'
a__isQid'(i') → tt'
a__isQid'(o') → tt'
a__isQid'(u') → tt'
mark'(__'(X1, X2)) → a____'(mark'(X1), mark'(X2))
mark'(U11'(X)) → a__U11'(mark'(X))
mark'(U21'(X1, X2)) → a__U21'(mark'(X1), X2)
mark'(U22'(X)) → a__U22'(mark'(X))
mark'(isList'(X)) → a__isList'(X)
mark'(U31'(X)) → a__U31'(mark'(X))
mark'(U41'(X1, X2)) → a__U41'(mark'(X1), X2)
mark'(U42'(X)) → a__U42'(mark'(X))
mark'(isNeList'(X)) → a__isNeList'(X)
mark'(U51'(X1, X2)) → a__U51'(mark'(X1), X2)
mark'(U52'(X)) → a__U52'(mark'(X))
mark'(U61'(X)) → a__U61'(mark'(X))
mark'(U71'(X1, X2)) → a__U71'(mark'(X1), X2)
mark'(U72'(X)) → a__U72'(mark'(X))
mark'(isPal'(X)) → a__isPal'(X)
mark'(U81'(X)) → a__U81'(mark'(X))
mark'(isQid'(X)) → a__isQid'(X)
mark'(isNePal'(X)) → a__isNePal'(X)
mark'(nil') → nil'
mark'(tt') → tt'
mark'(a') → a'
mark'(e') → e'
mark'(i') → i'
mark'(o') → o'
mark'(u') → u'
a____'(X1, X2) → __'(X1, X2)
a__U11'(X) → U11'(X)
a__U21'(X1, X2) → U21'(X1, X2)
a__U22'(X) → U22'(X)
a__isList'(X) → isList'(X)
a__U31'(X) → U31'(X)
a__U41'(X1, X2) → U41'(X1, X2)
a__U42'(X) → U42'(X)
a__isNeList'(X) → isNeList'(X)
a__U51'(X1, X2) → U51'(X1, X2)
a__U52'(X) → U52'(X)
a__U61'(X) → U61'(X)
a__U71'(X1, X2) → U71'(X1, X2)
a__U72'(X) → U72'(X)
a__isPal'(X) → isPal'(X)
a__U81'(X) → U81'(X)
a__isQid'(X) → isQid'(X)
a__isNePal'(X) → isNePal'(X)

Types:
a____' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
__' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
mark' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
nil' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U11' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
tt' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U21' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U22' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__isList' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U31' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U41' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U42' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__isNeList' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U51' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U52' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U61' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U71' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U72' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__isPal' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__U81' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__isQid' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a__isNePal' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
a' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
e' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
i' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
o' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
u' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U11' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U21' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U22' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
isList' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U31' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U41' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U42' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
isNeList' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U51' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U52' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U61' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U71' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U72' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
isPal' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
U81' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
isQid' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
isNePal' :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal' → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
___hole___':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'1 :: __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'
___gen___':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'2 :: Nat → __':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'

Heuristically decided to analyse the following defined symbols:
a____', mark', a__U21', a__isList', a__U41', a__isNeList', a__U51', a__U71', a__isPal', a__isNePal'

They will be analysed ascendingly in the following order:
a____' = mark'
a__U21' < mark'
a__isList' < mark'
a__U41' < mark'
a__isNeList' < mark'
a__U51' < mark'
a__U71' < mark'
a__isPal' < mark'
a__isNePal' < mark'
a__U21' = a__isList'
a__U21' = a__U41'
a__U21' = a__isNeList'
a__U21' = a__U51'
a__isList' = a__U41'
a__isList' = a__isNeList'
a__isList' = a__U51'
a__U41' = a__isNeList'
a__U41' = a__U51'
a__isNeList' = a__U51'
a__U71' = a__isPal'
a__U71' = a__isNePal'
a__isPal' = a__isNePal'

Generator Equations:
___gen___':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'2(0) ⇔ nil'
___gen___':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'2(+(x, 1)) ⇔ __'(___gen___':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'2(x), nil')

The following defined symbols remain to be analysed:
a__isPal', a____', mark', a__U21', a__isList', a__U41', a__isNeList', a__U51', a__U71', a__isNePal'

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

The following defined symbols remain to be analysed:
a__isNePal', a____', mark', a__U21', a__isList', a__U41', a__isNeList', a__U51', a__U71'

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

The following defined symbols remain to be analysed:
a__U71', a____', mark', a__U21', a__isList', a__U41', a__isNeList', a__U51'

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

The following defined symbols remain to be analysed:
a__isList', a____', mark', a__U21', a__U41', a__isNeList', a__U51'

They will be analysed ascendingly in the following order:
a____' = mark'
a__U21' < mark'
a__isList' < mark'
a__U41' < mark'
a__isNeList' < mark'
a__U51' < mark'
a__U21' = a__isList'
a__U21' = a__U41'
a__U21' = a__isNeList'
a__U21' = a__U51'
a__isList' = a__U41'
a__isList' = a__isNeList'
a__isList' = a__U51'
a__U41' = a__isNeList'
a__U41' = a__U51'
a__isNeList' = a__U51'

Proved the following rewrite lemma:
a__isList'(___gen___':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'2(___n282)) → tt', rt ∈ Ω(1 + _{__n282})

Induction Base:
a__isList'(___gen___':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'2(0)) →_R^Ω(1)
tt'

Induction Step:
a__isList'(___gen___':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'2(+(___$n283, 1))) →_R^Ω(1)
a__U21'(a__isList'(___gen___':nil':tt':a':e':i':o':u':U11':U21':U22':isList':U31':U41':U42':isNeList':U51':U52':U61':U71':U72':isPal':U81':isQid':isNePal'2(___$n283)), nil') →_IH
a__U21'(tt', nil') →_R^Ω(1)
a__U22'(a__isList'(nil')) →_R^Ω(1)
a__U22'(tt') →_R^Ω(1)
tt'

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