### (0) Obligation:

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

0(#) → #
+(x, #) → x
+(#, x) → x
+(0(x), 0(y)) → 0(+(x, y))
+(0(x), 1(y)) → 1(+(x, y))
+(1(x), 0(y)) → 1(+(x, y))
+(1(x), 1(y)) → 0(+(+(x, y), 1(#)))
+(+(x, y), z) → +(x, +(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +(log'(x), 1(#)), #)
*(#, x) → #
*(0(x), y) → 0(*(x, y))
*(1(x), y) → +(0(*(x, y)), y)
*(*(x, y), z) → *(x, *(y, z))
*(x, +(y, z)) → +(*(x, y), *(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +(x, sum(l))
sum(app(l1, l2)) → +(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *(x, prod(l))
prod(app(l1, l2)) → *(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Rewrite Strategy: FULL

### (1) DecreasingLoopProof (EQUIVALENT transformation)

The following loop(s) give(s) rise to the lower bound Ω(2n):
The rewrite sequence
prod(cons(1(x322657_4), l)) →+ +(0(*(x322657_4, prod(l))), prod(l))
gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0,1].
The pumping substitution is [l / cons(1(x322657_4), l)].
The result substitution is [ ].

The rewrite sequence
prod(cons(1(x322657_4), l)) →+ +(0(*(x322657_4, prod(l))), prod(l))
gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
The pumping substitution is [l / cons(1(x322657_4), l)].
The result substitution is [ ].

### (3) RenamingProof (EQUIVALENT transformation)

Renamed function symbols to avoid clashes with predefined symbol.

### (4) Obligation:

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

0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

S is empty.
Rewrite Strategy: FULL

Infered types.

### (6) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

### (7) OrderProof (LOWER BOUND(ID) transformation)

Heuristically decided to analyse the following defined symbols:
+', -, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
+' < log'
+' < *'
+' < sum
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

### (8) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
+', -, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
+' < log'
+' < *'
+' < sum
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

### (9) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

Induction Base:
+'(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0))

Induction Step:
+'(gen_#:1:true:false3_4(+(n6_4, 1)), gen_#:1:true:false3_4(+(n6_4, 1))) →RΩ(1)
0(+'(+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)), 1(#))) →IH
0(+'(*5_4, 1(#)))

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

### (11) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
-, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

### (12) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)

Induction Base:
-(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →RΩ(1)
#

Induction Step:
-(gen_#:1:true:false3_4(+(n109048_4, 1)), gen_#:1:true:false3_4(+(n109048_4, 1))) →RΩ(1)
0(-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4))) →IH
0(gen_#:1:true:false3_4(0)) →RΩ(1)
#

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

### (14) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

### (15) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)

Induction Base:
eq(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →RΩ(1)
true

Induction Step:
eq(gen_#:1:true:false3_4(+(n111371_4, 1)), gen_#:1:true:false3_4(+(n111371_4, 1))) →RΩ(1)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) →IH
true

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

### (17) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
ge < log'
*' < prod
app < inter
mem < inter

### (18) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)

Induction Base:
ge(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →RΩ(1)
true

Induction Step:
ge(gen_#:1:true:false3_4(+(n144082_4, 1)), gen_#:1:true:false3_4(+(n144082_4, 1))) →RΩ(1)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) →IH
true

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

### (20) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
*' < prod
app < inter
mem < inter

### (21) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)

Induction Base:
log'(gen_#:1:true:false3_4(+(1, 0)))

Induction Step:
log'(gen_#:1:true:false3_4(+(1, +(n147901_4, 1)))) →RΩ(1)
+'(log'(gen_#:1:true:false3_4(+(1, n147901_4))), 1(#)) →IH
+'(*5_4, 1(#))

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

### (23) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
*', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
*' < prod
app < inter
mem < inter

### (24) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)

Induction Base:
*'(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →RΩ(1)
#

Induction Step:
*'(gen_#:1:true:false3_4(+(n244341_4, 1)), gen_#:1:true:false3_4(0)) →RΩ(1)
+'(0(*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0))), gen_#:1:true:false3_4(0)) →IH
+'(0(gen_#:1:true:false3_4(0)), gen_#:1:true:false3_4(0)) →RΩ(1)
+'(#, gen_#:1:true:false3_4(0)) →RΩ(1)
#

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

### (26) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
app < inter
mem < inter

### (27) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)

Induction Base:
app(gen_nil:cons4_4(0), gen_nil:cons4_4(b)) →RΩ(1)
gen_nil:cons4_4(b)

Induction Step:
app(gen_nil:cons4_4(+(n259236_4, 1)), gen_nil:cons4_4(b)) →RΩ(1)
cons(#, app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b))) →IH
cons(#, gen_nil:cons4_4(+(b, c259237_4)))

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

### (29) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
sum, prod, mem, inter

They will be analysed ascendingly in the following order:
mem < inter

### (30) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2612714)

Induction Base:
sum(gen_nil:cons4_4(0)) →RΩ(1)
0(#) →RΩ(1)
#

Induction Step:
sum(gen_nil:cons4_4(+(n261271_4, 1))) →RΩ(1)
+'(#, sum(gen_nil:cons4_4(n261271_4))) →IH
+'(#, gen_#:1:true:false3_4(0)) →RΩ(1)
#

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

### (32) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2612714)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
prod, mem, inter

They will be analysed ascendingly in the following order:
mem < inter

### (33) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n2677554)

Induction Base:
prod(gen_nil:cons4_4(0))

Induction Step:
prod(gen_nil:cons4_4(+(n267755_4, 1))) →RΩ(1)
*'(#, prod(gen_nil:cons4_4(n267755_4))) →IH
*'(#, *5_4)

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

### (35) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2612714)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n2677554)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
mem, inter

They will be analysed ascendingly in the following order:
mem < inter

### (36) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4)) → *5_4, rt ∈ Ω(n2798994)

Induction Base:
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(0))

Induction Step:
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(+(n279899_4, 1))) →RΩ(1)
if(eq(gen_#:1:true:false3_4(0), #), true, mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4))) →LΩ(1)
if(true, true, mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4))) →IH
if(true, true, *5_4)

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

### (38) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2612714)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n2677554)
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4)) → *5_4, rt ∈ Ω(n2798994)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
inter

### (39) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol inter.

### (40) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2612714)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n2677554)
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4)) → *5_4, rt ∈ Ω(n2798994)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (41) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (43) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2612714)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n2677554)
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4)) → *5_4, rt ∈ Ω(n2798994)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (44) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (46) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2612714)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n2677554)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (47) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (49) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2612714)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (50) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (52) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n2592364)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (53) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (55) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n2443414)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (56) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (58) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n1479014)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (59) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (61) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n1440824)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (62) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (64) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n1113714)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (65) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (67) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n1090484)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (68) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

### (70) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

### (71) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n64)