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

a__zeros → cons(0, zeros)
a__U11(tt, L) → s(a__length(mark(L)))
a__U21(tt) → nil
a__U31(tt, IL, M, N) → cons(mark(N), take(M, IL))
a__and(tt, X) → mark(X)
a__isNat(0) → tt
a__isNat(length(V1)) → a__isNatList(V1)
a__isNat(s(V1)) → a__isNat(V1)
a__isNatIList(V) → a__isNatList(V)
a__isNatIList(zeros) → tt
a__isNatIList(cons(V1, V2)) → a__and(a__isNat(V1), isNatIList(V2))
a__isNatList(nil) → tt
a__isNatList(cons(V1, V2)) → a__and(a__isNat(V1), isNatList(V2))
a__isNatList(take(V1, V2)) → a__and(a__isNat(V1), isNatIList(V2))
a__length(nil) → 0
a__length(cons(N, L)) → a__U11(a__and(a__isNatList(L), isNat(N)), L)
a__take(0, IL) → a__U21(a__isNatIList(IL))
a__take(s(M), cons(N, IL)) → a__U31(a__and(a__isNatIList(IL), and(isNat(M), isNat(N))), IL, M, N)
mark(zeros) → a__zeros
mark(U11(X1, X2)) → a__U11(mark(X1), X2)
mark(length(X)) → a__length(mark(X))
mark(U21(X)) → a__U21(mark(X))
mark(U31(X1, X2, X3, X4)) → a__U31(mark(X1), X2, X3, X4)
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(and(X1, X2)) → a__and(mark(X1), X2)
mark(isNat(X)) → a__isNat(X)
mark(isNatList(X)) → a__isNatList(X)
mark(isNatIList(X)) → a__isNatIList(X)
mark(cons(X1, X2)) → cons(mark(X1), X2)
mark(0) → 0
mark(tt) → tt
mark(s(X)) → s(mark(X))
mark(nil) → nil
a__zeros → zeros
a__U11(X1, X2) → U11(X1, X2)
a__length(X) → length(X)
a__U21(X) → U21(X)
a__U31(X1, X2, X3, X4) → U31(X1, X2, X3, X4)
a__take(X1, X2) → take(X1, X2)
a__and(X1, X2) → and(X1, X2)
a__isNat(X) → isNat(X)
a__isNatList(X) → isNatList(X)
a__isNatIList(X) → isNatIList(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__zeros' → cons'(0', zeros')
a__U11'(tt', L) → s'(a__length'(mark'(L)))
a__U21'(tt') → nil'
a__U31'(tt', IL, M, N) → cons'(mark'(N), take'(M, IL))
a__and'(tt', X) → mark'(X)
a__isNat'(0') → tt'
a__isNat'(length'(V1)) → a__isNatList'(V1)
a__isNat'(s'(V1)) → a__isNat'(V1)
a__isNatIList'(V) → a__isNatList'(V)
a__isNatIList'(zeros') → tt'
a__isNatIList'(cons'(V1, V2)) → a__and'(a__isNat'(V1), isNatIList'(V2))
a__isNatList'(nil') → tt'
a__isNatList'(cons'(V1, V2)) → a__and'(a__isNat'(V1), isNatList'(V2))
a__isNatList'(take'(V1, V2)) → a__and'(a__isNat'(V1), isNatIList'(V2))
a__length'(nil') → 0'
a__length'(cons'(N, L)) → a__U11'(a__and'(a__isNatList'(L), isNat'(N)), L)
a__take'(0', IL) → a__U21'(a__isNatIList'(IL))
a__take'(s'(M), cons'(N, IL)) → a__U31'(a__and'(a__isNatIList'(IL), and'(isNat'(M), isNat'(N))), IL, M, N)
mark'(zeros') → a__zeros'
mark'(U11'(X1, X2)) → a__U11'(mark'(X1), X2)
mark'(length'(X)) → a__length'(mark'(X))
mark'(U21'(X)) → a__U21'(mark'(X))
mark'(U31'(X1, X2, X3, X4)) → a__U31'(mark'(X1), X2, X3, X4)
mark'(take'(X1, X2)) → a__take'(mark'(X1), mark'(X2))
mark'(and'(X1, X2)) → a__and'(mark'(X1), X2)
mark'(isNat'(X)) → a__isNat'(X)
mark'(isNatList'(X)) → a__isNatList'(X)
mark'(isNatIList'(X)) → a__isNatIList'(X)
mark'(cons'(X1, X2)) → cons'(mark'(X1), X2)
mark'(0') → 0'
mark'(tt') → tt'
mark'(s'(X)) → s'(mark'(X))
mark'(nil') → nil'
a__zeros' → zeros'
a__U11'(X1, X2) → U11'(X1, X2)
a__length'(X) → length'(X)
a__U21'(X) → U21'(X)
a__U31'(X1, X2, X3, X4) → U31'(X1, X2, X3, X4)
a__take'(X1, X2) → take'(X1, X2)
a__and'(X1, X2) → and'(X1, X2)
a__isNat'(X) → isNat'(X)
a__isNatList'(X) → isNatList'(X)
a__isNatIList'(X) → isNatIList'(X)

