/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^2), ?)
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).

(0) CpxTRS
(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxTRS
(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) typed CpxTrs
(5) OrderProof [LOWER BOUND(ID), 0 ms]
(6) typed CpxTrs
(7) RewriteLemmaProof [LOWER BOUND(ID), 295 ms]
(8) BEST
    (9) proven lower bound
        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
        (11) BOUNDS(n^1, INF)
    (12) typed CpxTrs
        (13) RewriteLemmaProof [LOWER BOUND(ID), 31 ms]
        (14) typed CpxTrs
        (15) RewriteLemmaProof [LOWER BOUND(ID), 41 ms]
        (16) BEST
            (17) proven lower bound
                (18) LowerBoundPropagationProof [FINISHED, 0 ms]
                (19) BOUNDS(n^2, INF)
            (20) typed CpxTrs
                (21) RewriteLemmaProof [LOWER BOUND(ID), 0 ms]
                (22) typed CpxTrs
                (23) RewriteLemmaProof [LOWER BOUND(ID), 3970 ms]
                (24) BOUNDS(1, INF)


----------------------------------------

(0)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).


The TRS R consists of the following rules:

   sum#1(Nil) -> 0
   sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
   map#2(Nil) -> Nil
   map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
   unfoldr#2(0) -> Nil
   unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
   mult#2(0, x2) -> 0
   mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
   plus#2(0, x8) -> x8
   plus#2(S(x4), x2) -> S(plus#2(x4, x2))
   main(0) -> 0
   main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(1) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(2)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).


The TRS R consists of the following rules:

   sum#1(Nil) -> 0'
   sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
   map#2(Nil) -> Nil
   map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
   unfoldr#2(0') -> Nil
   unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
   mult#2(0', x2) -> 0'
   mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
   plus#2(0', x8) -> x8
   plus#2(S(x4), x2) -> S(plus#2(x4, x2))
   main(0') -> 0'
   main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(4)
Obligation:
Innermost TRS:
Rules:
sum#1(Nil) -> 0'
sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
map#2(Nil) -> Nil
map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
unfoldr#2(0') -> Nil
unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
mult#2(0', x2) -> 0'
mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
plus#2(0', x8) -> x8
plus#2(S(x4), x2) -> S(plus#2(x4, x2))
main(0') -> 0'
main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

Types:
sum#1 :: Nil:Cons -> 0':S
Nil :: Nil:Cons
0' :: 0':S
Cons :: 0':S -> Nil:Cons -> Nil:Cons
plus#2 :: 0':S -> 0':S -> 0':S
map#2 :: Nil:Cons -> Nil:Cons
mult#2 :: 0':S -> 0':S -> 0':S
unfoldr#2 :: 0':S -> Nil:Cons
S :: 0':S -> 0':S
main :: 0':S -> 0':S
hole_0':S1_0 :: 0':S
hole_Nil:Cons2_0 :: Nil:Cons
gen_0':S3_0 :: Nat -> 0':S
gen_Nil:Cons4_0 :: Nat -> Nil:Cons

----------------------------------------

(5) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
sum#1, plus#2, map#2, mult#2, unfoldr#2

They will be analysed ascendingly in the following order:
plus#2 < sum#1
plus#2 < mult#2
mult#2 < map#2

----------------------------------------

(6)
Obligation:
Innermost TRS:
Rules:
sum#1(Nil) -> 0'
sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
map#2(Nil) -> Nil
map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
unfoldr#2(0') -> Nil
unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
mult#2(0', x2) -> 0'
mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
plus#2(0', x8) -> x8
plus#2(S(x4), x2) -> S(plus#2(x4, x2))
main(0') -> 0'
main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

Types:
sum#1 :: Nil:Cons -> 0':S
Nil :: Nil:Cons
0' :: 0':S
Cons :: 0':S -> Nil:Cons -> Nil:Cons
plus#2 :: 0':S -> 0':S -> 0':S
map#2 :: Nil:Cons -> Nil:Cons
mult#2 :: 0':S -> 0':S -> 0':S
unfoldr#2 :: 0':S -> Nil:Cons
S :: 0':S -> 0':S
main :: 0':S -> 0':S
hole_0':S1_0 :: 0':S
hole_Nil:Cons2_0 :: Nil:Cons
gen_0':S3_0 :: Nat -> 0':S
gen_Nil:Cons4_0 :: Nat -> Nil:Cons


Generator Equations:
gen_0':S3_0(0) <=> 0'
gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
gen_Nil:Cons4_0(0) <=> Nil
gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))


The following defined symbols remain to be analysed:
plus#2, sum#1, map#2, mult#2, unfoldr#2

They will be analysed ascendingly in the following order:
plus#2 < sum#1
plus#2 < mult#2
mult#2 < map#2

----------------------------------------

(7) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)

