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


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


WORST_CASE(Omega(n^1), O(n^1))
proof of /export/starexec/sandbox2/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^1, n^1).

(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), 0 ms]
    (6) CpxTypedWeightedCompleteTrs
    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 3 ms]
    (8) CpxRNTS
    (9) CompleteCoflocoProof [FINISHED, 360 ms]
    (10) BOUNDS(1, n^1)
(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), 261 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), 78 ms]
            (24) typed CpxTrs
            (25) RewriteLemmaProof [LOWER BOUND(ID), 61 ms]
            (26) typed CpxTrs
            (27) RewriteLemmaProof [LOWER BOUND(ID), 3 ms]
            (28) typed CpxTrs


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

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


The TRS R consists of the following rules:

   append(@l1, @l2) -> append#1(@l1, @l2)
   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
   append#1(nil, @l2) -> @l2
   appendAll(@l) -> appendAll#1(@l)
   appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
   appendAll#1(nil) -> nil
   appendAll2(@l) -> appendAll2#1(@l)
   appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
   appendAll2#1(nil) -> nil
   appendAll3(@l) -> appendAll3#1(@l)
   appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
   appendAll3#1(nil) -> nil

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^1).


The TRS R consists of the following rules:

   append(@l1, @l2) -> append#1(@l1, @l2) [1]
   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2)) [1]
   append#1(nil, @l2) -> @l2 [1]
   appendAll(@l) -> appendAll#1(@l) [1]
   appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls)) [1]
   appendAll#1(nil) -> nil [1]
   appendAll2(@l) -> appendAll2#1(@l) [1]
   appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls)) [1]
   appendAll2#1(nil) -> nil [1]
   appendAll3(@l) -> appendAll3#1(@l) [1]
   appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls)) [1]
   appendAll3#1(nil) -> nil [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:

   append(@l1, @l2) -> append#1(@l1, @l2) [1]
   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2)) [1]
   append#1(nil, @l2) -> @l2 [1]
   appendAll(@l) -> appendAll#1(@l) [1]
   appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls)) [1]
   appendAll#1(nil) -> nil [1]
   appendAll2(@l) -> appendAll2#1(@l) [1]
   appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls)) [1]
   appendAll2#1(nil) -> nil [1]
   appendAll3(@l) -> appendAll3#1(@l) [1]
   appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls)) [1]
   appendAll3#1(nil) -> nil [1]

The TRS has the following type information:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil -> :::nil
nil :: :::nil
appendAll :: :::nil -> :::nil
appendAll#1 :: :::nil -> :::nil
appendAll2 :: :::nil -> :::nil
appendAll2#1 :: :::nil -> :::nil
appendAll3 :: :::nil -> :::nil
appendAll3#1 :: :::nil -> :::nil

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:
none

And the following fresh constants: none

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

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

   append(@l1, @l2) -> append#1(@l1, @l2) [1]
   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2)) [1]
   append#1(nil, @l2) -> @l2 [1]
   appendAll(@l) -> appendAll#1(@l) [1]
   appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls)) [1]
   appendAll#1(nil) -> nil [1]
   appendAll2(@l) -> appendAll2#1(@l) [1]
   appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls)) [1]
   appendAll2#1(nil) -> nil [1]
   appendAll3(@l) -> appendAll3#1(@l) [1]
   appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls)) [1]
   appendAll3#1(nil) -> nil [1]

