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) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CpxWeightedTrs
    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxTypedWeightedTrs
    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
    (8) CpxTypedWeightedCompleteTrs
    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (10) CpxRNTS
    (11) CompleteCoflocoProof [FINISHED, 223 ms]
    (12) BOUNDS(1, n^1)
(13) RenamingProof [BOTH BOUNDS(ID, 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), 402 ms]
    (20) proven lower bound
    (21) LowerBoundPropagationProof [FINISHED, 0 ms]
    (22) BOUNDS(n^1, INF)


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

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

   del(.(x, .(y, z))) -> f(=(x, y), x, y, z)
   f(true, x, y, z) -> del(.(y, z))
   f(false, x, y, z) -> .(x, del(.(y, z)))
   =(nil, nil) -> true
   =(.(x, y), nil) -> false
   =(nil, .(y, z)) -> false
   =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v))

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:

   del(.(x, .(y, z))) -> f(=(x, y), x, y, z) [1]
   f(true, x, y, z) -> del(.(y, z)) [1]
   f(false, x, y, z) -> .(x, del(.(y, z))) [1]
   =(nil, nil) -> true [1]
   =(.(x, y), nil) -> false [1]
   =(nil, .(y, z)) -> false [1]
   =(.(x, y), .(u, v)) -> and(=(x, u), =(y, v)) [1]

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

(3) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
Renamed defined symbols to avoid conflicts with arithmetic symbols:

= => eq

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

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

   del(.(x, .(y, z))) -> f(eq(x, y), x, y, z) [1]
   f(true, x, y, z) -> del(.(y, z)) [1]
   f(false, x, y, z) -> .(x, del(.(y, z))) [1]
   eq(nil, nil) -> true [1]
   eq(.(x, y), nil) -> false [1]
   eq(nil, .(y, z)) -> false [1]
   eq(.(x, y), .(u, v)) -> and(eq(x, u), eq(y, v)) [1]

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

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

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

   del(.(x, .(y, z))) -> f(eq(x, y), x, y, z) [1]
   f(true, x, y, z) -> del(.(y, z)) [1]
   f(false, x, y, z) -> .(x, del(.(y, z))) [1]
   eq(nil, nil) -> true [1]
   eq(.(x, y), nil) -> false [1]
   eq(nil, .(y, z)) -> false [1]
   eq(.(x, y), .(u, v)) -> and(eq(x, u), eq(y, v)) [1]

The TRS has the following type information:
del :: .:nil:u:v -> .:nil:u:v
. :: .:nil:u:v -> .:nil:u:v -> .:nil:u:v
f :: true:false:and -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v
eq :: .:nil:u:v -> .:nil:u:v -> true:false:and
true :: true:false:and
false :: true:false:and
nil :: .:nil:u:v
u :: .:nil:u:v
v :: .:nil:u:v
and :: true:false:and -> true:false:and -> true:false:and

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

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

   del(v0) -> null_del [0]
   f(v0, v1, v2, v3) -> null_f [0]
   eq(v0, v1) -> null_eq [0]

And the following fresh constants:    null_del, null_f, null_eq

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

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

   del(.(x, .(y, z))) -> f(eq(x, y), x, y, z) [1]
   f(true, x, y, z) -> del(.(y, z)) [1]
   f(false, x, y, z) -> .(x, del(.(y, z))) [1]
   eq(nil, nil) -> true [1]
   eq(.(x, y), nil) -> false [1]
   eq(nil, .(y, z)) -> false [1]
   eq(.(x, y), .(u, v)) -> and(eq(x, u), eq(y, v)) [1]
   del(v0) -> null_del [0]
   f(v0, v1, v2, v3) -> null_f [0]
   eq(v0, v1) -> null_eq [0]