Induction Base:
plus#2(gen_0':S3_0(0), gen_0':S3_0(b)) ->_R^Omega(1)
gen_0':S3_0(b)

Induction Step:
plus#2(gen_0':S3_0(+(n6_0, 1)), gen_0':S3_0(b)) ->_R^Omega(1)
S(plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b))) ->_IH
S(gen_0':S3_0(+(b, c7_0)))

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(8)
Complex Obligation (BEST)

----------------------------------------

(9)
Obligation:
Proved the lower bound n^1 for the following obligation:

Innermost TRS:
Rules:
sum#1(Nil) -> 0'
sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
map#2(Nil) -> Nil
map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
unfoldr#2(0') -> Nil
unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
mult#2(0', x2) -> 0'
mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
plus#2(0', x8) -> x8
plus#2(S(x4), x2) -> S(plus#2(x4, x2))
main(0') -> 0'
main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

Types:
sum#1 :: Nil:Cons -> 0':S
Nil :: Nil:Cons
0' :: 0':S
Cons :: 0':S -> Nil:Cons -> Nil:Cons
plus#2 :: 0':S -> 0':S -> 0':S
map#2 :: Nil:Cons -> Nil:Cons
mult#2 :: 0':S -> 0':S -> 0':S
unfoldr#2 :: 0':S -> Nil:Cons
S :: 0':S -> 0':S
main :: 0':S -> 0':S
hole_0':S1_0 :: 0':S
hole_Nil:Cons2_0 :: Nil:Cons
gen_0':S3_0 :: Nat -> 0':S
gen_Nil:Cons4_0 :: Nat -> Nil:Cons


Generator Equations:
gen_0':S3_0(0) <=> 0'
gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
gen_Nil:Cons4_0(0) <=> Nil
gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))


The following defined symbols remain to be analysed:
plus#2, sum#1, map#2, mult#2, unfoldr#2

They will be analysed ascendingly in the following order:
plus#2 < sum#1
plus#2 < mult#2
mult#2 < map#2

----------------------------------------

(10) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(11)
BOUNDS(n^1, INF)

----------------------------------------

(12)
Obligation:
Innermost TRS:
Rules:
sum#1(Nil) -> 0'
sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
map#2(Nil) -> Nil
map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
unfoldr#2(0') -> Nil
unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
mult#2(0', x2) -> 0'
mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
plus#2(0', x8) -> x8
plus#2(S(x4), x2) -> S(plus#2(x4, x2))
main(0') -> 0'
main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

Types:
sum#1 :: Nil:Cons -> 0':S
Nil :: Nil:Cons
0' :: 0':S
Cons :: 0':S -> Nil:Cons -> Nil:Cons
plus#2 :: 0':S -> 0':S -> 0':S
map#2 :: Nil:Cons -> Nil:Cons
mult#2 :: 0':S -> 0':S -> 0':S
unfoldr#2 :: 0':S -> Nil:Cons
S :: 0':S -> 0':S
main :: 0':S -> 0':S
hole_0':S1_0 :: 0':S
hole_Nil:Cons2_0 :: Nil:Cons
gen_0':S3_0 :: Nat -> 0':S
gen_Nil:Cons4_0 :: Nat -> Nil:Cons


Lemmas:
plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)


Generator Equations:
gen_0':S3_0(0) <=> 0'
gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
gen_Nil:Cons4_0(0) <=> Nil
gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))


The following defined symbols remain to be analysed:
sum#1, map#2, mult#2, unfoldr#2

They will be analysed ascendingly in the following order:
mult#2 < map#2

----------------------------------------

(13) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)

Induction Base:
sum#1(gen_Nil:Cons4_0(0)) ->_R^Omega(1)
0'

