cond1(true, x) → cond2(even(x), x)
cond2(true, x) → cond1(neq(x, 0), div2(x))
cond2(false, x) → cond1(neq(x, 0), p(x))
neq(0, 0) → false
neq(0, s(x)) → true
neq(s(x), 0) → true
neq(s(x), s(y)) → neq(x, y)
even(0) → true
even(s(0)) → false
even(s(s(x))) → even(x)
div2(0) → 0
div2(s(0)) → 0
div2(s(s(x))) → s(div2(x))
p(0) → 0
p(s(x)) → x
Renamed function symbols to avoid clashes with predefined symbol.
Runtime Complexity TRS:
The TRS R consists of the following rules:
cond1'(true', x) → cond2'(even'(x), x)
cond2'(true', x) → cond1'(neq'(x, 0'), div2'(x))
cond2'(false', x) → cond1'(neq'(x, 0'), p'(x))
neq'(0', 0') → false'
neq'(0', s'(x)) → true'
neq'(s'(x), 0') → true'
neq'(s'(x), s'(y')) → neq'(x, y')
even'(0') → true'
even'(s'(0')) → false'
even'(s'(s'(x))) → even'(x)
div2'(0') → 0'
div2'(s'(0')) → 0'
div2'(s'(s'(x))) → s'(div2'(x))
p'(0') → 0'
p'(s'(x)) → x
Infered types.
Rules:
cond1'(true', x) → cond2'(even'(x), x)
cond2'(true', x) → cond1'(neq'(x, 0'), div2'(x))
cond2'(false', x) → cond1'(neq'(x, 0'), p'(x))
neq'(0', 0') → false'
neq'(0', s'(x)) → true'
neq'(s'(x), 0') → true'
neq'(s'(x), s'(y')) → neq'(x, y')
even'(0') → true'
even'(s'(0')) → false'
even'(s'(s'(x))) → even'(x)
div2'(0') → 0'
div2'(s'(0')) → 0'
div2'(s'(s'(x))) → s'(div2'(x))
p'(0') → 0'
p'(s'(x)) → x
Types:
cond1' :: true':false' → 0':s':y' → cond1':cond2'
true' :: true':false'
cond2' :: true':false' → 0':s':y' → cond1':cond2'
even' :: 0':s':y' → true':false'
neq' :: 0':s':y' → 0':s':y' → true':false'
0' :: 0':s':y'
div2' :: 0':s':y' → 0':s':y'
false' :: true':false'
p' :: 0':s':y' → 0':s':y'
s' :: 0':s':y' → 0':s':y'
y' :: 0':s':y'
_hole_cond1':cond2'1 :: cond1':cond2'
_hole_true':false'2 :: true':false'
_hole_0':s':y'3 :: 0':s':y'
_gen_0':s':y'4 :: Nat → 0':s':y'
Heuristically decided to analyse the following defined symbols:
cond1', cond2', even', neq', div2'
They will be analysed ascendingly in the following order:
cond1' = cond2'
even' < cond1'
neq' < cond2'
div2' < cond2'
Rules:
cond1'(true', x) → cond2'(even'(x), x)
cond2'(true', x) → cond1'(neq'(x, 0'), div2'(x))
cond2'(false', x) → cond1'(neq'(x, 0'), p'(x))
neq'(0', 0') → false'
neq'(0', s'(x)) → true'
neq'(s'(x), 0') → true'
neq'(s'(x), s'(y')) → neq'(x, y')
even'(0') → true'
even'(s'(0')) → false'
even'(s'(s'(x))) → even'(x)
div2'(0') → 0'
div2'(s'(0')) → 0'
div2'(s'(s'(x))) → s'(div2'(x))
p'(0') → 0'
p'(s'(x)) → x
Types:
cond1' :: true':false' → 0':s':y' → cond1':cond2'
true' :: true':false'
cond2' :: true':false' → 0':s':y' → cond1':cond2'
even' :: 0':s':y' → true':false'
neq' :: 0':s':y' → 0':s':y' → true':false'
0' :: 0':s':y'
div2' :: 0':s':y' → 0':s':y'
false' :: true':false'
p' :: 0':s':y' → 0':s':y'
s' :: 0':s':y' → 0':s':y'
y' :: 0':s':y'
_hole_cond1':cond2'1 :: cond1':cond2'
_hole_true':false'2 :: true':false'
_hole_0':s':y'3 :: 0':s':y'
_gen_0':s':y'4 :: Nat → 0':s':y'
Generator Equations:
_gen_0':s':y'4(0) ⇔ 0'
_gen_0':s':y'4(+(x, 1)) ⇔ s'(_gen_0':s':y'4(x))
The following defined symbols remain to be analysed:
even', cond1', cond2', neq', div2'
They will be analysed ascendingly in the following order:
cond1' = cond2'
even' < cond1'
neq' < cond2'
div2' < cond2'
Proved the following rewrite lemma:
even'(_gen_0':s':y'4(*(2, _n6))) → true', rt ∈ Ω(1 + n6)
Induction Base:
even'(_gen_0':s':y'4(*(2, 0))) →RΩ(1)
true'
Induction Step:
even'(_gen_0':s':y'4(*(2, +(_$n7, 1)))) →RΩ(1)
even'(_gen_0':s':y'4(*(2, _$n7))) →IH
true'
We have rt ∈ Ω(n) and sz ∈ O(n). Thus, we have ircR ∈ Ω(n).
Rules:
cond1'(true', x) → cond2'(even'(x), x)
cond2'(true', x) → cond1'(neq'(x, 0'), div2'(x))
cond2'(false', x) → cond1'(neq'(x, 0'), p'(x))
neq'(0', 0') → false'
neq'(0', s'(x)) → true'
neq'(s'(x), 0') → true'
neq'(s'(x), s'(y')) → neq'(x, y')
even'(0') → true'
even'(s'(0')) → false'
even'(s'(s'(x))) → even'(x)
div2'(0') → 0'
div2'(s'(0')) → 0'
div2'(s'(s'(x))) → s'(div2'(x))
p'(0') → 0'
p'(s'(x)) → x
Types:
cond1' :: true':false' → 0':s':y' → cond1':cond2'
true' :: true':false'
cond2' :: true':false' → 0':s':y' → cond1':cond2'
even' :: 0':s':y' → true':false'
neq' :: 0':s':y' → 0':s':y' → true':false'
0' :: 0':s':y'
div2' :: 0':s':y' → 0':s':y'
false' :: true':false'
p' :: 0':s':y' → 0':s':y'
s' :: 0':s':y' → 0':s':y'
y' :: 0':s':y'
_hole_cond1':cond2'1 :: cond1':cond2'
_hole_true':false'2 :: true':false'
_hole_0':s':y'3 :: 0':s':y'
_gen_0':s':y'4 :: Nat → 0':s':y'
Lemmas:
even'(_gen_0':s':y'4(*(2, _n6))) → true', rt ∈ Ω(1 + n6)
Generator Equations:
_gen_0':s':y'4(0) ⇔ 0'
_gen_0':s':y'4(+(x, 1)) ⇔ s'(_gen_0':s':y'4(x))
The following defined symbols remain to be analysed:
neq', cond1', cond2', div2'
They will be analysed ascendingly in the following order:
cond1' = cond2'
neq' < cond2'
div2' < cond2'
Could not prove a rewrite lemma for the defined symbol neq'.
Rules:
cond1'(true', x) → cond2'(even'(x), x)
cond2'(true', x) → cond1'(neq'(x, 0'), div2'(x))
cond2'(false', x) → cond1'(neq'(x, 0'), p'(x))
neq'(0', 0') → false'
neq'(0', s'(x)) → true'
neq'(s'(x), 0') → true'
neq'(s'(x), s'(y')) → neq'(x, y')
even'(0') → true'
even'(s'(0')) → false'
even'(s'(s'(x))) → even'(x)
div2'(0') → 0'
div2'(s'(0')) → 0'
div2'(s'(s'(x))) → s'(div2'(x))
p'(0') → 0'
p'(s'(x)) → x
Types:
cond1' :: true':false' → 0':s':y' → cond1':cond2'
true' :: true':false'
cond2' :: true':false' → 0':s':y' → cond1':cond2'
even' :: 0':s':y' → true':false'
neq' :: 0':s':y' → 0':s':y' → true':false'
0' :: 0':s':y'
div2' :: 0':s':y' → 0':s':y'
false' :: true':false'
p' :: 0':s':y' → 0':s':y'
s' :: 0':s':y' → 0':s':y'
y' :: 0':s':y'
_hole_cond1':cond2'1 :: cond1':cond2'
_hole_true':false'2 :: true':false'
_hole_0':s':y'3 :: 0':s':y'
_gen_0':s':y'4 :: Nat → 0':s':y'
Lemmas:
even'(_gen_0':s':y'4(*(2, _n6))) → true', rt ∈ Ω(1 + n6)
Generator Equations:
_gen_0':s':y'4(0) ⇔ 0'
_gen_0':s':y'4(+(x, 1)) ⇔ s'(_gen_0':s':y'4(x))
The following defined symbols remain to be analysed:
div2', cond1', cond2'
They will be analysed ascendingly in the following order:
cond1' = cond2'
div2' < cond2'
Proved the following rewrite lemma:
div2'(_gen_0':s':y'4(*(2, _n368))) → _gen_0':s':y'4(_n368), rt ∈ Ω(1 + n368)
Induction Base:
div2'(_gen_0':s':y'4(*(2, 0))) →RΩ(1)
0'
Induction Step:
div2'(_gen_0':s':y'4(*(2, +(_$n369, 1)))) →RΩ(1)
s'(div2'(_gen_0':s':y'4(*(2, _$n369)))) →IH
s'(_gen_0':s':y'4(_$n369))
We have rt ∈ Ω(n) and sz ∈ O(n). Thus, we have ircR ∈ Ω(n).
Rules:
cond1'(true', x) → cond2'(even'(x), x)
cond2'(true', x) → cond1'(neq'(x, 0'), div2'(x))
cond2'(false', x) → cond1'(neq'(x, 0'), p'(x))
neq'(0', 0') → false'
neq'(0', s'(x)) → true'
neq'(s'(x), 0') → true'
neq'(s'(x), s'(y')) → neq'(x, y')
even'(0') → true'
even'(s'(0')) → false'
even'(s'(s'(x))) → even'(x)
div2'(0') → 0'
div2'(s'(0')) → 0'
div2'(s'(s'(x))) → s'(div2'(x))
p'(0') → 0'
p'(s'(x)) → x
Types:
cond1' :: true':false' → 0':s':y' → cond1':cond2'
true' :: true':false'
cond2' :: true':false' → 0':s':y' → cond1':cond2'
even' :: 0':s':y' → true':false'
neq' :: 0':s':y' → 0':s':y' → true':false'
0' :: 0':s':y'
div2' :: 0':s':y' → 0':s':y'
false' :: true':false'
p' :: 0':s':y' → 0':s':y'
s' :: 0':s':y' → 0':s':y'
y' :: 0':s':y'
_hole_cond1':cond2'1 :: cond1':cond2'
_hole_true':false'2 :: true':false'
_hole_0':s':y'3 :: 0':s':y'
_gen_0':s':y'4 :: Nat → 0':s':y'
Lemmas:
even'(_gen_0':s':y'4(*(2, _n6))) → true', rt ∈ Ω(1 + n6)
div2'(_gen_0':s':y'4(*(2, _n368))) → _gen_0':s':y'4(_n368), rt ∈ Ω(1 + n368)
Generator Equations:
_gen_0':s':y'4(0) ⇔ 0'
_gen_0':s':y'4(+(x, 1)) ⇔ s'(_gen_0':s':y'4(x))
The following defined symbols remain to be analysed:
cond2', cond1'
They will be analysed ascendingly in the following order:
cond1' = cond2'
Could not prove a rewrite lemma for the defined symbol cond2'.
Rules:
cond1'(true', x) → cond2'(even'(x), x)
cond2'(true', x) → cond1'(neq'(x, 0'), div2'(x))
cond2'(false', x) → cond1'(neq'(x, 0'), p'(x))
neq'(0', 0') → false'
neq'(0', s'(x)) → true'
neq'(s'(x), 0') → true'
neq'(s'(x), s'(y')) → neq'(x, y')
even'(0') → true'
even'(s'(0')) → false'
even'(s'(s'(x))) → even'(x)
div2'(0') → 0'
div2'(s'(0')) → 0'
div2'(s'(s'(x))) → s'(div2'(x))
p'(0') → 0'
p'(s'(x)) → x
Types:
cond1' :: true':false' → 0':s':y' → cond1':cond2'
true' :: true':false'
cond2' :: true':false' → 0':s':y' → cond1':cond2'
even' :: 0':s':y' → true':false'
neq' :: 0':s':y' → 0':s':y' → true':false'
0' :: 0':s':y'
div2' :: 0':s':y' → 0':s':y'
false' :: true':false'
p' :: 0':s':y' → 0':s':y'
s' :: 0':s':y' → 0':s':y'
y' :: 0':s':y'
_hole_cond1':cond2'1 :: cond1':cond2'
_hole_true':false'2 :: true':false'
_hole_0':s':y'3 :: 0':s':y'
_gen_0':s':y'4 :: Nat → 0':s':y'
Lemmas:
even'(_gen_0':s':y'4(*(2, _n6))) → true', rt ∈ Ω(1 + n6)
div2'(_gen_0':s':y'4(*(2, _n368))) → _gen_0':s':y'4(_n368), rt ∈ Ω(1 + n368)
Generator Equations:
_gen_0':s':y'4(0) ⇔ 0'
_gen_0':s':y'4(+(x, 1)) ⇔ s'(_gen_0':s':y'4(x))
The following defined symbols remain to be analysed:
cond1'
They will be analysed ascendingly in the following order:
cond1' = cond2'
Could not prove a rewrite lemma for the defined symbol cond1'.
Rules:
cond1'(true', x) → cond2'(even'(x), x)
cond2'(true', x) → cond1'(neq'(x, 0'), div2'(x))
cond2'(false', x) → cond1'(neq'(x, 0'), p'(x))
neq'(0', 0') → false'
neq'(0', s'(x)) → true'
neq'(s'(x), 0') → true'
neq'(s'(x), s'(y')) → neq'(x, y')
even'(0') → true'
even'(s'(0')) → false'
even'(s'(s'(x))) → even'(x)
div2'(0') → 0'
div2'(s'(0')) → 0'
div2'(s'(s'(x))) → s'(div2'(x))
p'(0') → 0'
p'(s'(x)) → x
Types:
cond1' :: true':false' → 0':s':y' → cond1':cond2'
true' :: true':false'
cond2' :: true':false' → 0':s':y' → cond1':cond2'
even' :: 0':s':y' → true':false'
neq' :: 0':s':y' → 0':s':y' → true':false'
0' :: 0':s':y'
div2' :: 0':s':y' → 0':s':y'
false' :: true':false'
p' :: 0':s':y' → 0':s':y'
s' :: 0':s':y' → 0':s':y'
y' :: 0':s':y'
_hole_cond1':cond2'1 :: cond1':cond2'
_hole_true':false'2 :: true':false'
_hole_0':s':y'3 :: 0':s':y'
_gen_0':s':y'4 :: Nat → 0':s':y'
Lemmas:
even'(_gen_0':s':y'4(*(2, _n6))) → true', rt ∈ Ω(1 + n6)
div2'(_gen_0':s':y'4(*(2, _n368))) → _gen_0':s':y'4(_n368), rt ∈ Ω(1 + n368)
Generator Equations:
_gen_0':s':y'4(0) ⇔ 0'
_gen_0':s':y'4(+(x, 1)) ⇔ s'(_gen_0':s':y'4(x))
No more defined symbols left to analyse.
The lowerbound Ω(n) was proven with the following lemma:
even'(_gen_0':s':y'4(*(2, _n6))) → true', rt ∈ Ω(1 + n6)