The TRS has the following type information:
del :: .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f
. :: .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f
f :: true:false:and:null_eq -> .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f
eq :: .:nil:u:v:null_del:null_f -> .:nil:u:v:null_del:null_f -> true:false:and:null_eq
true :: true:false:and:null_eq
false :: true:false:and:null_eq
nil :: .:nil:u:v:null_del:null_f
u :: .:nil:u:v:null_del:null_f
v :: .:nil:u:v:null_del:null_f
and :: true:false:and:null_eq -> true:false:and:null_eq -> true:false:and:null_eq
null_del :: .:nil:u:v:null_del:null_f
null_f :: .:nil:u:v:null_del:null_f
null_eq :: true:false:and:null_eq

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

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

   true => 1
   false => 0
   nil => 0
   u => 1
   v => 2
   null_del => 0
   null_f => 0
   null_eq => 0

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

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

   del(z') -{ 1 }-> f(eq(x, y), x, y, z) :|: z' = 1 + x + (1 + y + z), z >= 0, x >= 0, y >= 0
   del(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0
   eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 1 + x + y, x >= 0, y >= 0
   eq(z', z'') -{ 1 }-> 0 :|: z >= 0, y >= 0, z'' = 1 + y + z, z' = 0
   eq(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   eq(z', z'') -{ 1 }-> 1 + eq(x, 1) + eq(y, 2) :|: z'' = 1 + 1 + 2, z' = 1 + x + y, x >= 0, y >= 0
   f(z', z'', z1, z2) -{ 1 }-> del(1 + y + z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1
   f(z', z'', z1, z2) -{ 0 }-> 0 :|: z2 = v3, v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, v3 >= 0, z' = v0
   f(z', z'', z1, z2) -{ 1 }-> 1 + x + del(1 + y + z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 0

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V, V6, V9, V7),0,[del(V, Out)],[V >= 0]).
eq(start(V, V6, V9, V7),0,[f(V, V6, V9, V7, Out)],[V >= 0,V6 >= 0,V9 >= 0,V7 >= 0]).
eq(start(V, V6, V9, V7),0,[eq(V, V6, Out)],[V >= 0,V6 >= 0]).
eq(del(V, Out),1,[eq(V2, V1, Ret0),f(Ret0, V2, V1, V3, Ret)],[Out = Ret,V = 2 + V1 + V2 + V3,V3 >= 0,V2 >= 0,V1 >= 0]).
eq(f(V, V6, V9, V7, Out),1,[del(1 + V8 + V4, Ret1)],[Out = Ret1,V9 = V8,V4 >= 0,V7 = V4,V5 >= 0,V8 >= 0,V6 = V5,V = 1]).
eq(f(V, V6, V9, V7, Out),1,[del(1 + V10 + V12, Ret11)],[Out = 1 + Ret11 + V11,V9 = V10,V12 >= 0,V7 = V12,V11 >= 0,V10 >= 0,V6 = V11,V = 0]).
eq(eq(V, V6, Out),1,[],[Out = 1,V6 = 0,V = 0]).
eq(eq(V, V6, Out),1,[],[Out = 0,V6 = 0,V = 1 + V13 + V14,V13 >= 0,V14 >= 0]).
eq(eq(V, V6, Out),1,[],[Out = 0,V15 >= 0,V16 >= 0,V6 = 1 + V15 + V16,V = 0]).
eq(eq(V, V6, Out),1,[eq(V17, 1, Ret01),eq(V18, 2, Ret12)],[Out = 1 + Ret01 + Ret12,V6 = 4,V = 1 + V17 + V18,V17 >= 0,V18 >= 0]).
eq(del(V, Out),0,[],[Out = 0,V19 >= 0,V = V19]).
eq(f(V, V6, V9, V7, Out),0,[],[Out = 0,V7 = V22,V21 >= 0,V9 = V23,V20 >= 0,V6 = V20,V23 >= 0,V22 >= 0,V = V21]).
eq(eq(V, V6, Out),0,[],[Out = 0,V25 >= 0,V24 >= 0,V6 = V24,V = V25]).
input_output_vars(del(V,Out),[V],[Out]).
input_output_vars(f(V,V6,V9,V7,Out),[V,V6,V9,V7],[Out]).
input_output_vars(eq(V,V6,Out),[V,V6],[Out]).


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

#### Computed strongly connected components 
0. recursive [multiple] : [eq/3]
1. recursive  : [del/2,f/5]
2. non_recursive  : [start/4]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into eq/3
1. SCC is partially evaluated into del/2
2. SCC is partially evaluated into start/4

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

### Specialization of cost equations eq/3 
* CE 11 is refined into CE [15] 
* CE 12 is refined into CE [16] 
* CE 14 is refined into CE [17] 
* CE 10 is refined into CE [18] 
* CE 13 is refined into CE [19] 


### Cost equations --> "Loop" of eq/3 
* CEs [19] --> Loop 10 
* CEs [15] --> Loop 11 
* CEs [16,17] --> Loop 12 
* CEs [18] --> Loop 13 

### Ranking functions of CR eq(V,V6,Out) 

#### Partial ranking functions of CR eq(V,V6,Out) 


### Specialization of cost equations del/2 
* CE 6 is refined into CE [20,21,22] 
* CE 9 is refined into CE [23] 
* CE 7 is refined into CE [24] 
* CE 8 is refined into CE [25,26] 


### Cost equations --> "Loop" of del/2 
* CEs [24] --> Loop 14 
* CEs [26] --> Loop 15 
* CEs [25] --> Loop 16 
* CEs [20,21,22,23] --> Loop 17 

### Ranking functions of CR del(V,Out) 
* RF of phase [14,15,16]: [V-1]

#### Partial ranking functions of CR del(V,Out) 
* Partial RF of phase [14,15,16]:
  - RF of loop [14:1,16:1]:
    V-1
  - RF of loop [15:1]:
    V/2-3


### Specialization of cost equations start/4 
* CE 3 is refined into CE [27,28] 
* CE 1 is refined into CE [29] 
* CE 2 is refined into CE [30,31] 
* CE 4 is refined into CE [32,33] 
* CE 5 is refined into CE [34,35,36] 


### Cost equations --> "Loop" of start/4 
* CEs [36] --> Loop 18 
* CEs [27,28] --> Loop 19 
* CEs [30,31] --> Loop 20 
* CEs [29,32,33,34,35] --> Loop 21 

### Ranking functions of CR start(V,V6,V9,V7) 

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


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

#### Cost of chains of eq(V,V6,Out):
* Chain [13]: 1
  with precondition: [V=0,V6=0,Out=1] 

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

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

* Chain [multiple(10,[[12]])]: 3
  with precondition: [V6=4,Out=1,V>=1] 


#### Cost of chains of del(V,Out):
* Chain [[14,15,16],17]: 6*it(14)+5*it(15)+4
  Such that:it(15) =< V/2
aux(3) =< V
it(14) =< aux(3)
it(15) =< aux(3)

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

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


#### Cost of chains of start(V,V6,V9,V7):
* Chain [21]: 5*s(1)+6*s(3)+4
  Such that:s(2) =< V
s(1) =< V/2
s(3) =< s(2)
s(1) =< s(2)

  with precondition: [V>=0] 

* Chain [20]: 5*s(4)+6*s(6)+5
  Such that:s(5) =< V9+V7+1
s(4) =< V9/2+V7/2+1/2
s(6) =< s(5)
s(4) =< s(5)

  with precondition: [V=0,V6>=0,V9>=0,V7>=0] 

* Chain [19]: 5*s(7)+6*s(9)+5
  Such that:s(8) =< V9+V7+1
s(7) =< V9/2+V7/2+1/2
s(9) =< s(8)
s(7) =< s(8)

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

* Chain [18]: 3
  with precondition: [V6=4,V>=1] 


Closed-form bounds of start(V,V6,V9,V7): 
-------------------------------------
* Chain [21] with precondition: [V>=0] 
    - Upper bound: 17/2*V+4 
    - Complexity: n 
* Chain [20] with precondition: [V=0,V6>=0,V9>=0,V7>=0] 
    - Upper bound: 17/2*V9+17/2*V7+27/2 
    - Complexity: n 
* Chain [19] with precondition: [V=1,V6>=0,V9>=0,V7>=0] 
    - Upper bound: 17/2*V9+17/2*V7+27/2 
    - Complexity: n 
* Chain [18] with precondition: [V6=4,V>=1] 
    - Upper bound: 3 
    - Complexity: constant 

### Maximum cost of start(V,V6,V9,V7): max([17/2*V+1,nat(V9+V7+1)*6+2+nat(V9/2+V7/2+1/2)*5])+3 
Asymptotic class: n 
* Total analysis performed in 153 ms.


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

(12)
BOUNDS(1, n^1)

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

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

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

   del(.(x, .(y, z))) -> f(='(x, y), x, y, z)
   f(true, x, y, z) -> del(.(y, z))
   f(false, x, y, z) -> .(x, del(.(y, z)))
   ='(nil, nil) -> true
   ='(.(x, y), nil) -> false
   ='(nil, .(y, z)) -> false
   ='(.(x, y), .(u, v)) -> and(='(x, u), ='(y, v))

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

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

(16)
Obligation:
Innermost TRS:
Rules:
del(.(x, .(y, z))) -> f(='(x, y), x, y, z)
f(true, x, y, z) -> del(.(y, z))
f(false, x, y, z) -> .(x, del(.(y, z)))
='(nil, nil) -> true
='(.(x, y), nil) -> false
='(nil, .(y, z)) -> false
='(.(x, y), .(u, v)) -> and(='(x, u), ='(y, v))

Types:
del :: .:nil:u:v -> .:nil:u:v
. :: .:nil:u:v -> .:nil:u:v -> .:nil:u:v
f :: true:false:and -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v
=' :: .:nil:u:v -> .:nil:u:v -> true:false:and
true :: true:false:and
false :: true:false:and
nil :: .:nil:u:v
u :: .:nil:u:v
v :: .:nil:u:v
and :: true:false:and -> true:false:and -> true:false:and
hole_.:nil:u:v1_0 :: .:nil:u:v
hole_true:false:and2_0 :: true:false:and
gen_.:nil:u:v3_0 :: Nat -> .:nil:u:v
gen_true:false:and4_0 :: Nat -> true:false:and

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

(17) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
del, ='

They will be analysed ascendingly in the following order:
=' < del

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

(18)
Obligation:
Innermost TRS:
Rules:
del(.(x, .(y, z))) -> f(='(x, y), x, y, z)
f(true, x, y, z) -> del(.(y, z))
f(false, x, y, z) -> .(x, del(.(y, z)))
='(nil, nil) -> true
='(.(x, y), nil) -> false
='(nil, .(y, z)) -> false
='(.(x, y), .(u, v)) -> and(='(x, u), ='(y, v))

Types:
del :: .:nil:u:v -> .:nil:u:v
. :: .:nil:u:v -> .:nil:u:v -> .:nil:u:v
f :: true:false:and -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v
=' :: .:nil:u:v -> .:nil:u:v -> true:false:and
true :: true:false:and
false :: true:false:and
nil :: .:nil:u:v
u :: .:nil:u:v
v :: .:nil:u:v
and :: true:false:and -> true:false:and -> true:false:and
hole_.:nil:u:v1_0 :: .:nil:u:v
hole_true:false:and2_0 :: true:false:and
gen_.:nil:u:v3_0 :: Nat -> .:nil:u:v
gen_true:false:and4_0 :: Nat -> true:false:and


Generator Equations:
gen_.:nil:u:v3_0(0) <=> nil
gen_.:nil:u:v3_0(+(x, 1)) <=> .(nil, gen_.:nil:u:v3_0(x))
gen_true:false:and4_0(0) <=> false
gen_true:false:and4_0(+(x, 1)) <=> and(false, gen_true:false:and4_0(x))


The following defined symbols remain to be analysed:
=', del

They will be analysed ascendingly in the following order:
=' < del

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

(19) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
del(gen_.:nil:u:v3_0(+(2, n56_0))) -> *5_0, rt in Omega(n56_0)

Induction Base:
del(gen_.:nil:u:v3_0(+(2, 0)))

Induction Step:
del(gen_.:nil:u:v3_0(+(2, +(n56_0, 1)))) ->_R^Omega(1)
f(='(nil, nil), nil, nil, gen_.:nil:u:v3_0(+(1, n56_0))) ->_R^Omega(1)
f(true, nil, nil, gen_.:nil:u:v3_0(+(1, n56_0))) ->_R^Omega(1)
del(.(nil, gen_.:nil:u:v3_0(+(1, n56_0)))) ->_IH
*5_0

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

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

Innermost TRS:
Rules:
del(.(x, .(y, z))) -> f(='(x, y), x, y, z)
f(true, x, y, z) -> del(.(y, z))
f(false, x, y, z) -> .(x, del(.(y, z)))
='(nil, nil) -> true
='(.(x, y), nil) -> false
='(nil, .(y, z)) -> false
='(.(x, y), .(u, v)) -> and(='(x, u), ='(y, v))

Types:
del :: .:nil:u:v -> .:nil:u:v
. :: .:nil:u:v -> .:nil:u:v -> .:nil:u:v
f :: true:false:and -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v -> .:nil:u:v
=' :: .:nil:u:v -> .:nil:u:v -> true:false:and
true :: true:false:and
false :: true:false:and
nil :: .:nil:u:v
u :: .:nil:u:v
v :: .:nil:u:v
and :: true:false:and -> true:false:and -> true:false:and
hole_.:nil:u:v1_0 :: .:nil:u:v
hole_true:false:and2_0 :: true:false:and
gen_.:nil:u:v3_0 :: Nat -> .:nil:u:v
gen_true:false:and4_0 :: Nat -> true:false:and


Generator Equations:
gen_.:nil:u:v3_0(0) <=> nil
gen_.:nil:u:v3_0(+(x, 1)) <=> .(nil, gen_.:nil:u:v3_0(x))
gen_true:false:and4_0(0) <=> false
gen_true:false:and4_0(+(x, 1)) <=> and(false, gen_true:false:and4_0(x))


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

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

(22)
BOUNDS(n^1, INF)