Induction Step:
sum#1(gen_Nil:Cons4_0(+(n715_0, 1))) ->_R^Omega(1)
plus#2(0', sum#1(gen_Nil:Cons4_0(n715_0))) ->_IH
plus#2(0', gen_0':S3_0(0)) ->_L^Omega(1)
gen_0':S3_0(+(0, 0))

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(14)
Obligation:
Innermost TRS:
Rules:
sum#1(Nil) -> 0'
sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
map#2(Nil) -> Nil
map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
unfoldr#2(0') -> Nil
unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
mult#2(0', x2) -> 0'
mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
plus#2(0', x8) -> x8
plus#2(S(x4), x2) -> S(plus#2(x4, x2))
main(0') -> 0'
main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

Types:
sum#1 :: Nil:Cons -> 0':S
Nil :: Nil:Cons
0' :: 0':S
Cons :: 0':S -> Nil:Cons -> Nil:Cons
plus#2 :: 0':S -> 0':S -> 0':S
map#2 :: Nil:Cons -> Nil:Cons
mult#2 :: 0':S -> 0':S -> 0':S
unfoldr#2 :: 0':S -> Nil:Cons
S :: 0':S -> 0':S
main :: 0':S -> 0':S
hole_0':S1_0 :: 0':S
hole_Nil:Cons2_0 :: Nil:Cons
gen_0':S3_0 :: Nat -> 0':S
gen_Nil:Cons4_0 :: Nat -> Nil:Cons


Lemmas:
plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)


Generator Equations:
gen_0':S3_0(0) <=> 0'
gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
gen_Nil:Cons4_0(0) <=> Nil
gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))


The following defined symbols remain to be analysed:
mult#2, map#2, unfoldr#2

They will be analysed ascendingly in the following order:
mult#2 < map#2

----------------------------------------

(15) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
mult#2(gen_0':S3_0(n1039_0), gen_0':S3_0(b)) -> gen_0':S3_0(*(n1039_0, b)), rt in Omega(1 + b*n1039_0 + n1039_0)

Induction Base:
mult#2(gen_0':S3_0(0), gen_0':S3_0(b)) ->_R^Omega(1)
0'

Induction Step:
mult#2(gen_0':S3_0(+(n1039_0, 1)), gen_0':S3_0(b)) ->_R^Omega(1)
plus#2(gen_0':S3_0(b), mult#2(gen_0':S3_0(n1039_0), gen_0':S3_0(b))) ->_IH
plus#2(gen_0':S3_0(b), gen_0':S3_0(*(c1040_0, b))) ->_L^Omega(1 + b)
gen_0':S3_0(+(b, *(n1039_0, b)))

We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
----------------------------------------

(16)
Complex Obligation (BEST)

----------------------------------------

(17)
Obligation:
Proved the lower bound n^2 for the following obligation:

Innermost TRS:
Rules:
sum#1(Nil) -> 0'
sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
map#2(Nil) -> Nil
map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
unfoldr#2(0') -> Nil
unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
mult#2(0', x2) -> 0'
mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
plus#2(0', x8) -> x8
plus#2(S(x4), x2) -> S(plus#2(x4, x2))
main(0') -> 0'
main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

Types:
sum#1 :: Nil:Cons -> 0':S
Nil :: Nil:Cons
0' :: 0':S
Cons :: 0':S -> Nil:Cons -> Nil:Cons
plus#2 :: 0':S -> 0':S -> 0':S
map#2 :: Nil:Cons -> Nil:Cons
mult#2 :: 0':S -> 0':S -> 0':S
unfoldr#2 :: 0':S -> Nil:Cons
S :: 0':S -> 0':S
main :: 0':S -> 0':S
hole_0':S1_0 :: 0':S
hole_Nil:Cons2_0 :: Nil:Cons
gen_0':S3_0 :: Nat -> 0':S
gen_Nil:Cons4_0 :: Nat -> Nil:Cons


Lemmas:
plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)


Generator Equations:
gen_0':S3_0(0) <=> 0'
gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
gen_Nil:Cons4_0(0) <=> Nil
gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))


The following defined symbols remain to be analysed:
mult#2, map#2, unfoldr#2

They will be analysed ascendingly in the following order:
mult#2 < map#2

----------------------------------------

(18) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(19)
BOUNDS(n^2, INF)

----------------------------------------

