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

a__zeros → cons(0, zeros)
a__U11(tt) → tt
a__U21(tt) → tt
a__U31(tt) → tt
a__U41(tt, V2) → a__U42(a__isNatIList(V2))
a__U42(tt) → tt
a__U51(tt, V2) → a__U52(a__isNatList(V2))
a__U52(tt) → tt
a__U61(tt, L, N) → a__U62(a__isNat(N), L)
a__U62(tt, L) → s(a__length(mark(L)))
a__isNat(0) → tt
a__isNat(length(V1)) → a__U11(a__isNatList(V1))
a__isNat(s(V1)) → a__U21(a__isNat(V1))
a__isNatIList(V) → a__U31(a__isNatList(V))
a__isNatIList(zeros) → tt
a__isNatIList(cons(V1, V2)) → a__U41(a__isNat(V1), V2)
a__isNatList(nil) → tt
a__isNatList(cons(V1, V2)) → a__U51(a__isNat(V1), V2)
a__length(nil) → 0
a__length(cons(N, L)) → a__U61(a__isNatList(L), L, N)
mark(zeros) → a__zeros
mark(U11(X)) → a__U11(mark(X))
mark(U21(X)) → a__U21(mark(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(isNatIList(X)) → a__isNatIList(X)
mark(U51(X1, X2)) → a__U51(mark(X1), X2)
mark(U52(X)) → a__U52(mark(X))
mark(isNatList(X)) → a__isNatList(X)
mark(U61(X1, X2, X3)) → a__U61(mark(X1), X2, X3)
mark(U62(X1, X2)) → a__U62(mark(X1), X2)
mark(isNat(X)) → a__isNat(X)
mark(length(X)) → a__length(mark(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(X) → U11(X)
a__U21(X) → U21(X)
a__U31(X) → U31(X)
a__U41(X1, X2) → U41(X1, X2)
a__U42(X) → U42(X)
a__isNatIList(X) → isNatIList(X)
a__U51(X1, X2) → U51(X1, X2)
a__U52(X) → U52(X)
a__isNatList(X) → isNatList(X)
a__U61(X1, X2, X3) → U61(X1, X2, X3)
a__U62(X1, X2) → U62(X1, X2)
a__isNat(X) → isNat(X)
a__length(X) → length(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') → tt'
a__U21'(tt') → tt'
a__U31'(tt') → tt'
a__U41'(tt', V2) → a__U42'(a__isNatIList'(V2))
a__U42'(tt') → tt'
a__U51'(tt', V2) → a__U52'(a__isNatList'(V2))
a__U52'(tt') → tt'
a__U61'(tt', L, N) → a__U62'(a__isNat'(N), L)
a__U62'(tt', L) → s'(a__length'(mark'(L)))
a__isNat'(0') → tt'
a__isNat'(length'(V1)) → a__U11'(a__isNatList'(V1))
a__isNat'(s'(V1)) → a__U21'(a__isNat'(V1))
a__isNatIList'(V) → a__U31'(a__isNatList'(V))
a__isNatIList'(zeros') → tt'
a__isNatIList'(cons'(V1, V2)) → a__U41'(a__isNat'(V1), V2)
a__isNatList'(nil') → tt'
a__isNatList'(cons'(V1, V2)) → a__U51'(a__isNat'(V1), V2)
a__length'(nil') → 0'
a__length'(cons'(N, L)) → a__U61'(a__isNatList'(L), L, N)
mark'(zeros') → a__zeros'
mark'(U11'(X)) → a__U11'(mark'(X))
mark'(U21'(X)) → a__U21'(mark'(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'(isNatIList'(X)) → a__isNatIList'(X)
mark'(U51'(X1, X2)) → a__U51'(mark'(X1), X2)
mark'(U52'(X)) → a__U52'(mark'(X))
mark'(isNatList'(X)) → a__isNatList'(X)
mark'(U61'(X1, X2, X3)) → a__U61'(mark'(X1), X2, X3)
mark'(U62'(X1, X2)) → a__U62'(mark'(X1), X2)
mark'(isNat'(X)) → a__isNat'(X)
mark'(length'(X)) → a__length'(mark'(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'(X) → U11'(X)
a__U21'(X) → U21'(X)
a__U31'(X) → U31'(X)
a__U41'(X1, X2) → U41'(X1, X2)
a__U42'(X) → U42'(X)
a__isNatIList'(X) → isNatIList'(X)
a__U51'(X1, X2) → U51'(X1, X2)
a__U52'(X) → U52'(X)
a__isNatList'(X) → isNatList'(X)
a__U61'(X1, X2, X3) → U61'(X1, X2, X3)
a__U62'(X1, X2) → U62'(X1, X2)
a__isNat'(X) → isNat'(X)
a__length'(X) → length'(X)

Rewrite Strategy: INNERMOST

Infered types.

Rules:
a__zeros' → cons'(0', zeros')
a__U11'(tt') → tt'
a__U21'(tt') → tt'
a__U31'(tt') → tt'
a__U41'(tt', V2) → a__U42'(a__isNatIList'(V2))
a__U42'(tt') → tt'
a__U51'(tt', V2) → a__U52'(a__isNatList'(V2))
a__U52'(tt') → tt'
a__U61'(tt', L, N) → a__U62'(a__isNat'(N), L)
a__U62'(tt', L) → s'(a__length'(mark'(L)))
a__isNat'(0') → tt'
a__isNat'(length'(V1)) → a__U11'(a__isNatList'(V1))
a__isNat'(s'(V1)) → a__U21'(a__isNat'(V1))
a__isNatIList'(V) → a__U31'(a__isNatList'(V))
a__isNatIList'(zeros') → tt'
a__isNatIList'(cons'(V1, V2)) → a__U41'(a__isNat'(V1), V2)
a__isNatList'(nil') → tt'
a__isNatList'(cons'(V1, V2)) → a__U51'(a__isNat'(V1), V2)
a__length'(nil') → 0'
a__length'(cons'(N, L)) → a__U61'(a__isNatList'(L), L, N)
mark'(zeros') → a__zeros'
mark'(U11'(X)) → a__U11'(mark'(X))
mark'(U21'(X)) → a__U21'(mark'(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'(isNatIList'(X)) → a__isNatIList'(X)
mark'(U51'(X1, X2)) → a__U51'(mark'(X1), X2)
mark'(U52'(X)) → a__U52'(mark'(X))
mark'(isNatList'(X)) → a__isNatList'(X)
mark'(U61'(X1, X2, X3)) → a__U61'(mark'(X1), X2, X3)
mark'(U62'(X1, X2)) → a__U62'(mark'(X1), X2)
mark'(isNat'(X)) → a__isNat'(X)
mark'(length'(X)) → a__length'(mark'(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'(X) → U11'(X)
a__U21'(X) → U21'(X)
a__U31'(X) → U31'(X)
a__U41'(X1, X2) → U41'(X1, X2)
a__U42'(X) → U42'(X)
a__isNatIList'(X) → isNatIList'(X)
a__U51'(X1, X2) → U51'(X1, X2)
a__U52'(X) → U52'(X)
a__isNatList'(X) → isNatList'(X)
a__U61'(X1, X2, X3) → U61'(X1, X2, X3)
a__U62'(X1, X2) → U62'(X1, X2)
a__isNat'(X) → isNat'(X)
a__length'(X) → length'(X)

Types:
a__zeros' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
cons' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
0' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
zeros' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__U11' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
tt' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__U21' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__U31' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__U41' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__U42' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__isNatIList' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__U51' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__U52' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__isNatList' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__U61' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__U62' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__isNat' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
s' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
a__length' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
mark' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
length' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
nil' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
U11' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
U21' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
U31' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
U41' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
U42' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
isNatIList' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
U51' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
U52' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
isNatList' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
U61' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
U62' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
isNat' :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat' → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
_hole_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'1 :: 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'
_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2 :: Nat → 0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'

Heuristically decided to analyse the following defined symbols:
a__U41', a__isNatIList', a__U51', a__isNatList', a__U61', a__U62', a__isNat', a__length', mark'

They will be analysed ascendingly in the following order:
a__U41' = a__isNatIList'
a__U41' < mark'
a__isNatList' < a__isNatIList'
a__isNat' < a__isNatIList'
a__isNatIList' < mark'
a__U51' = a__isNatList'
a__U51' = a__isNat'
a__U51' < mark'
a__isNatList' = a__isNat'
a__isNatList' < a__length'
a__isNatList' < mark'
a__U61' = a__U62'
a__isNat' < a__U61'
a__U61' = a__length'
a__U61' = mark'
a__U62' = a__length'
a__U62' = mark'
a__isNat' < mark'
a__length' = mark'

Generator Equations:
_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(0) ⇔ 0'
_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(+(x, 1)) ⇔ cons'(_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(x), 0')