The TRS has the following type information:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil -> :::nil
nil :: :::nil
appendAll :: :::nil -> :::nil
appendAll#1 :: :::nil -> :::nil
appendAll2 :: :::nil -> :::nil
appendAll2#1 :: :::nil -> :::nil
appendAll3 :: :::nil -> :::nil
appendAll3#1 :: :::nil -> :::nil

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

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

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

   append(z, z') -{ 1 }-> append#1(@l1, @l2) :|: @l1 >= 0, z' = @l2, @l2 >= 0, z = @l1
   append#1(z, z') -{ 1 }-> @l2 :|: z' = @l2, @l2 >= 0, z = 0
   append#1(z, z') -{ 1 }-> 1 + @x + append(@xs, @l2) :|: z' = @l2, @x >= 0, z = 1 + @x + @xs, @l2 >= 0, @xs >= 0
   appendAll(z) -{ 1 }-> appendAll#1(@l) :|: z = @l, @l >= 0
   appendAll#1(z) -{ 1 }-> append(@l1, appendAll(@ls)) :|: @ls >= 0, @l1 >= 0, z = 1 + @l1 + @ls
   appendAll#1(z) -{ 1 }-> 0 :|: z = 0
   appendAll2(z) -{ 1 }-> appendAll2#1(@l) :|: z = @l, @l >= 0
   appendAll2#1(z) -{ 1 }-> append(appendAll(@l1), appendAll2(@ls)) :|: @ls >= 0, @l1 >= 0, z = 1 + @l1 + @ls
   appendAll2#1(z) -{ 1 }-> 0 :|: z = 0
   appendAll3(z) -{ 1 }-> appendAll3#1(@l) :|: z = @l, @l >= 0
   appendAll3#1(z) -{ 1 }-> append(appendAll2(@l1), appendAll3(@ls)) :|: @ls >= 0, @l1 >= 0, z = 1 + @l1 + @ls
   appendAll3#1(z) -{ 1 }-> 0 :|: z = 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(V2, V1),0,[append(V2, V1, Out)],[V2 >= 0,V1 >= 0]).
eq(start(V2, V1),0,[fun(V2, V1, Out)],[V2 >= 0,V1 >= 0]).
eq(start(V2, V1),0,[appendAll(V2, Out)],[V2 >= 0]).
eq(start(V2, V1),0,[fun1(V2, Out)],[V2 >= 0]).
eq(start(V2, V1),0,[appendAll2(V2, Out)],[V2 >= 0]).
eq(start(V2, V1),0,[fun2(V2, Out)],[V2 >= 0]).
eq(start(V2, V1),0,[appendAll3(V2, Out)],[V2 >= 0]).
eq(start(V2, V1),0,[fun3(V2, Out)],[V2 >= 0]).
eq(append(V2, V1, Out),1,[fun(V3, V, Ret)],[Out = Ret,V3 >= 0,V1 = V,V >= 0,V2 = V3]).
eq(fun(V2, V1, Out),1,[append(V6, V4, Ret1)],[Out = 1 + Ret1 + V5,V1 = V4,V5 >= 0,V2 = 1 + V5 + V6,V4 >= 0,V6 >= 0]).
eq(fun(V2, V1, Out),1,[],[Out = V7,V1 = V7,V7 >= 0,V2 = 0]).
eq(appendAll(V2, Out),1,[fun1(V8, Ret2)],[Out = Ret2,V2 = V8,V8 >= 0]).
eq(fun1(V2, Out),1,[appendAll(V9, Ret11),append(V10, Ret11, Ret3)],[Out = Ret3,V9 >= 0,V10 >= 0,V2 = 1 + V10 + V9]).
eq(fun1(V2, Out),1,[],[Out = 0,V2 = 0]).
eq(appendAll2(V2, Out),1,[fun2(V11, Ret4)],[Out = Ret4,V2 = V11,V11 >= 0]).
eq(fun2(V2, Out),1,[appendAll(V13, Ret0),appendAll2(V12, Ret12),append(Ret0, Ret12, Ret5)],[Out = Ret5,V12 >= 0,V13 >= 0,V2 = 1 + V12 + V13]).
eq(fun2(V2, Out),1,[],[Out = 0,V2 = 0]).
eq(appendAll3(V2, Out),1,[fun3(V14, Ret6)],[Out = Ret6,V2 = V14,V14 >= 0]).
eq(fun3(V2, Out),1,[appendAll2(V16, Ret01),appendAll3(V15, Ret13),append(Ret01, Ret13, Ret7)],[Out = Ret7,V15 >= 0,V16 >= 0,V2 = 1 + V15 + V16]).
eq(fun3(V2, Out),1,[],[Out = 0,V2 = 0]).
input_output_vars(append(V2,V1,Out),[V2,V1],[Out]).
input_output_vars(fun(V2,V1,Out),[V2,V1],[Out]).
input_output_vars(appendAll(V2,Out),[V2],[Out]).
input_output_vars(fun1(V2,Out),[V2],[Out]).
input_output_vars(appendAll2(V2,Out),[V2],[Out]).
input_output_vars(fun2(V2,Out),[V2],[Out]).
input_output_vars(appendAll3(V2,Out),[V2],[Out]).
input_output_vars(fun3(V2,Out),[V2],[Out]).


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

#### Computed strongly connected components 
0. recursive  : [append/3,fun/3]
1. recursive [non_tail] : [appendAll/2,fun1/2]
2. recursive [non_tail] : [appendAll2/2,fun2/2]
3. recursive [non_tail] : [appendAll3/2,fun3/2]
4. non_recursive  : [start/2]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into append/3
1. SCC is partially evaluated into appendAll/2
2. SCC is partially evaluated into appendAll2/2
3. SCC is partially evaluated into fun3/2
4. SCC is partially evaluated into start/2

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

### Specialization of cost equations append/3 
* CE 17 is refined into CE [18] 
* CE 16 is refined into CE [19] 


### Cost equations --> "Loop" of append/3 
* CEs [19] --> Loop 10 
* CEs [18] --> Loop 11 

### Ranking functions of CR append(V2,V1,Out) 
* RF of phase [11]: [V2]

#### Partial ranking functions of CR append(V2,V1,Out) 
* Partial RF of phase [11]:
  - RF of loop [11:1]:
    V2


### Specialization of cost equations appendAll/2 
* CE 13 is refined into CE [20,21] 
* CE 12 is refined into CE [22] 


### Cost equations --> "Loop" of appendAll/2 
* CEs [22] --> Loop 12 
* CEs [21] --> Loop 13 
* CEs [20] --> Loop 14 

### Ranking functions of CR appendAll(V2,Out) 
* RF of phase [13,14]: [V2]

#### Partial ranking functions of CR appendAll(V2,Out) 
* Partial RF of phase [13,14]:
  - RF of loop [13:1]:
    V2-1
  - RF of loop [14:1]:
    V2


### Specialization of cost equations appendAll2/2 
* CE 15 is refined into CE [23,24,25] 
* CE 14 is refined into CE [26] 


### Cost equations --> "Loop" of appendAll2/2 
* CEs [26] --> Loop 15 
* CEs [25] --> Loop 16 
* CEs [24] --> Loop 17 
* CEs [23] --> Loop 18 

### Ranking functions of CR appendAll2(V2,Out) 
* RF of phase [16,17,18]: [V2]

#### Partial ranking functions of CR appendAll2(V2,Out) 
* Partial RF of phase [16,17,18]:
  - RF of loop [16:1]:
    V2-2
  - RF of loop [17:1]:
    V2-1
  - RF of loop [18:1]:
    V2


### Specialization of cost equations fun3/2 
* CE 11 is refined into CE [27] 
* CE 10 is refined into CE [28,29,30] 


### Cost equations --> "Loop" of fun3/2 
* CEs [30] --> Loop 19 
* CEs [29] --> Loop 20 
* CEs [28] --> Loop 21 
* CEs [27] --> Loop 22 

### Ranking functions of CR fun3(V2,Out) 
* RF of phase [19,20,21]: [V2]

#### Partial ranking functions of CR fun3(V2,Out) 
* Partial RF of phase [19,20,21]:
  - RF of loop [19:1]:
    V2-2
  - RF of loop [20:1]:
    V2-1
  - RF of loop [21:1]:
    V2


### Specialization of cost equations start/2 
* CE 1 is refined into CE [31,32] 
* CE 2 is refined into CE [33] 
* CE 3 is refined into CE [34,35,36,37,38,39] 
* CE 4 is refined into CE [40,41,42,43] 
* CE 5 is refined into CE [44,45] 
* CE 6 is refined into CE [46,47] 
* CE 7 is refined into CE [48,49] 
* CE 8 is refined into CE [50,51] 
* CE 9 is refined into CE [52,53] 


### Cost equations --> "Loop" of start/2 
* CEs [32,34,35,36,37,38,39,40,41,42,43,44,45,47,49,51,53] --> Loop 23 
* CEs [31,33,46,48,50,52] --> Loop 24 

### Ranking functions of CR start(V2,V1) 

#### Partial ranking functions of CR start(V2,V1) 


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

#### Cost of chains of append(V2,V1,Out):
* Chain [[11],10]: 2*it(11)+2
  Such that:it(11) =< -V1+Out

  with precondition: [V1+V2=Out,V2>=1,V1>=0] 

* Chain [10]: 2
  with precondition: [V2=0,V1=Out,V1>=0] 


#### Cost of chains of appendAll(V2,Out):
* Chain [[13,14],12]: 10*it(13)+2
  Such that:aux(3) =< V2
it(13) =< aux(3)

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

* Chain [12]: 2
  with precondition: [V2=0,Out=0] 


#### Cost of chains of appendAll2(V2,Out):
* Chain [[16,17,18],15]: 40*it(16)+2
  Such that:aux(7) =< V2
it(16) =< aux(7)

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

* Chain [15]: 2
  with precondition: [V2=0,Out=0] 


#### Cost of chains of fun3(V2,Out):
* Chain [[19,20,21],22]: 100*it(19)+1
  Such that:aux(11) =< V2
it(19) =< aux(11)

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

* Chain [22]: 1
  with precondition: [V2=0,Out=0] 


#### Cost of chains of start(V2,V1):
* Chain [24]: 2
  with precondition: [V2=0] 

* Chain [23]: 442*s(31)+7
  Such that:aux(16) =< V2
s(31) =< aux(16)

  with precondition: [V2>=1] 


Closed-form bounds of start(V2,V1): 
-------------------------------------
* Chain [24] with precondition: [V2=0] 
    - Upper bound: 2 
    - Complexity: constant 
* Chain [23] with precondition: [V2>=1] 
    - Upper bound: 442*V2+7 
    - Complexity: n 

### Maximum cost of start(V2,V1): 442*V2+7 
Asymptotic class: n 
* Total analysis performed in 270 ms.


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

(10)
BOUNDS(1, n^1)

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

(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^1, INF).


The TRS R consists of the following rules:

   append(@l1, @l2) -> append#1(@l1, @l2)
   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
   append#1(nil, @l2) -> @l2
   appendAll(@l) -> appendAll#1(@l)
   appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
   appendAll#1(nil) -> nil
   appendAll2(@l) -> appendAll2#1(@l)
   appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
   appendAll2#1(nil) -> nil
   appendAll3(@l) -> appendAll3#1(@l)
   appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
   appendAll3#1(nil) -> nil

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

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

(14)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
append#1(nil, @l2) -> @l2
appendAll(@l) -> appendAll#1(@l)
appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
appendAll#1(nil) -> nil
appendAll2(@l) -> appendAll2#1(@l)
appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
appendAll2#1(nil) -> nil
appendAll3(@l) -> appendAll3#1(@l)
appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
appendAll3#1(nil) -> nil

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil -> :::nil
nil :: :::nil
appendAll :: :::nil -> :::nil
appendAll#1 :: :::nil -> :::nil
appendAll2 :: :::nil -> :::nil
appendAll2#1 :: :::nil -> :::nil
appendAll3 :: :::nil -> :::nil
appendAll3#1 :: :::nil -> :::nil
hole_:::nil1_0 :: :::nil
gen_:::nil2_0 :: Nat -> :::nil

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

(15) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
append, append#1, appendAll, appendAll#1, appendAll2, appendAll2#1, appendAll3, appendAll3#1

They will be analysed ascendingly in the following order:
append = append#1
append < appendAll#1
append < appendAll2#1
append < appendAll3#1
appendAll = appendAll#1
appendAll < appendAll2#1
appendAll2 = appendAll2#1
appendAll2 < appendAll3#1
appendAll3 = appendAll3#1

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

(16)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
append#1(nil, @l2) -> @l2
appendAll(@l) -> appendAll#1(@l)
appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
appendAll#1(nil) -> nil
appendAll2(@l) -> appendAll2#1(@l)
appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
appendAll2#1(nil) -> nil
appendAll3(@l) -> appendAll3#1(@l)
appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
appendAll3#1(nil) -> nil

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil -> :::nil
nil :: :::nil
appendAll :: :::nil -> :::nil
appendAll#1 :: :::nil -> :::nil
appendAll2 :: :::nil -> :::nil
appendAll2#1 :: :::nil -> :::nil
appendAll3 :: :::nil -> :::nil
appendAll3#1 :: :::nil -> :::nil
hole_:::nil1_0 :: :::nil
gen_:::nil2_0 :: Nat -> :::nil


Generator Equations:
gen_:::nil2_0(0) <=> nil
gen_:::nil2_0(+(x, 1)) <=> ::(nil, gen_:::nil2_0(x))


The following defined symbols remain to be analysed:
append#1, append, appendAll, appendAll#1, appendAll2, appendAll2#1, appendAll3, appendAll3#1

They will be analysed ascendingly in the following order:
append = append#1
append < appendAll#1
append < appendAll2#1
append < appendAll3#1
appendAll = appendAll#1
appendAll < appendAll2#1
appendAll2 = appendAll2#1
appendAll2 < appendAll3#1
appendAll3 = appendAll3#1

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
append#1(gen_:::nil2_0(n4_0), gen_:::nil2_0(b)) -> gen_:::nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)

Induction Base:
append#1(gen_:::nil2_0(0), gen_:::nil2_0(b)) ->_R^Omega(1)
gen_:::nil2_0(b)

Induction Step:
append#1(gen_:::nil2_0(+(n4_0, 1)), gen_:::nil2_0(b)) ->_R^Omega(1)
::(nil, append(gen_:::nil2_0(n4_0), gen_:::nil2_0(b))) ->_R^Omega(1)
::(nil, append#1(gen_:::nil2_0(n4_0), gen_:::nil2_0(b))) ->_IH
::(nil, gen_:::nil2_0(+(b, c5_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:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
append#1(nil, @l2) -> @l2
appendAll(@l) -> appendAll#1(@l)
appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
appendAll#1(nil) -> nil
appendAll2(@l) -> appendAll2#1(@l)
appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
appendAll2#1(nil) -> nil
appendAll3(@l) -> appendAll3#1(@l)
appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
appendAll3#1(nil) -> nil

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil -> :::nil
nil :: :::nil
appendAll :: :::nil -> :::nil
appendAll#1 :: :::nil -> :::nil
appendAll2 :: :::nil -> :::nil
appendAll2#1 :: :::nil -> :::nil
appendAll3 :: :::nil -> :::nil
appendAll3#1 :: :::nil -> :::nil
hole_:::nil1_0 :: :::nil
gen_:::nil2_0 :: Nat -> :::nil


Generator Equations:
gen_:::nil2_0(0) <=> nil
gen_:::nil2_0(+(x, 1)) <=> ::(nil, gen_:::nil2_0(x))


The following defined symbols remain to be analysed:
append#1, append, appendAll, appendAll#1, appendAll2, appendAll2#1, appendAll3, appendAll3#1

They will be analysed ascendingly in the following order:
append = append#1
append < appendAll#1
append < appendAll2#1
append < appendAll3#1
appendAll = appendAll#1
appendAll < appendAll2#1
appendAll2 = appendAll2#1
appendAll2 < appendAll3#1
appendAll3 = appendAll3#1

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

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

(21)
BOUNDS(n^1, INF)

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

(22)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
append#1(nil, @l2) -> @l2
appendAll(@l) -> appendAll#1(@l)
appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
appendAll#1(nil) -> nil
appendAll2(@l) -> appendAll2#1(@l)
appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
appendAll2#1(nil) -> nil
appendAll3(@l) -> appendAll3#1(@l)
appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
appendAll3#1(nil) -> nil

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil -> :::nil
nil :: :::nil
appendAll :: :::nil -> :::nil
appendAll#1 :: :::nil -> :::nil
appendAll2 :: :::nil -> :::nil
appendAll2#1 :: :::nil -> :::nil
appendAll3 :: :::nil -> :::nil
appendAll3#1 :: :::nil -> :::nil
hole_:::nil1_0 :: :::nil
gen_:::nil2_0 :: Nat -> :::nil


Lemmas:
append#1(gen_:::nil2_0(n4_0), gen_:::nil2_0(b)) -> gen_:::nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)


Generator Equations:
gen_:::nil2_0(0) <=> nil
gen_:::nil2_0(+(x, 1)) <=> ::(nil, gen_:::nil2_0(x))


The following defined symbols remain to be analysed:
append, appendAll, appendAll#1, appendAll2, appendAll2#1, appendAll3, appendAll3#1

They will be analysed ascendingly in the following order:
append = append#1
append < appendAll#1
append < appendAll2#1
append < appendAll3#1
appendAll = appendAll#1
appendAll < appendAll2#1
appendAll2 = appendAll2#1
appendAll2 < appendAll3#1
appendAll3 = appendAll3#1

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

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
appendAll#1(gen_:::nil2_0(n633_0)) -> gen_:::nil2_0(0), rt in Omega(1 + n633_0)

Induction Base:
appendAll#1(gen_:::nil2_0(0)) ->_R^Omega(1)
nil

Induction Step:
appendAll#1(gen_:::nil2_0(+(n633_0, 1))) ->_R^Omega(1)
append(nil, appendAll(gen_:::nil2_0(n633_0))) ->_R^Omega(1)
append(nil, appendAll#1(gen_:::nil2_0(n633_0))) ->_IH
append(nil, gen_:::nil2_0(0)) ->_R^Omega(1)
append#1(nil, gen_:::nil2_0(0)) ->_L^Omega(1)
gen_:::nil2_0(+(0, 0))

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

(24)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
append#1(nil, @l2) -> @l2
appendAll(@l) -> appendAll#1(@l)
appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
appendAll#1(nil) -> nil
appendAll2(@l) -> appendAll2#1(@l)
appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
appendAll2#1(nil) -> nil
appendAll3(@l) -> appendAll3#1(@l)
appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
appendAll3#1(nil) -> nil

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil -> :::nil
nil :: :::nil
appendAll :: :::nil -> :::nil
appendAll#1 :: :::nil -> :::nil
appendAll2 :: :::nil -> :::nil
appendAll2#1 :: :::nil -> :::nil
appendAll3 :: :::nil -> :::nil
appendAll3#1 :: :::nil -> :::nil
hole_:::nil1_0 :: :::nil
gen_:::nil2_0 :: Nat -> :::nil


Lemmas:
append#1(gen_:::nil2_0(n4_0), gen_:::nil2_0(b)) -> gen_:::nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
appendAll#1(gen_:::nil2_0(n633_0)) -> gen_:::nil2_0(0), rt in Omega(1 + n633_0)


Generator Equations:
gen_:::nil2_0(0) <=> nil
gen_:::nil2_0(+(x, 1)) <=> ::(nil, gen_:::nil2_0(x))


The following defined symbols remain to be analysed:
appendAll, appendAll2, appendAll2#1, appendAll3, appendAll3#1

They will be analysed ascendingly in the following order:
appendAll = appendAll#1
appendAll < appendAll2#1
appendAll2 = appendAll2#1
appendAll2 < appendAll3#1
appendAll3 = appendAll3#1

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

(25) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
appendAll2#1(gen_:::nil2_0(n1017_0)) -> gen_:::nil2_0(0), rt in Omega(1 + n1017_0)

Induction Base:
appendAll2#1(gen_:::nil2_0(0)) ->_R^Omega(1)
nil

Induction Step:
appendAll2#1(gen_:::nil2_0(+(n1017_0, 1))) ->_R^Omega(1)
append(appendAll(nil), appendAll2(gen_:::nil2_0(n1017_0))) ->_R^Omega(1)
append(appendAll#1(nil), appendAll2(gen_:::nil2_0(n1017_0))) ->_L^Omega(1)
append(gen_:::nil2_0(0), appendAll2(gen_:::nil2_0(n1017_0))) ->_R^Omega(1)
append(gen_:::nil2_0(0), appendAll2#1(gen_:::nil2_0(n1017_0))) ->_IH
append(gen_:::nil2_0(0), gen_:::nil2_0(0)) ->_R^Omega(1)
append#1(gen_:::nil2_0(0), gen_:::nil2_0(0)) ->_L^Omega(1)
gen_:::nil2_0(+(0, 0))

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

(26)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
append#1(nil, @l2) -> @l2
appendAll(@l) -> appendAll#1(@l)
appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
appendAll#1(nil) -> nil
appendAll2(@l) -> appendAll2#1(@l)
appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
appendAll2#1(nil) -> nil
appendAll3(@l) -> appendAll3#1(@l)
appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
appendAll3#1(nil) -> nil

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil -> :::nil
nil :: :::nil
appendAll :: :::nil -> :::nil
appendAll#1 :: :::nil -> :::nil
appendAll2 :: :::nil -> :::nil
appendAll2#1 :: :::nil -> :::nil
appendAll3 :: :::nil -> :::nil
appendAll3#1 :: :::nil -> :::nil
hole_:::nil1_0 :: :::nil
gen_:::nil2_0 :: Nat -> :::nil


Lemmas:
append#1(gen_:::nil2_0(n4_0), gen_:::nil2_0(b)) -> gen_:::nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
appendAll#1(gen_:::nil2_0(n633_0)) -> gen_:::nil2_0(0), rt in Omega(1 + n633_0)
appendAll2#1(gen_:::nil2_0(n1017_0)) -> gen_:::nil2_0(0), rt in Omega(1 + n1017_0)


Generator Equations:
gen_:::nil2_0(0) <=> nil
gen_:::nil2_0(+(x, 1)) <=> ::(nil, gen_:::nil2_0(x))


The following defined symbols remain to be analysed:
appendAll2, appendAll3, appendAll3#1

They will be analysed ascendingly in the following order:
appendAll2 = appendAll2#1
appendAll2 < appendAll3#1
appendAll3 = appendAll3#1

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

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
appendAll3#1(gen_:::nil2_0(n1767_0)) -> gen_:::nil2_0(0), rt in Omega(1 + n1767_0)

Induction Base:
appendAll3#1(gen_:::nil2_0(0)) ->_R^Omega(1)
nil

Induction Step:
appendAll3#1(gen_:::nil2_0(+(n1767_0, 1))) ->_R^Omega(1)
append(appendAll2(nil), appendAll3(gen_:::nil2_0(n1767_0))) ->_R^Omega(1)
append(appendAll2#1(nil), appendAll3(gen_:::nil2_0(n1767_0))) ->_L^Omega(1)
append(gen_:::nil2_0(0), appendAll3(gen_:::nil2_0(n1767_0))) ->_R^Omega(1)
append(gen_:::nil2_0(0), appendAll3#1(gen_:::nil2_0(n1767_0))) ->_IH
append(gen_:::nil2_0(0), gen_:::nil2_0(0)) ->_R^Omega(1)
append#1(gen_:::nil2_0(0), gen_:::nil2_0(0)) ->_L^Omega(1)
gen_:::nil2_0(+(0, 0))

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

(28)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
append#1(nil, @l2) -> @l2
appendAll(@l) -> appendAll#1(@l)
appendAll#1(::(@l1, @ls)) -> append(@l1, appendAll(@ls))
appendAll#1(nil) -> nil
appendAll2(@l) -> appendAll2#1(@l)
appendAll2#1(::(@l1, @ls)) -> append(appendAll(@l1), appendAll2(@ls))
appendAll2#1(nil) -> nil
appendAll3(@l) -> appendAll3#1(@l)
appendAll3#1(::(@l1, @ls)) -> append(appendAll2(@l1), appendAll3(@ls))
appendAll3#1(nil) -> nil

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil -> :::nil
nil :: :::nil
appendAll :: :::nil -> :::nil
appendAll#1 :: :::nil -> :::nil
appendAll2 :: :::nil -> :::nil
appendAll2#1 :: :::nil -> :::nil
appendAll3 :: :::nil -> :::nil
appendAll3#1 :: :::nil -> :::nil
hole_:::nil1_0 :: :::nil
gen_:::nil2_0 :: Nat -> :::nil


Lemmas:
append#1(gen_:::nil2_0(n4_0), gen_:::nil2_0(b)) -> gen_:::nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
appendAll#1(gen_:::nil2_0(n633_0)) -> gen_:::nil2_0(0), rt in Omega(1 + n633_0)
appendAll2#1(gen_:::nil2_0(n1017_0)) -> gen_:::nil2_0(0), rt in Omega(1 + n1017_0)
appendAll3#1(gen_:::nil2_0(n1767_0)) -> gen_:::nil2_0(0), rt in Omega(1 + n1767_0)


Generator Equations:
gen_:::nil2_0(0) <=> nil
gen_:::nil2_0(+(x, 1)) <=> ::(nil, gen_:::nil2_0(x))


The following defined symbols remain to be analysed:
appendAll3

They will be analysed ascendingly in the following order:
appendAll3 = appendAll3#1