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


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


WORST_CASE(Omega(n^2), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) CpxTRS
(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxWeightedTrs
    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CpxTypedWeightedTrs
    (5) CompletionProof [UPPER BOUND(ID), 1 ms]
    (6) CpxTypedWeightedCompleteTrs
    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (8) CpxRNTS
    (9) CompleteCoflocoProof [FINISHED, 240 ms]
    (10) BOUNDS(1, n^2)
(11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(12) CpxTRS
    (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) typed CpxTrs
    (15) OrderProof [LOWER BOUND(ID), 0 ms]
    (16) typed CpxTrs
    (17) RewriteLemmaProof [LOWER BOUND(ID), 329 ms]
    (18) BEST
        (19) proven lower bound
            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
            (21) BOUNDS(n^1, INF)
        (22) typed CpxTrs
            (23) RewriteLemmaProof [LOWER BOUND(ID), 29 ms]
            (24) proven lower bound
            (25) LowerBoundPropagationProof [FINISHED, 0 ms]
            (26) BOUNDS(n^2, INF)


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

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


The TRS R consists of the following rules:

   rev(nil) -> nil
   rev(.(x, y)) -> ++(rev(y), .(x, nil))
   car(.(x, y)) -> x
   cdr(.(x, y)) -> y
   null(nil) -> true
   null(.(x, y)) -> false
   ++(nil, y) -> y
   ++(.(x, y), z) -> .(x, ++(y, z))

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

(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
Transformed relative TRS to weighted TRS
----------------------------------------

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


The TRS R consists of the following rules:

   rev(nil) -> nil [1]
   rev(.(x, y)) -> ++(rev(y), .(x, nil)) [1]
   car(.(x, y)) -> x [1]
   cdr(.(x, y)) -> y [1]
   null(nil) -> true [1]
   null(.(x, y)) -> false [1]
   ++(nil, y) -> y [1]
   ++(.(x, y), z) -> .(x, ++(y, z)) [1]

Rewrite Strategy: INNERMOST
----------------------------------------

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

(4)
Obligation:
Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   rev(nil) -> nil [1]
   rev(.(x, y)) -> ++(rev(y), .(x, nil)) [1]
   car(.(x, y)) -> x [1]
   cdr(.(x, y)) -> y [1]
   null(nil) -> true [1]
   null(.(x, y)) -> false [1]
   ++(nil, y) -> y [1]
   ++(.(x, y), z) -> .(x, ++(y, z)) [1]

The TRS has the following type information:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false

Rewrite Strategy: INNERMOST
----------------------------------------

(5) CompletionProof (UPPER BOUND(ID))
The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:

   car(v0) -> null_car [0]
   cdr(v0) -> null_cdr [0]
   rev(v0) -> null_rev [0]
   null(v0) -> null_null [0]
   ++(v0, v1) -> null_++ [0]

And the following fresh constants:    null_car, null_cdr, null_rev, null_null, null_++

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

(6)
Obligation:
Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   rev(nil) -> nil [1]
   rev(.(x, y)) -> ++(rev(y), .(x, nil)) [1]
   car(.(x, y)) -> x [1]
   cdr(.(x, y)) -> y [1]
   null(nil) -> true [1]
   null(.(x, y)) -> false [1]
   ++(nil, y) -> y [1]
   ++(.(x, y), z) -> .(x, ++(y, z)) [1]
   car(v0) -> null_car [0]
   cdr(v0) -> null_cdr [0]
   rev(v0) -> null_rev [0]
   null(v0) -> null_null [0]
   ++(v0, v1) -> null_++ [0]

The TRS has the following type information:
rev :: nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++
nil :: nil:.:null_cdr:null_rev:null_++
. :: null_car -> nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++
++ :: nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++
car :: nil:.:null_cdr:null_rev:null_++ -> null_car
cdr :: nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++
null :: nil:.:null_cdr:null_rev:null_++ -> true:false:null_null
true :: true:false:null_null
false :: true:false:null_null
null_car :: null_car
null_cdr :: nil:.:null_cdr:null_rev:null_++
null_rev :: nil:.:null_cdr:null_rev:null_++
null_null :: true:false:null_null
null_++ :: nil:.:null_cdr:null_rev:null_++

Rewrite Strategy: INNERMOST
----------------------------------------

(7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
The constant constructors are abstracted as follows:

   nil => 0
   true => 2
   false => 1
   null_car => 0
   null_cdr => 0
   null_rev => 0
   null_null => 0
   null_++ => 0

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

(8)
Obligation:
Complexity RNTS consisting of the following rules:

   ++(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 0
   ++(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   ++(z', z'') -{ 1 }-> 1 + x + ++(y, z) :|: z'' = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0
   car(z') -{ 1 }-> x :|: z' = 1 + x + y, x >= 0, y >= 0
   car(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   cdr(z') -{ 1 }-> y :|: z' = 1 + x + y, x >= 0, y >= 0
   cdr(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   null(z') -{ 1 }-> 2 :|: z' = 0
   null(z') -{ 1 }-> 1 :|: z' = 1 + x + y, x >= 0, y >= 0
   null(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   rev(z') -{ 1 }-> 0 :|: z' = 0
   rev(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   rev(z') -{ 1 }-> ++(rev(y), 1 + x + 0) :|: z' = 1 + x + y, x >= 0, y >= 0

Only complete derivations are relevant for the runtime complexity.

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

(9) CompleteCoflocoProof (FINISHED)
Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:

eq(start(V, V10),0,[rev(V, Out)],[V >= 0]).
eq(start(V, V10),0,[car(V, Out)],[V >= 0]).
eq(start(V, V10),0,[cdr(V, Out)],[V >= 0]).
eq(start(V, V10),0,[null(V, Out)],[V >= 0]).
eq(start(V, V10),0,[fun(V, V10, Out)],[V >= 0,V10 >= 0]).
eq(rev(V, Out),1,[],[Out = 0,V = 0]).
eq(rev(V, Out),1,[rev(V1, Ret0),fun(Ret0, 1 + V2 + 0, Ret)],[Out = Ret,V = 1 + V1 + V2,V2 >= 0,V1 >= 0]).
eq(car(V, Out),1,[],[Out = V3,V = 1 + V3 + V4,V3 >= 0,V4 >= 0]).
eq(cdr(V, Out),1,[],[Out = V5,V = 1 + V5 + V6,V6 >= 0,V5 >= 0]).
eq(null(V, Out),1,[],[Out = 2,V = 0]).
eq(null(V, Out),1,[],[Out = 1,V = 1 + V7 + V8,V7 >= 0,V8 >= 0]).
eq(fun(V, V10, Out),1,[],[Out = V9,V10 = V9,V9 >= 0,V = 0]).
eq(fun(V, V10, Out),1,[fun(V12, V13, Ret1)],[Out = 1 + Ret1 + V11,V10 = V13,V13 >= 0,V = 1 + V11 + V12,V11 >= 0,V12 >= 0]).
eq(car(V, Out),0,[],[Out = 0,V14 >= 0,V = V14]).
eq(cdr(V, Out),0,[],[Out = 0,V15 >= 0,V = V15]).
eq(rev(V, Out),0,[],[Out = 0,V16 >= 0,V = V16]).
eq(null(V, Out),0,[],[Out = 0,V17 >= 0,V = V17]).
eq(fun(V, V10, Out),0,[],[Out = 0,V18 >= 0,V19 >= 0,V10 = V19,V = V18]).
input_output_vars(rev(V,Out),[V],[Out]).
input_output_vars(car(V,Out),[V],[Out]).
input_output_vars(cdr(V,Out),[V],[Out]).
input_output_vars(null(V,Out),[V],[Out]).
input_output_vars(fun(V,V10,Out),[V,V10],[Out]).


CoFloCo proof output:
Preprocessing Cost Relations
=====================================

#### Computed strongly connected components 
0. non_recursive  : [car/2]
1. non_recursive  : [cdr/2]
2. recursive  : [fun/3]
3. non_recursive  : [null/2]
4. recursive [non_tail] : [rev/2]
5. non_recursive  : [start/2]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into car/2
1. SCC is partially evaluated into cdr/2
2. SCC is partially evaluated into fun/3
3. SCC is partially evaluated into null/2
4. SCC is partially evaluated into rev/2
5. SCC is partially evaluated into start/2

Control-Flow Refinement of Cost Relations
=====================================

### Specialization of cost equations car/2 
* CE 9 is refined into CE [19] 
* CE 10 is refined into CE [20] 


### Cost equations --> "Loop" of car/2 
* CEs [19] --> Loop 14 
* CEs [20] --> Loop 15 

### Ranking functions of CR car(V,Out) 

#### Partial ranking functions of CR car(V,Out) 


### Specialization of cost equations cdr/2 
* CE 11 is refined into CE [21] 
* CE 12 is refined into CE [22] 


### Cost equations --> "Loop" of cdr/2 
* CEs [21] --> Loop 16 
* CEs [22] --> Loop 17 

### Ranking functions of CR cdr(V,Out) 

#### Partial ranking functions of CR cdr(V,Out) 


### Specialization of cost equations fun/3 
* CE 18 is refined into CE [23] 
* CE 16 is refined into CE [24] 
* CE 17 is refined into CE [25] 


### Cost equations --> "Loop" of fun/3 
* CEs [25] --> Loop 18 
* CEs [23] --> Loop 19 
* CEs [24] --> Loop 20 

### Ranking functions of CR fun(V,V10,Out) 
* RF of phase [18]: [V]

#### Partial ranking functions of CR fun(V,V10,Out) 
* Partial RF of phase [18]:
  - RF of loop [18:1]:
    V


### Specialization of cost equations null/2 
* CE 14 is refined into CE [26] 
* CE 15 is refined into CE [27] 
* CE 13 is refined into CE [28] 


### Cost equations --> "Loop" of null/2 
* CEs [26] --> Loop 21 
* CEs [27] --> Loop 22 
* CEs [28] --> Loop 23 

### Ranking functions of CR null(V,Out) 

#### Partial ranking functions of CR null(V,Out) 


### Specialization of cost equations rev/2 
* CE 6 is refined into CE [29] 
* CE 8 is refined into CE [30] 
* CE 7 is refined into CE [31,32,33,34] 


### Cost equations --> "Loop" of rev/2 
* CEs [34] --> Loop 24 
* CEs [33] --> Loop 25 
* CEs [31] --> Loop 26 
* CEs [32] --> Loop 27 
* CEs [29,30] --> Loop 28 

### Ranking functions of CR rev(V,Out) 
* RF of phase [24,25,26,27]: [V]

#### Partial ranking functions of CR rev(V,Out) 
* Partial RF of phase [24,25,26,27]:
  - RF of loop [24:1,25:1,26:1,27:1]:
    V


### Specialization of cost equations start/2 
* CE 1 is refined into CE [35,36] 
* CE 2 is refined into CE [37,38] 
* CE 3 is refined into CE [39,40] 
* CE 4 is refined into CE [41,42,43] 
* CE 5 is refined into CE [44,45,46,47] 


### Cost equations --> "Loop" of start/2 
* CEs [35,36,37,38,39,40,41,42,43,44,45,46,47] --> Loop 29 

### Ranking functions of CR start(V,V10) 

#### Partial ranking functions of CR start(V,V10) 


Computing Bounds
=====================================

#### Cost of chains of car(V,Out):
* Chain [15]: 0
  with precondition: [Out=0,V>=0] 

* Chain [14]: 1
  with precondition: [Out>=0,V>=Out+1] 


#### Cost of chains of cdr(V,Out):
* Chain [17]: 0
  with precondition: [Out=0,V>=0] 

* Chain [16]: 1
  with precondition: [Out>=0,V>=Out+1] 


#### Cost of chains of fun(V,V10,Out):
* Chain [[18],20]: 1*it(18)+1
  Such that:it(18) =< -V10+Out

  with precondition: [V+V10=Out,V>=1,V10>=0] 

* Chain [[18],19]: 1*it(18)+0
  Such that:it(18) =< Out

  with precondition: [V10>=0,Out>=1,V>=Out] 

* Chain [20]: 1
  with precondition: [V=0,V10=Out,V10>=0] 

* Chain [19]: 0
  with precondition: [Out=0,V>=0,V10>=0] 


#### Cost of chains of null(V,Out):
* Chain [23]: 1
  with precondition: [V=0,Out=2] 

* Chain [22]: 0
  with precondition: [Out=0,V>=0] 

* Chain [21]: 1
  with precondition: [Out=1,V>=1] 


#### Cost of chains of rev(V,Out):
* Chain [[24,25,26,27],28]: 6*it(24)+1*s(5)+1*s(6)+1
  Such that:aux(5) =< V
it(24) =< aux(5)
aux(2) =< aux(5)
s(5) =< it(24)*aux(5)
s(6) =< it(24)*aux(2)

  with precondition: [V>=1,Out>=0,V>=Out] 

* Chain [28]: 1
  with precondition: [Out=0,V>=0] 


#### Cost of chains of start(V,V10):
* Chain [29]: 8*s(8)+1*s(10)+1*s(11)+1
  Such that:aux(6) =< V
s(8) =< aux(6)
s(9) =< aux(6)
s(10) =< s(8)*aux(6)
s(11) =< s(8)*s(9)

  with precondition: [V>=0] 


Closed-form bounds of start(V,V10): 
-------------------------------------
* Chain [29] with precondition: [V>=0] 
    - Upper bound: 8*V+1+2*V*V 
    - Complexity: n^2 

### Maximum cost of start(V,V10): 8*V+1+2*V*V 
Asymptotic class: n^2 
* Total analysis performed in 162 ms.


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

(10)
BOUNDS(1, n^2)

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

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

(12)
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:

   rev(nil) -> nil
   rev(.(x, y)) -> ++(rev(y), .(x, nil))
   car(.(x, y)) -> x
   cdr(.(x, y)) -> y
   null(nil) -> true
   null(.(x, y)) -> false
   ++(nil, y) -> y
   ++(.(x, y), z) -> .(x, ++(y, z))

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

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

(14)
Obligation:
Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.

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

(15) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
rev, ++

They will be analysed ascendingly in the following order:
++ < rev

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

(16)
Obligation:
Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.


Generator Equations:
gen_nil:.4_0(0) <=> nil
gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))


The following defined symbols remain to be analysed:
++, rev

They will be analysed ascendingly in the following order:
++ < rev

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0)

Induction Base:
++(gen_nil:.4_0(0), gen_nil:.4_0(b)) ->_R^Omega(1)
gen_nil:.4_0(b)

Induction Step:
++(gen_nil:.4_0(+(n6_0, 1)), gen_nil:.4_0(b)) ->_R^Omega(1)
.(hole_car2_0, ++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b))) ->_IH
.(hole_car2_0, gen_nil:.4_0(+(b, c7_0)))

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

(18)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.


Generator Equations:
gen_nil:.4_0(0) <=> nil
gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))


The following defined symbols remain to be analysed:
++, rev

They will be analysed ascendingly in the following order:
++ < rev

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

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

(21)
BOUNDS(n^1, INF)

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

(22)
Obligation:
Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.


Lemmas:
++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0)


Generator Equations:
gen_nil:.4_0(0) <=> nil
gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))


The following defined symbols remain to be analysed:
rev
----------------------------------------

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
rev(gen_nil:.4_0(n535_0)) -> gen_nil:.4_0(n535_0), rt in Omega(1 + n535_0 + n535_0^2)

Induction Base:
rev(gen_nil:.4_0(0)) ->_R^Omega(1)
nil

Induction Step:
rev(gen_nil:.4_0(+(n535_0, 1))) ->_R^Omega(1)
++(rev(gen_nil:.4_0(n535_0)), .(hole_car2_0, nil)) ->_IH
++(gen_nil:.4_0(c536_0), .(hole_car2_0, nil)) ->_L^Omega(1 + n535_0)
gen_nil:.4_0(+(n535_0, +(0, 1)))

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

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

Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.


Lemmas:
++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0)


Generator Equations:
gen_nil:.4_0(0) <=> nil
gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))


The following defined symbols remain to be analysed:
rev
----------------------------------------

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

(26)
BOUNDS(n^2, INF)