eq(n__0, n__0) → true
eq(n__s(X), n__s(Y)) → eq(activate(X), activate(Y))
eq(X, Y) → false
inf(X) → cons(X, n__inf(s(X)))
take(0, X) → nil
take(s(X), cons(Y, L)) → cons(activate(Y), n__take(activate(X), activate(L)))
length(nil) → 0
length(cons(X, L)) → s(n__length(activate(L)))
0 → n__0
s(X) → n__s(X)
inf(X) → n__inf(X)
take(X1, X2) → n__take(X1, X2)
length(X) → n__length(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(n__inf(X)) → inf(X)
activate(n__take(X1, X2)) → take(X1, X2)
activate(n__length(X)) → length(X)
activate(X) → X
Renamed function symbols to avoid clashes with predefined symbol.
Runtime Complexity TRS:
The TRS R consists of the following rules:
eq'(n__0', n__0') → true'
eq'(n__s'(X), n__s'(Y)) → eq'(activate'(X), activate'(Y))
eq'(X, Y) → false'
inf'(X) → cons'(X, n__inf'(s'(X)))
take'(0', X) → nil'
take'(s'(X), cons'(Y, L)) → cons'(activate'(Y), n__take'(activate'(X), activate'(L)))
length'(nil') → 0'
length'(cons'(X, L)) → s'(n__length'(activate'(L)))
0' → n__0'
s'(X) → n__s'(X)
inf'(X) → n__inf'(X)
take'(X1, X2) → n__take'(X1, X2)
length'(X) → n__length'(X)
activate'(n__0') → 0'
activate'(n__s'(X)) → s'(X)
activate'(n__inf'(X)) → inf'(X)
activate'(n__take'(X1, X2)) → take'(X1, X2)
activate'(n__length'(X)) → length'(X)
activate'(X) → X
Infered types.
Rules:
eq'(n__0', n__0') → true'
eq'(n__s'(X), n__s'(Y)) → eq'(activate'(X), activate'(Y))
eq'(X, Y) → false'
inf'(X) → cons'(X, n__inf'(s'(X)))
take'(0', X) → nil'
take'(s'(X), cons'(Y, L)) → cons'(activate'(Y), n__take'(activate'(X), activate'(L)))
length'(nil') → 0'
length'(cons'(X, L)) → s'(n__length'(activate'(L)))
0' → n__0'
s'(X) → n__s'(X)
inf'(X) → n__inf'(X)
take'(X1, X2) → n__take'(X1, X2)
length'(X) → n__length'(X)
activate'(n__0') → 0'
activate'(n__s'(X)) → s'(X)
activate'(n__inf'(X)) → inf'(X)
activate'(n__take'(X1, X2)) → take'(X1, X2)
activate'(n__length'(X)) → length'(X)
activate'(X) → X
Types:
eq' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → true':false'
n__0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
true' :: true':false'
n__s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
activate' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
false' :: true':false'
inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
cons' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
nil' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
_hole_true':false'1 :: true':false'
_hole_n__0':n__s':n__inf':cons':nil':n__take':n__length'2 :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3 :: Nat → n__0':n__s':n__inf':cons':nil':n__take':n__length'
Heuristically decided to analyse the following defined symbols:
eq', activate', length'
They will be analysed ascendingly in the following order:
activate' < eq'
activate' = length'
Rules:
eq'(n__0', n__0') → true'
eq'(n__s'(X), n__s'(Y)) → eq'(activate'(X), activate'(Y))
eq'(X, Y) → false'
inf'(X) → cons'(X, n__inf'(s'(X)))
take'(0', X) → nil'
take'(s'(X), cons'(Y, L)) → cons'(activate'(Y), n__take'(activate'(X), activate'(L)))
length'(nil') → 0'
length'(cons'(X, L)) → s'(n__length'(activate'(L)))
0' → n__0'
s'(X) → n__s'(X)
inf'(X) → n__inf'(X)
take'(X1, X2) → n__take'(X1, X2)
length'(X) → n__length'(X)
activate'(n__0') → 0'
activate'(n__s'(X)) → s'(X)
activate'(n__inf'(X)) → inf'(X)
activate'(n__take'(X1, X2)) → take'(X1, X2)
activate'(n__length'(X)) → length'(X)
activate'(X) → X
Types:
eq' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → true':false'
n__0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
true' :: true':false'
n__s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
activate' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
false' :: true':false'
inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
cons' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
nil' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
_hole_true':false'1 :: true':false'
_hole_n__0':n__s':n__inf':cons':nil':n__take':n__length'2 :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3 :: Nat → n__0':n__s':n__inf':cons':nil':n__take':n__length'
Generator Equations:
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(0) ⇔ n__0'
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(x, 1)) ⇔ n__s'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(x))
The following defined symbols remain to be analysed:
length', eq', activate'
They will be analysed ascendingly in the following order:
activate' < eq'
activate' = length'
Could not prove a rewrite lemma for the defined symbol length'.
Rules:
eq'(n__0', n__0') → true'
eq'(n__s'(X), n__s'(Y)) → eq'(activate'(X), activate'(Y))
eq'(X, Y) → false'
inf'(X) → cons'(X, n__inf'(s'(X)))
take'(0', X) → nil'
take'(s'(X), cons'(Y, L)) → cons'(activate'(Y), n__take'(activate'(X), activate'(L)))
length'(nil') → 0'
length'(cons'(X, L)) → s'(n__length'(activate'(L)))
0' → n__0'
s'(X) → n__s'(X)
inf'(X) → n__inf'(X)
take'(X1, X2) → n__take'(X1, X2)
length'(X) → n__length'(X)
activate'(n__0') → 0'
activate'(n__s'(X)) → s'(X)
activate'(n__inf'(X)) → inf'(X)
activate'(n__take'(X1, X2)) → take'(X1, X2)
activate'(n__length'(X)) → length'(X)
activate'(X) → X
Types:
eq' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → true':false'
n__0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
true' :: true':false'
n__s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
activate' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
false' :: true':false'
inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
cons' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
nil' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
_hole_true':false'1 :: true':false'
_hole_n__0':n__s':n__inf':cons':nil':n__take':n__length'2 :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3 :: Nat → n__0':n__s':n__inf':cons':nil':n__take':n__length'
Generator Equations:
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(0) ⇔ n__0'
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(x, 1)) ⇔ n__s'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(x))
The following defined symbols remain to be analysed:
activate', eq'
They will be analysed ascendingly in the following order:
activate' < eq'
activate' = length'
Could not prove a rewrite lemma for the defined symbol activate'.
Rules:
eq'(n__0', n__0') → true'
eq'(n__s'(X), n__s'(Y)) → eq'(activate'(X), activate'(Y))
eq'(X, Y) → false'
inf'(X) → cons'(X, n__inf'(s'(X)))
take'(0', X) → nil'
take'(s'(X), cons'(Y, L)) → cons'(activate'(Y), n__take'(activate'(X), activate'(L)))
length'(nil') → 0'
length'(cons'(X, L)) → s'(n__length'(activate'(L)))
0' → n__0'
s'(X) → n__s'(X)
inf'(X) → n__inf'(X)
take'(X1, X2) → n__take'(X1, X2)
length'(X) → n__length'(X)
activate'(n__0') → 0'
activate'(n__s'(X)) → s'(X)
activate'(n__inf'(X)) → inf'(X)
activate'(n__take'(X1, X2)) → take'(X1, X2)
activate'(n__length'(X)) → length'(X)
activate'(X) → X
Types:
eq' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → true':false'
n__0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
true' :: true':false'
n__s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
activate' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
false' :: true':false'
inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
cons' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
nil' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
_hole_true':false'1 :: true':false'
_hole_n__0':n__s':n__inf':cons':nil':n__take':n__length'2 :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3 :: Nat → n__0':n__s':n__inf':cons':nil':n__take':n__length'
Generator Equations:
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(0) ⇔ n__0'
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(x, 1)) ⇔ n__s'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(x))
The following defined symbols remain to be analysed:
eq'
Proved the following rewrite lemma:
eq'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(1, _n235)), _gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(_n235)) → false', rt ∈ Ω(1 + n235)
Induction Base:
eq'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(1, 0)), _gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(0)) →RΩ(1)
false'
Induction Step:
eq'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(1, +(_$n236, 1))), _gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(_$n236, 1))) →RΩ(1)
eq'(activate'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(1, _$n236))), activate'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(_$n236))) →RΩ(1)
eq'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(1, _$n236)), activate'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(_$n236))) →RΩ(1)
eq'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(1, _$n236)), _gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(_$n236)) →IH
false'
We have rt ∈ Ω(n) and sz ∈ O(n). Thus, we have ircR ∈ Ω(n).
Rules:
eq'(n__0', n__0') → true'
eq'(n__s'(X), n__s'(Y)) → eq'(activate'(X), activate'(Y))
eq'(X, Y) → false'
inf'(X) → cons'(X, n__inf'(s'(X)))
take'(0', X) → nil'
take'(s'(X), cons'(Y, L)) → cons'(activate'(Y), n__take'(activate'(X), activate'(L)))
length'(nil') → 0'
length'(cons'(X, L)) → s'(n__length'(activate'(L)))
0' → n__0'
s'(X) → n__s'(X)
inf'(X) → n__inf'(X)
take'(X1, X2) → n__take'(X1, X2)
length'(X) → n__length'(X)
activate'(n__0') → 0'
activate'(n__s'(X)) → s'(X)
activate'(n__inf'(X)) → inf'(X)
activate'(n__take'(X1, X2)) → take'(X1, X2)
activate'(n__length'(X)) → length'(X)
activate'(X) → X
Types:
eq' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → true':false'
n__0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
true' :: true':false'
n__s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
activate' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
false' :: true':false'
inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
cons' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__inf' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
s' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
0' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
nil' :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__take' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
n__length' :: n__0':n__s':n__inf':cons':nil':n__take':n__length' → n__0':n__s':n__inf':cons':nil':n__take':n__length'
_hole_true':false'1 :: true':false'
_hole_n__0':n__s':n__inf':cons':nil':n__take':n__length'2 :: n__0':n__s':n__inf':cons':nil':n__take':n__length'
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3 :: Nat → n__0':n__s':n__inf':cons':nil':n__take':n__length'
Lemmas:
eq'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(1, _n235)), _gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(_n235)) → false', rt ∈ Ω(1 + n235)
Generator Equations:
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(0) ⇔ n__0'
_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(x, 1)) ⇔ n__s'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(x))
No more defined symbols left to analyse.
The lowerbound Ω(n) was proven with the following lemma:
eq'(_gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(+(1, _n235)), _gen_n__0':n__s':n__inf':cons':nil':n__take':n__length'3(_n235)) → false', rt ∈ Ω(1 + n235)