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__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__length(nil) → 0
a__length(cons(N, L)) → a__U11(a__and(a__isNatList(L), isNat(N)), L)
mark(zeros) → a__zeros
mark(U11(X1, X2)) → a__U11(mark(X1), X2)
mark(length(X)) → a__length(mark(X))
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__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__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__length'(nil') → 0'
a__length'(cons'(N, L)) → a__U11'(a__and'(a__isNatList'(L), isNat'(N)), L)
mark'(zeros') → a__zeros'
mark'(U11'(X1, X2)) → a__U11'(mark'(X1), X2)
mark'(length'(X)) → a__length'(mark'(X))
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__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__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__length'(nil') → 0'
a__length'(cons'(N, L)) → a__U11'(a__and'(a__isNatList'(L), isNat'(N)), L)
mark'(zeros') → a__zeros'
mark'(U11'(X1, X2)) → a__U11'(mark'(X1), X2)
mark'(length'(X)) → a__length'(mark'(X))
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__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':length':isNatIList':nil':isNatList':isNat':U11':and'
cons' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
0' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
zeros' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
a__U11' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
tt' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
s' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
a__length' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
mark' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
a__and' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
a__isNat' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
length' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
a__isNatList' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
a__isNatIList' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
isNatIList' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
nil' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
isNatList' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
isNat' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
U11' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
and' :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and' → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
_hole_0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'1 :: 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'
_gen_0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'2 :: Nat → 0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'

Heuristically decided to analyse the following defined symbols:
a__U11', a__length', mark', 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__and'
a__U11' = a__isNat'
a__U11' = a__isNatList'
a__U11' = a__isNatIList'
a__length' = mark'
a__length' = a__and'
a__length' = a__isNat'
a__length' = a__isNatList'
a__length' = a__isNatIList'
mark' = a__and'
mark' = a__isNat'
mark' = a__isNatList'
mark' = 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':length':isNatIList':nil':isNatList':isNat':U11':and'2(0) ⇔ 0'
_gen_0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'2(+(x, 1)) ⇔ cons'(_gen_0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'2(x), 0')

The following defined symbols remain to be analysed:
a__length', a__U11', mark', 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__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__and', a__isNat', a__isNatList', a__isNatIList'

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

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

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

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

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

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':length':isNatIList':nil':isNatList':isNat':U11':and'2(_n142)) → _gen_0':zeros':cons':tt':s':length':isNatIList':nil':isNatList':isNat':U11':and'2(_n142), rt ∈ Ω(1 + _n142)