Rewrite Strategy: INNERMOST

Infered types.

Rules:
a__zeros' → cons'(0', zeros')
a__U11'(tt', L) → s'(a__length'(mark'(L)))
a__U21'(tt') → nil'
a__U31'(tt', IL, M, N) → cons'(mark'(N), take'(M, IL))
a__and'(tt', X) → mark'(X)
a__isNat'(0') → tt'
a__isNat'(length'(V1)) → a__isNatList'(V1)
a__isNat'(s'(V1)) → a__isNat'(V1)
a__isNatIList'(V) → a__isNatList'(V)
a__isNatIList'(zeros') → tt'
a__isNatIList'(cons'(V1, V2)) → a__and'(a__isNat'(V1), isNatIList'(V2))
a__isNatList'(nil') → tt'
a__isNatList'(cons'(V1, V2)) → a__and'(a__isNat'(V1), isNatList'(V2))
a__isNatList'(take'(V1, V2)) → a__and'(a__isNat'(V1), isNatIList'(V2))
a__length'(nil') → 0'
a__length'(cons'(N, L)) → a__U11'(a__and'(a__isNatList'(L), isNat'(N)), L)
a__take'(0', IL) → a__U21'(a__isNatIList'(IL))
a__take'(s'(M), cons'(N, IL)) → a__U31'(a__and'(a__isNatIList'(IL), and'(isNat'(M), isNat'(N))), IL, M, N)
mark'(zeros') → a__zeros'
mark'(U11'(X1, X2)) → a__U11'(mark'(X1), X2)
mark'(length'(X)) → a__length'(mark'(X))
mark'(U21'(X)) → a__U21'(mark'(X))
mark'(U31'(X1, X2, X3, X4)) → a__U31'(mark'(X1), X2, X3, X4)
mark'(take'(X1, X2)) → a__take'(mark'(X1), mark'(X2))
mark'(and'(X1, X2)) → a__and'(mark'(X1), X2)
mark'(isNat'(X)) → a__isNat'(X)
mark'(isNatList'(X)) → a__isNatList'(X)
mark'(isNatIList'(X)) → a__isNatIList'(X)
mark'(cons'(X1, X2)) → cons'(mark'(X1), X2)
mark'(0') → 0'
mark'(tt') → tt'
mark'(s'(X)) → s'(mark'(X))
mark'(nil') → nil'
a__zeros' → zeros'
a__U11'(X1, X2) → U11'(X1, X2)
a__length'(X) → length'(X)
a__U21'(X) → U21'(X)
a__U31'(X1, X2, X3, X4) → U31'(X1, X2, X3, X4)
a__take'(X1, X2) → take'(X1, X2)
a__and'(X1, X2) → and'(X1, X2)
a__isNat'(X) → isNat'(X)
a__isNatList'(X) → isNatList'(X)
a__isNatIList'(X) → isNatIList'(X)