The following defined symbols remain to be analysed:
a__isNatList', a__U41', a__isNatIList', a__U51', a__U61', a__U62', a__isNat', a__length', mark'

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

The following defined symbols remain to be analysed:
a__U51', a__U41', a__isNatIList', a__U61', a__U62', a__isNat', a__length', mark'

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

The following defined symbols remain to be analysed:
a__isNat', a__U41', a__isNatIList', a__U61', a__U62', a__length', mark'

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

The following defined symbols remain to be analysed:
a__isNatIList', a__U41', a__U61', a__U62', a__length', mark'

They will be analysed ascendingly in the following order:
a__U41' = a__isNatIList'
a__U41' < mark'
a__isNatIList' < mark'
a__U61' = a__U62'
a__U61' = a__length'
a__U61' = mark'
a__U62' = a__length'
a__U62' = mark'
a__length' = mark'

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

The following defined symbols remain to be analysed:
a__U41', a__U61', a__U62', a__length', mark'

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

The following defined symbols remain to be analysed:
a__U62', a__U61', a__length', mark'

They will be analysed ascendingly in the following order:
a__U61' = a__U62'
a__U61' = a__length'
a__U61' = mark'
a__U62' = a__length'
a__U62' = mark'
a__length' = mark'

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

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

They will be analysed ascendingly in the following order:
a__U61' = a__U62'
a__U61' = a__length'
a__U61' = mark'
a__U62' = a__length'
a__U62' = mark'
a__length' = mark'

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