(20)
Obligation:
Innermost TRS:
Rules:
sum#1(Nil) -> 0'
sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
map#2(Nil) -> Nil
map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
unfoldr#2(0') -> Nil
unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
mult#2(0', x2) -> 0'
mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
plus#2(0', x8) -> x8
plus#2(S(x4), x2) -> S(plus#2(x4, x2))
main(0') -> 0'
main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

Types:
sum#1 :: Nil:Cons -> 0':S
Nil :: Nil:Cons
0' :: 0':S
Cons :: 0':S -> Nil:Cons -> Nil:Cons
plus#2 :: 0':S -> 0':S -> 0':S
map#2 :: Nil:Cons -> Nil:Cons
mult#2 :: 0':S -> 0':S -> 0':S
unfoldr#2 :: 0':S -> Nil:Cons
S :: 0':S -> 0':S
main :: 0':S -> 0':S
hole_0':S1_0 :: 0':S
hole_Nil:Cons2_0 :: Nil:Cons
gen_0':S3_0 :: Nat -> 0':S
gen_Nil:Cons4_0 :: Nat -> Nil:Cons


Lemmas:
plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)
mult#2(gen_0':S3_0(n1039_0), gen_0':S3_0(b)) -> gen_0':S3_0(*(n1039_0, b)), rt in Omega(1 + b*n1039_0 + n1039_0)


Generator Equations:
gen_0':S3_0(0) <=> 0'
gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
gen_Nil:Cons4_0(0) <=> Nil
gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))


The following defined symbols remain to be analysed:
map#2, unfoldr#2
----------------------------------------

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
map#2(gen_Nil:Cons4_0(n1983_0)) -> gen_Nil:Cons4_0(n1983_0), rt in Omega(1 + n1983_0)

Induction Base:
map#2(gen_Nil:Cons4_0(0)) ->_R^Omega(1)
Nil

Induction Step:
map#2(gen_Nil:Cons4_0(+(n1983_0, 1))) ->_R^Omega(1)
Cons(mult#2(0', 0'), map#2(gen_Nil:Cons4_0(n1983_0))) ->_L^Omega(1)
Cons(gen_0':S3_0(*(0, 0)), map#2(gen_Nil:Cons4_0(n1983_0))) ->_IH
Cons(gen_0':S3_0(0), gen_Nil:Cons4_0(c1984_0))

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(22)
Obligation:
Innermost TRS:
Rules:
sum#1(Nil) -> 0'
sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
map#2(Nil) -> Nil
map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
unfoldr#2(0') -> Nil
unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
mult#2(0', x2) -> 0'
mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
plus#2(0', x8) -> x8
plus#2(S(x4), x2) -> S(plus#2(x4, x2))
main(0') -> 0'
main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))

Types:
sum#1 :: Nil:Cons -> 0':S
Nil :: Nil:Cons
0' :: 0':S
Cons :: 0':S -> Nil:Cons -> Nil:Cons
plus#2 :: 0':S -> 0':S -> 0':S
map#2 :: Nil:Cons -> Nil:Cons
mult#2 :: 0':S -> 0':S -> 0':S
unfoldr#2 :: 0':S -> Nil:Cons
S :: 0':S -> 0':S
main :: 0':S -> 0':S
hole_0':S1_0 :: 0':S
hole_Nil:Cons2_0 :: Nil:Cons
gen_0':S3_0 :: Nat -> 0':S
gen_Nil:Cons4_0 :: Nat -> Nil:Cons


Lemmas:
plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)
mult#2(gen_0':S3_0(n1039_0), gen_0':S3_0(b)) -> gen_0':S3_0(*(n1039_0, b)), rt in Omega(1 + b*n1039_0 + n1039_0)
map#2(gen_Nil:Cons4_0(n1983_0)) -> gen_Nil:Cons4_0(n1983_0), rt in Omega(1 + n1983_0)


Generator Equations:
gen_0':S3_0(0) <=> 0'
gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
gen_Nil:Cons4_0(0) <=> Nil
gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))


The following defined symbols remain to be analysed:
unfoldr#2
----------------------------------------

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
unfoldr#2(gen_0':S3_0(+(1, n2324_0))) -> *5_0, rt in Omega(n2324_0)

Induction Base:
unfoldr#2(gen_0':S3_0(+(1, 0)))

Induction Step:
unfoldr#2(gen_0':S3_0(+(1, +(n2324_0, 1)))) ->_R^Omega(1)
Cons(gen_0':S3_0(+(1, n2324_0)), unfoldr#2(gen_0':S3_0(+(1, n2324_0)))) ->_IH
Cons(gen_0':S3_0(+(1, n2324_0)), *5_0)

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(24)
BOUNDS(1, INF)