Types:
a__zeros' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
cons' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
0' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
zeros' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
a__U11' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
tt' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
s' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
a__length' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
mark' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
a__U21' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
nil' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
a__U31' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
take' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
a__and' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
a__isNat' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
length' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
a__isNatList' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
a__isNatIList' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
isNatIList' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
isNatList' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
isNat' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
a__take' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
and' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
U11' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
U21' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
U31' :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31' → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
_hole_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'1 :: 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'
_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2 :: Nat → 0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'

Heuristically decided to analyse the following defined symbols:
a__U11', a__length', mark', a__U31', a__and', a__isNat', a__isNatList', a__isNatIList'

They will be analysed ascendingly in the following order:
a__U11' = a__length'
a__U11' = mark'
a__U11' = a__U31'
a__U11' = a__and'
a__U11' = a__isNat'
a__U11' = a__isNatList'
a__U11' = a__isNatIList'
a__length' = mark'
a__length' = a__U31'
a__length' = a__and'
a__length' = a__isNat'
a__length' = a__isNatList'
a__length' = a__isNatIList'
mark' = a__U31'
mark' = a__and'
mark' = a__isNat'
mark' = a__isNatList'
mark' = a__isNatIList'
a__U31' = a__and'
a__U31' = a__isNat'
a__U31' = a__isNatList'
a__U31' = a__isNatIList'
a__and' = a__isNat'
a__and' = a__isNatList'
a__and' = a__isNatIList'
a__isNat' = a__isNatList'
a__isNat' = a__isNatIList'
a__isNatList' = a__isNatIList'

Generator Equations:
_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(0) ⇔ 0'
_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(+(x, 1)) ⇔ cons'(_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(x), 0')

The following defined symbols remain to be analysed:
a__length', a__U11', mark', a__U31', a__and', a__isNat', a__isNatList', a__isNatIList'

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

The following defined symbols remain to be analysed:
a__U11', mark', a__U31', a__and', a__isNat', a__isNatList', a__isNatIList'

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

The following defined symbols remain to be analysed:
mark', a__U31', a__and', a__isNat', a__isNatList', a__isNatIList'

Proved the following rewrite lemma:
mark'(_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(_n170)) → _gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(_n170), rt ∈ Ω(1 + _n170)

Induction Base:
mark'(_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(0)) →_R^Ω(1)
0'

Induction Step:
mark'(_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(+(_$n171, 1))) →_R^Ω(1)
cons'(mark'(_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(_$n171)), 0') →_IH
cons'(_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(_$n171), 0')

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

Lemmas:
mark'(_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(_n170)) → _gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(_n170), rt ∈ Ω(1 + _n170)

The following defined symbols remain to be analysed:
a__U31', a__U11', a__length', a__and', a__isNat', a__isNatList', a__isNatIList'

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

The following defined symbols remain to be analysed:
a__and', a__U11', a__length', a__isNat', a__isNatList', a__isNatIList'

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

The following defined symbols remain to be analysed:
a__isNat', a__U11', a__length', a__isNatList', a__isNatIList'

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

The following defined symbols remain to be analysed:
a__isNatList', a__U11', a__length', a__isNatIList'

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

The following defined symbols remain to be analysed:
a__isNatIList', a__U11', a__length'

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

The following defined symbols remain to be analysed:
a__length', a__U11'

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

The following defined symbols remain to be analysed:
a__U11'

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

No more defined symbols left to analyse.

The lowerbound Ω(n) was proven with the following lemma:
mark'(_gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(_n170)) → _gen_0':zeros':cons':tt':s':nil':take':length':isNatIList':isNatList':isNat':and':U11':U21':U31'2(_n170), rt ∈ Ω(1 + _n170)