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), 2 ms]
    (8) CpxRNTS
    (9) CompleteCoflocoProof [FINISHED, 108 ms]
    (10) BOUNDS(1, n^1)
(11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(12) CpxTRS
    (13) SlicingProof [LOWER BOUND(ID), 0 ms]
    (14) CpxTRS
    (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (16) typed CpxTrs
    (17) OrderProof [LOWER BOUND(ID), 0 ms]
    (18) typed CpxTrs
    (19) RewriteLemmaProof [LOWER BOUND(ID), 209 ms]
    (20) BEST
        (21) proven lower bound
            (22) LowerBoundPropagationProof [FINISHED, 0 ms]
            (23) BOUNDS(n^1, INF)
        (24) 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:

   is_empty(nil) -> true
   is_empty(cons(x, l)) -> false
   hd(cons(x, l)) -> x
   tl(cons(x, l)) -> l
   append(l1, l2) -> ifappend(l1, l2, l1)
   ifappend(l1, l2, nil) -> l2
   ifappend(l1, l2, cons(x, l)) -> cons(x, append(l, l2))

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:

   is_empty(nil) -> true [1]
   is_empty(cons(x, l)) -> false [1]
   hd(cons(x, l)) -> x [1]
   tl(cons(x, l)) -> l [1]
   append(l1, l2) -> ifappend(l1, l2, l1) [1]
   ifappend(l1, l2, nil) -> l2 [1]
   ifappend(l1, l2, cons(x, l)) -> cons(x, append(l, l2)) [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:

   is_empty(nil) -> true [1]
   is_empty(cons(x, l)) -> false [1]
   hd(cons(x, l)) -> x [1]
   tl(cons(x, l)) -> l [1]
   append(l1, l2) -> ifappend(l1, l2, l1) [1]
   ifappend(l1, l2, nil) -> l2 [1]
   ifappend(l1, l2, cons(x, l)) -> cons(x, append(l, l2)) [1]

The TRS has the following type information:
is_empty :: nil:cons -> true:false
nil :: nil:cons
true :: true:false
cons :: hd -> nil:cons -> nil:cons
false :: true:false
hd :: nil:cons -> hd
tl :: nil:cons -> nil:cons
append :: nil:cons -> nil:cons -> nil:cons
ifappend :: nil:cons -> nil:cons -> nil:cons -> nil:cons

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:

   hd(v0) -> null_hd [0]
   tl(v0) -> null_tl [0]
   is_empty(v0) -> null_is_empty [0]
   ifappend(v0, v1, v2) -> null_ifappend [0]

And the following fresh constants:    null_hd, null_tl, null_is_empty, null_ifappend

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

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

   is_empty(nil) -> true [1]
   is_empty(cons(x, l)) -> false [1]
   hd(cons(x, l)) -> x [1]
   tl(cons(x, l)) -> l [1]
   append(l1, l2) -> ifappend(l1, l2, l1) [1]
   ifappend(l1, l2, nil) -> l2 [1]
   ifappend(l1, l2, cons(x, l)) -> cons(x, append(l, l2)) [1]
   hd(v0) -> null_hd [0]
   tl(v0) -> null_tl [0]
   is_empty(v0) -> null_is_empty [0]
   ifappend(v0, v1, v2) -> null_ifappend [0]

The TRS has the following type information:
is_empty :: nil:cons:null_tl:null_ifappend -> true:false:null_is_empty
nil :: nil:cons:null_tl:null_ifappend
true :: true:false:null_is_empty
cons :: null_hd -> nil:cons:null_tl:null_ifappend -> nil:cons:null_tl:null_ifappend
false :: true:false:null_is_empty
hd :: nil:cons:null_tl:null_ifappend -> null_hd
tl :: nil:cons:null_tl:null_ifappend -> nil:cons:null_tl:null_ifappend
append :: nil:cons:null_tl:null_ifappend -> nil:cons:null_tl:null_ifappend -> nil:cons:null_tl:null_ifappend
ifappend :: nil:cons:null_tl:null_ifappend -> nil:cons:null_tl:null_ifappend -> nil:cons:null_tl:null_ifappend -> nil:cons:null_tl:null_ifappend
null_hd :: null_hd
null_tl :: nil:cons:null_tl:null_ifappend
null_is_empty :: true:false:null_is_empty
null_ifappend :: nil:cons:null_tl:null_ifappend

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_hd => 0
   null_tl => 0
   null_is_empty => 0
   null_ifappend => 0

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

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

   append(z, z') -{ 1 }-> ifappend(l1, l2, l1) :|: z = l1, z' = l2, l1 >= 0, l2 >= 0
   hd(z) -{ 1 }-> x :|: x >= 0, l >= 0, z = 1 + x + l
   hd(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   ifappend(z, z', z'') -{ 1 }-> l2 :|: z'' = 0, z = l1, z' = l2, l1 >= 0, l2 >= 0
   ifappend(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   ifappend(z, z', z'') -{ 1 }-> 1 + x + append(l, l2) :|: z'' = 1 + x + l, z = l1, x >= 0, l >= 0, z' = l2, l1 >= 0, l2 >= 0
   is_empty(z) -{ 1 }-> 2 :|: z = 0
   is_empty(z) -{ 1 }-> 1 :|: x >= 0, l >= 0, z = 1 + x + l
   is_empty(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   tl(z) -{ 1 }-> l :|: x >= 0, l >= 0, z = 1 + x + l
   tl(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0

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, V7, V10),0,[fun(V, Out)],[V >= 0]).
eq(start(V, V7, V10),0,[hd(V, Out)],[V >= 0]).
eq(start(V, V7, V10),0,[tl(V, Out)],[V >= 0]).
eq(start(V, V7, V10),0,[append(V, V7, Out)],[V >= 0,V7 >= 0]).
eq(start(V, V7, V10),0,[ifappend(V, V7, V10, Out)],[V >= 0,V7 >= 0,V10 >= 0]).
eq(fun(V, Out),1,[],[Out = 2,V = 0]).
eq(fun(V, Out),1,[],[Out = 1,V1 >= 0,V2 >= 0,V = 1 + V1 + V2]).
eq(hd(V, Out),1,[],[Out = V3,V3 >= 0,V4 >= 0,V = 1 + V3 + V4]).
eq(tl(V, Out),1,[],[Out = V6,V5 >= 0,V6 >= 0,V = 1 + V5 + V6]).
eq(append(V, V7, Out),1,[ifappend(V9, V8, V9, Ret)],[Out = Ret,V = V9,V7 = V8,V9 >= 0,V8 >= 0]).
eq(ifappend(V, V7, V10, Out),1,[],[Out = V11,V10 = 0,V = V12,V7 = V11,V12 >= 0,V11 >= 0]).
eq(ifappend(V, V7, V10, Out),1,[append(V15, V16, Ret1)],[Out = 1 + Ret1 + V13,V10 = 1 + V13 + V15,V = V14,V13 >= 0,V15 >= 0,V7 = V16,V14 >= 0,V16 >= 0]).
eq(hd(V, Out),0,[],[Out = 0,V17 >= 0,V = V17]).
eq(tl(V, Out),0,[],[Out = 0,V18 >= 0,V = V18]).
eq(fun(V, Out),0,[],[Out = 0,V19 >= 0,V = V19]).
eq(ifappend(V, V7, V10, Out),0,[],[Out = 0,V20 >= 0,V10 = V22,V21 >= 0,V = V20,V7 = V21,V22 >= 0]).
input_output_vars(fun(V,Out),[V],[Out]).
input_output_vars(hd(V,Out),[V],[Out]).
input_output_vars(tl(V,Out),[V],[Out]).
input_output_vars(append(V,V7,Out),[V,V7],[Out]).
input_output_vars(ifappend(V,V7,V10,Out),[V,V7,V10],[Out]).


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

#### Computed strongly connected components 
0. recursive  : [append/3,ifappend/4]
1. non_recursive  : [fun/2]
2. non_recursive  : [hd/2]
3. non_recursive  : [tl/2]
4. non_recursive  : [start/3]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into append/3
1. SCC is partially evaluated into fun/2
2. SCC is partially evaluated into hd/2
3. SCC is partially evaluated into tl/2
4. SCC is partially evaluated into start/3

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

### Specialization of cost equations append/3 
* CE 8 is refined into CE [18] 
* CE 10 is refined into CE [19] 
* CE 9 is refined into CE [20] 


### Cost equations --> "Loop" of append/3 
* CEs [20] --> Loop 12 
* CEs [18] --> Loop 13 
* CEs [19] --> Loop 14 

### Ranking functions of CR append(V,V7,Out) 
* RF of phase [12]: [V]

#### Partial ranking functions of CR append(V,V7,Out) 
* Partial RF of phase [12]:
  - RF of loop [12:1]:
    V


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


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

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

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


### Specialization of cost equations hd/2 
* CE 14 is refined into CE [24] 
* CE 15 is refined into CE [25] 


### Cost equations --> "Loop" of hd/2 
* CEs [24] --> Loop 18 
* CEs [25] --> Loop 19 

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

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


### Specialization of cost equations tl/2 
* CE 16 is refined into CE [26] 
* CE 17 is refined into CE [27] 


### Cost equations --> "Loop" of tl/2 
* CEs [26] --> Loop 20 
* CEs [27] --> Loop 21 

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

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


### Specialization of cost equations start/3 
* CE 1 is refined into CE [28] 
* CE 2 is refined into CE [29,30,31,32] 
* CE 3 is refined into CE [33] 
* CE 4 is refined into CE [34,35,36] 
* CE 5 is refined into CE [37,38] 
* CE 6 is refined into CE [39,40] 
* CE 7 is refined into CE [41,42,43,44] 


### Cost equations --> "Loop" of start/3 
* CEs [33] --> Loop 22 
* CEs [28,29,30,31,32,34,35,36,37,38,39,40,41,42,43,44] --> Loop 23 

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

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


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

#### Cost of chains of append(V,V7,Out):
* Chain [[12],14]: 2*it(12)+2
  Such that:it(12) =< -V7+Out

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

* Chain [[12],13]: 2*it(12)+1
  Such that:it(12) =< Out

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

* Chain [14]: 2
  with precondition: [V=0,V7=Out,V7>=0] 

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


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

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

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


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

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


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

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


#### Cost of chains of start(V,V7,V10):
* Chain [23]: 4*s(1)+4*s(3)+3
  Such that:aux(1) =< V
aux(2) =< V10
s(3) =< aux(1)
s(1) =< aux(2)

  with precondition: [V>=0] 

* Chain [22]: 1
  with precondition: [V10=0,V>=0,V7>=0] 


Closed-form bounds of start(V,V7,V10): 
-------------------------------------
* Chain [23] with precondition: [V>=0] 
    - Upper bound: 4*V+3+nat(V10)*4 
    - Complexity: n 
* Chain [22] with precondition: [V10=0,V>=0,V7>=0] 
    - Upper bound: 1 
    - Complexity: constant 

### Maximum cost of start(V,V7,V10): 4*V+2+nat(V10)*4+1 
Asymptotic class: n 
* Total analysis performed in 121 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:

   is_empty(nil) -> true
   is_empty(cons(x, l)) -> false
   hd(cons(x, l)) -> x
   tl(cons(x, l)) -> l
   append(l1, l2) -> ifappend(l1, l2, l1)
   ifappend(l1, l2, nil) -> l2
   ifappend(l1, l2, cons(x, l)) -> cons(x, append(l, l2))

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

(13) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
ifappend/0

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

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

   is_empty(nil) -> true
   is_empty(cons(x, l)) -> false
   hd(cons(x, l)) -> x
   tl(cons(x, l)) -> l
   append(l1, l2) -> ifappend(l2, l1)
   ifappend(l2, nil) -> l2
   ifappend(l2, cons(x, l)) -> cons(x, append(l, l2))

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

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

(16)
Obligation:
Innermost TRS:
Rules:
is_empty(nil) -> true
is_empty(cons(x, l)) -> false
hd(cons(x, l)) -> x
tl(cons(x, l)) -> l
append(l1, l2) -> ifappend(l2, l1)
ifappend(l2, nil) -> l2
ifappend(l2, cons(x, l)) -> cons(x, append(l, l2))

Types:
is_empty :: nil:cons -> true:false
nil :: nil:cons
true :: true:false
cons :: hd -> nil:cons -> nil:cons
false :: true:false
hd :: nil:cons -> hd
tl :: nil:cons -> nil:cons
append :: nil:cons -> nil:cons -> nil:cons
ifappend :: nil:cons -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_nil:cons2_0 :: nil:cons
hole_hd3_0 :: hd
gen_nil:cons4_0 :: Nat -> nil:cons

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

(17) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
append, ifappend

They will be analysed ascendingly in the following order:
append = ifappend

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

(18)
Obligation:
Innermost TRS:
Rules:
is_empty(nil) -> true
is_empty(cons(x, l)) -> false
hd(cons(x, l)) -> x
tl(cons(x, l)) -> l
append(l1, l2) -> ifappend(l2, l1)
ifappend(l2, nil) -> l2
ifappend(l2, cons(x, l)) -> cons(x, append(l, l2))

Types:
is_empty :: nil:cons -> true:false
nil :: nil:cons
true :: true:false
cons :: hd -> nil:cons -> nil:cons
false :: true:false
hd :: nil:cons -> hd
tl :: nil:cons -> nil:cons
append :: nil:cons -> nil:cons -> nil:cons
ifappend :: nil:cons -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_nil:cons2_0 :: nil:cons
hole_hd3_0 :: hd
gen_nil:cons4_0 :: Nat -> nil:cons


Generator Equations:
gen_nil:cons4_0(0) <=> nil
gen_nil:cons4_0(+(x, 1)) <=> cons(hole_hd3_0, gen_nil:cons4_0(x))


The following defined symbols remain to be analysed:
ifappend, append

They will be analysed ascendingly in the following order:
append = ifappend

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

(19) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
ifappend(gen_nil:cons4_0(a), gen_nil:cons4_0(n6_0)) -> gen_nil:cons4_0(+(n6_0, a)), rt in Omega(1 + n6_0)

Induction Base:
ifappend(gen_nil:cons4_0(a), gen_nil:cons4_0(0)) ->_R^Omega(1)
gen_nil:cons4_0(a)

Induction Step:
ifappend(gen_nil:cons4_0(a), gen_nil:cons4_0(+(n6_0, 1))) ->_R^Omega(1)
cons(hole_hd3_0, append(gen_nil:cons4_0(n6_0), gen_nil:cons4_0(a))) ->_R^Omega(1)
cons(hole_hd3_0, ifappend(gen_nil:cons4_0(a), gen_nil:cons4_0(n6_0))) ->_IH
cons(hole_hd3_0, gen_nil:cons4_0(+(a, c7_0)))

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

(20)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
is_empty(nil) -> true
is_empty(cons(x, l)) -> false
hd(cons(x, l)) -> x
tl(cons(x, l)) -> l
append(l1, l2) -> ifappend(l2, l1)
ifappend(l2, nil) -> l2
ifappend(l2, cons(x, l)) -> cons(x, append(l, l2))

Types:
is_empty :: nil:cons -> true:false
nil :: nil:cons
true :: true:false
cons :: hd -> nil:cons -> nil:cons
false :: true:false
hd :: nil:cons -> hd
tl :: nil:cons -> nil:cons
append :: nil:cons -> nil:cons -> nil:cons
ifappend :: nil:cons -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_nil:cons2_0 :: nil:cons
hole_hd3_0 :: hd
gen_nil:cons4_0 :: Nat -> nil:cons


Generator Equations:
gen_nil:cons4_0(0) <=> nil
gen_nil:cons4_0(+(x, 1)) <=> cons(hole_hd3_0, gen_nil:cons4_0(x))


The following defined symbols remain to be analysed:
ifappend, append

They will be analysed ascendingly in the following order:
append = ifappend

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

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

(23)
BOUNDS(n^1, INF)

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

(24)
Obligation:
Innermost TRS:
Rules:
is_empty(nil) -> true
is_empty(cons(x, l)) -> false
hd(cons(x, l)) -> x
tl(cons(x, l)) -> l
append(l1, l2) -> ifappend(l2, l1)
ifappend(l2, nil) -> l2
ifappend(l2, cons(x, l)) -> cons(x, append(l, l2))

Types:
is_empty :: nil:cons -> true:false
nil :: nil:cons
true :: true:false
cons :: hd -> nil:cons -> nil:cons
false :: true:false
hd :: nil:cons -> hd
tl :: nil:cons -> nil:cons
append :: nil:cons -> nil:cons -> nil:cons
ifappend :: nil:cons -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_nil:cons2_0 :: nil:cons
hole_hd3_0 :: hd
gen_nil:cons4_0 :: Nat -> nil:cons


Lemmas:
ifappend(gen_nil:cons4_0(a), gen_nil:cons4_0(n6_0)) -> gen_nil:cons4_0(+(n6_0, a)), rt in Omega(1 + n6_0)


Generator Equations:
gen_nil:cons4_0(0) <=> nil
gen_nil:cons4_0(+(x, 1)) <=> cons(hole_hd3_0, gen_nil:cons4_0(x))


The following defined symbols remain to be analysed:
append

They will be analysed ascendingly in the following order:
append = ifappend