The following defined symbols remain to be analysed:
a__U61', mark'

They will be analysed ascendingly in the following order:
a__U61' = a__U62'
a__U61' = a__length'
a__U61' = mark'
a__U62' = a__length'
a__U62' = mark'
a__length' = mark'

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

The following defined symbols remain to be analysed:
mark'

They will be analysed ascendingly in the following order:
a__U61' = a__U62'
a__U61' = a__length'
a__U61' = mark'
a__U62' = a__length'
a__U62' = mark'
a__length' = mark'

Proved the following rewrite lemma:
mark'(_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(_n518)) → _gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(_n518), rt ∈ Ω(1 + _n518)

Induction Base:
mark'(_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(0)) →_R^Ω(1)
0'

Induction Step:
mark'(_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(+(_$n519, 1))) →_R^Ω(1)
cons'(mark'(_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(_$n519)), 0') →_IH
cons'(_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(_$n519), 0')

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

Lemmas:
mark'(_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(_n518)) → _gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(_n518), rt ∈ Ω(1 + _n518)

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

They will be analysed ascendingly in the following order:
a__U61' = a__U62'
a__U61' = a__length'
a__U61' = mark'
a__U62' = a__length'
a__U62' = mark'
a__length' = mark'

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

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

They will be analysed ascendingly in the following order:
a__U61' = a__U62'
a__U61' = a__length'
a__U61' = mark'
a__U62' = a__length'
a__U62' = mark'
a__length' = mark'

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

The following defined symbols remain to be analysed:
a__U61'

They will be analysed ascendingly in the following order:
a__U61' = a__U62'
a__U61' = a__length'
a__U61' = mark'
a__U62' = a__length'
a__U62' = mark'
a__length' = mark'

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

No more defined symbols left to analyse.

The lowerbound Ω(n) was proven with the following lemma:
mark'(_gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(_n518)) → _gen_0':zeros':cons':tt':s':length':nil':U11':U21':U31':U41':U42':isNatIList':U51':U52':isNatList':U61':U62':isNat'2(_n518), rt ∈ Ω(1 + _n518)