/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^2))
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^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), 0 ms]
    (6) CpxTypedWeightedCompleteTrs
    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 1 ms]
    (8) CpxRNTS
    (9) CompleteCoflocoProof [FINISHED, 1856 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), 435 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), 147 ms]
            (24) typed CpxTrs
            (25) RewriteLemmaProof [LOWER BOUND(ID), 84 ms]
            (26) typed CpxTrs


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

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


The TRS R consists of the following rules:

   ge(0, 0) -> true
   ge(s(x), 0) -> ge(x, 0)
   ge(0, s(0)) -> false
   ge(0, s(s(x))) -> ge(0, s(x))
   ge(s(x), s(y)) -> ge(x, y)
   minus(0, 0) -> 0
   minus(0, s(x)) -> minus(0, x)
   minus(s(x), 0) -> s(minus(x, 0))
   minus(s(x), s(y)) -> minus(x, y)
   plus(0, 0) -> 0
   plus(0, s(x)) -> s(plus(0, x))
   plus(s(x), y) -> s(plus(x, y))
   div(x, y) -> ify(ge(y, s(0)), x, y)
   ify(false, x, y) -> divByZeroError
   ify(true, x, y) -> if(ge(x, y), x, y)
   if(false, x, y) -> 0
   if(true, x, y) -> s(div(minus(x, y), y))

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:

   ge(0, 0) -> true [1]
   ge(s(x), 0) -> ge(x, 0) [1]
   ge(0, s(0)) -> false [1]
   ge(0, s(s(x))) -> ge(0, s(x)) [1]
   ge(s(x), s(y)) -> ge(x, y) [1]
   minus(0, 0) -> 0 [1]
   minus(0, s(x)) -> minus(0, x) [1]
   minus(s(x), 0) -> s(minus(x, 0)) [1]
   minus(s(x), s(y)) -> minus(x, y) [1]
   plus(0, 0) -> 0 [1]
   plus(0, s(x)) -> s(plus(0, x)) [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   div(x, y) -> ify(ge(y, s(0)), x, y) [1]
   ify(false, x, y) -> divByZeroError [1]
   ify(true, x, y) -> if(ge(x, y), x, y) [1]
   if(false, x, y) -> 0 [1]
   if(true, x, y) -> s(div(minus(x, y), y)) [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:

   ge(0, 0) -> true [1]
   ge(s(x), 0) -> ge(x, 0) [1]
   ge(0, s(0)) -> false [1]
   ge(0, s(s(x))) -> ge(0, s(x)) [1]
   ge(s(x), s(y)) -> ge(x, y) [1]
   minus(0, 0) -> 0 [1]
   minus(0, s(x)) -> minus(0, x) [1]
   minus(s(x), 0) -> s(minus(x, 0)) [1]
   minus(s(x), s(y)) -> minus(x, y) [1]
   plus(0, 0) -> 0 [1]
   plus(0, s(x)) -> s(plus(0, x)) [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   div(x, y) -> ify(ge(y, s(0)), x, y) [1]
   ify(false, x, y) -> divByZeroError [1]
   ify(true, x, y) -> if(ge(x, y), x, y) [1]
   if(false, x, y) -> 0 [1]
   if(true, x, y) -> s(div(minus(x, y), y)) [1]

The TRS has the following type information:
ge :: 0:s:divByZeroError -> 0:s:divByZeroError -> true:false
0 :: 0:s:divByZeroError
true :: true:false
s :: 0:s:divByZeroError -> 0:s:divByZeroError
false :: true:false
minus :: 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError
plus :: 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError
div :: 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError
ify :: true:false -> 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError
divByZeroError :: 0:s:divByZeroError
if :: true:false -> 0:s:divByZeroError -> 0:s:divByZeroError -> 0:s:divByZeroError

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:

   ge(v0, v1) -> null_ge [0]
   minus(v0, v1) -> null_minus [0]
   plus(v0, v1) -> null_plus [0]
   ify(v0, v1, v2) -> null_ify [0]
   if(v0, v1, v2) -> null_if [0]

And the following fresh constants:    null_ge, null_minus, null_plus, null_ify, null_if

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

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

   ge(0, 0) -> true [1]
   ge(s(x), 0) -> ge(x, 0) [1]
   ge(0, s(0)) -> false [1]
   ge(0, s(s(x))) -> ge(0, s(x)) [1]
   ge(s(x), s(y)) -> ge(x, y) [1]
   minus(0, 0) -> 0 [1]
   minus(0, s(x)) -> minus(0, x) [1]
   minus(s(x), 0) -> s(minus(x, 0)) [1]
   minus(s(x), s(y)) -> minus(x, y) [1]
   plus(0, 0) -> 0 [1]
   plus(0, s(x)) -> s(plus(0, x)) [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   div(x, y) -> ify(ge(y, s(0)), x, y) [1]
   ify(false, x, y) -> divByZeroError [1]
   ify(true, x, y) -> if(ge(x, y), x, y) [1]
   if(false, x, y) -> 0 [1]
   if(true, x, y) -> s(div(minus(x, y), y)) [1]
   ge(v0, v1) -> null_ge [0]
   minus(v0, v1) -> null_minus [0]
   plus(v0, v1) -> null_plus [0]
   ify(v0, v1, v2) -> null_ify [0]
   if(v0, v1, v2) -> null_if [0]

The TRS has the following type information:
ge :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> true:false:null_ge
0 :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
true :: true:false:null_ge
s :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
false :: true:false:null_ge
minus :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
plus :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
div :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
ify :: true:false:null_ge -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
divByZeroError :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
if :: true:false:null_ge -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if -> 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
null_ge :: true:false:null_ge
null_minus :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
null_plus :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
null_ify :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if
null_if :: 0:s:divByZeroError:null_minus:null_plus:null_ify:null_if

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:

   0 => 0
   true => 2
   false => 1
   divByZeroError => 1
   null_ge => 0
   null_minus => 0
   null_plus => 0
   null_ify => 0
   null_if => 0

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

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

   div(z, z') -{ 1 }-> ify(ge(y, 1 + 0), x, y) :|: x >= 0, y >= 0, z = x, z' = y
   ge(z, z') -{ 1 }-> ge(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   ge(z, z') -{ 1 }-> ge(x, 0) :|: x >= 0, z = 1 + x, z' = 0
   ge(z, z') -{ 1 }-> ge(0, 1 + x) :|: x >= 0, z = 0, z' = 1 + (1 + x)
   ge(z, z') -{ 1 }-> 2 :|: z = 0, z' = 0
   ge(z, z') -{ 1 }-> 1 :|: z' = 1 + 0, z = 0
   ge(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   if(z, z', z'') -{ 1 }-> 0 :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0
   if(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   if(z, z', z'') -{ 1 }-> 1 + div(minus(x, y), y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0
   ify(z, z', z'') -{ 1 }-> if(ge(x, y), x, y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0
   ify(z, z', z'') -{ 1 }-> 1 :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0
   ify(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   minus(z, z') -{ 1 }-> minus(0, x) :|: z' = 1 + x, x >= 0, z = 0
   minus(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   minus(z, z') -{ 1 }-> 1 + minus(x, 0) :|: x >= 0, z = 1 + x, z' = 0
   plus(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   plus(z, z') -{ 1 }-> 1 + plus(0, x) :|: z' = 1 + x, x >= 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(V1, V, V16),0,[ge(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V16),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V16),0,[plus(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V16),0,[div(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V16),0,[ify(V1, V, V16, Out)],[V1 >= 0,V >= 0,V16 >= 0]).
eq(start(V1, V, V16),0,[if(V1, V, V16, Out)],[V1 >= 0,V >= 0,V16 >= 0]).
eq(ge(V1, V, Out),1,[],[Out = 2,V1 = 0,V = 0]).
eq(ge(V1, V, Out),1,[ge(V2, 0, Ret)],[Out = Ret,V2 >= 0,V1 = 1 + V2,V = 0]).
eq(ge(V1, V, Out),1,[],[Out = 1,V = 1,V1 = 0]).
eq(ge(V1, V, Out),1,[ge(0, 1 + V3, Ret1)],[Out = Ret1,V3 >= 0,V1 = 0,V = 2 + V3]).
eq(ge(V1, V, Out),1,[ge(V4, V5, Ret2)],[Out = Ret2,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]).
eq(minus(V1, V, Out),1,[],[Out = 0,V1 = 0,V = 0]).
eq(minus(V1, V, Out),1,[minus(0, V6, Ret3)],[Out = Ret3,V = 1 + V6,V6 >= 0,V1 = 0]).
eq(minus(V1, V, Out),1,[minus(V7, 0, Ret11)],[Out = 1 + Ret11,V7 >= 0,V1 = 1 + V7,V = 0]).
eq(minus(V1, V, Out),1,[minus(V8, V9, Ret4)],[Out = Ret4,V = 1 + V9,V8 >= 0,V9 >= 0,V1 = 1 + V8]).
eq(plus(V1, V, Out),1,[],[Out = 0,V1 = 0,V = 0]).
eq(plus(V1, V, Out),1,[plus(0, V10, Ret12)],[Out = 1 + Ret12,V = 1 + V10,V10 >= 0,V1 = 0]).
eq(plus(V1, V, Out),1,[plus(V12, V11, Ret13)],[Out = 1 + Ret13,V12 >= 0,V11 >= 0,V1 = 1 + V12,V = V11]).
eq(div(V1, V, Out),1,[ge(V13, 1 + 0, Ret0),ify(Ret0, V14, V13, Ret5)],[Out = Ret5,V14 >= 0,V13 >= 0,V1 = V14,V = V13]).
eq(ify(V1, V, V16, Out),1,[],[Out = 1,V = V17,V16 = V15,V1 = 1,V17 >= 0,V15 >= 0]).
eq(ify(V1, V, V16, Out),1,[ge(V19, V18, Ret01),if(Ret01, V19, V18, Ret6)],[Out = Ret6,V1 = 2,V = V19,V16 = V18,V19 >= 0,V18 >= 0]).
eq(if(V1, V, V16, Out),1,[],[Out = 0,V = V21,V16 = V20,V1 = 1,V21 >= 0,V20 >= 0]).
eq(if(V1, V, V16, Out),1,[minus(V22, V23, Ret10),div(Ret10, V23, Ret14)],[Out = 1 + Ret14,V1 = 2,V = V22,V16 = V23,V22 >= 0,V23 >= 0]).
eq(ge(V1, V, Out),0,[],[Out = 0,V25 >= 0,V24 >= 0,V1 = V25,V = V24]).
eq(minus(V1, V, Out),0,[],[Out = 0,V27 >= 0,V26 >= 0,V1 = V27,V = V26]).
eq(plus(V1, V, Out),0,[],[Out = 0,V29 >= 0,V28 >= 0,V1 = V29,V = V28]).
eq(ify(V1, V, V16, Out),0,[],[Out = 0,V30 >= 0,V16 = V32,V31 >= 0,V1 = V30,V = V31,V32 >= 0]).
eq(if(V1, V, V16, Out),0,[],[Out = 0,V34 >= 0,V16 = V35,V33 >= 0,V1 = V34,V = V33,V35 >= 0]).
input_output_vars(ge(V1,V,Out),[V1,V],[Out]).
input_output_vars(minus(V1,V,Out),[V1,V],[Out]).
input_output_vars(plus(V1,V,Out),[V1,V],[Out]).
input_output_vars(div(V1,V,Out),[V1,V],[Out]).
input_output_vars(ify(V1,V,V16,Out),[V1,V,V16],[Out]).
input_output_vars(if(V1,V,V16,Out),[V1,V,V16],[Out]).


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

#### Computed strongly connected components 
0. recursive  : [ge/3]
1. recursive  : [minus/3]
2. recursive  : [(div)/3,if/4,ify/4]
3. recursive  : [plus/3]
4. non_recursive  : [start/3]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into ge/3
1. SCC is partially evaluated into minus/3
2. SCC is partially evaluated into (div)/3
3. SCC is partially evaluated into plus/3
4. SCC is partially evaluated into start/3

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

### Specialization of cost equations ge/3 
* CE 16 is refined into CE [31] 
* CE 13 is refined into CE [32] 
* CE 11 is refined into CE [33] 
* CE 15 is refined into CE [34] 
* CE 12 is refined into CE [35] 
* CE 14 is refined into CE [36] 


### Cost equations --> "Loop" of ge/3 
* CEs [34] --> Loop 19 
* CEs [35] --> Loop 20 
* CEs [36] --> Loop 21 
* CEs [31] --> Loop 22 
* CEs [32] --> Loop 23 
* CEs [33] --> Loop 24 

### Ranking functions of CR ge(V1,V,Out) 
* RF of phase [19]: [V,V1]
* RF of phase [20]: [V1]
* RF of phase [21]: [V-1]

#### Partial ranking functions of CR ge(V1,V,Out) 
* Partial RF of phase [19]:
  - RF of loop [19:1]:
    V
    V1
* Partial RF of phase [20]:
  - RF of loop [20:1]:
    V1
* Partial RF of phase [21]:
  - RF of loop [21:1]:
    V-1


### Specialization of cost equations minus/3 
* CE 17 is refined into CE [37] 
* CE 21 is refined into CE [38] 
* CE 20 is refined into CE [39] 
* CE 19 is refined into CE [40] 
* CE 18 is refined into CE [41] 


### Cost equations --> "Loop" of minus/3 
* CEs [39] --> Loop 25 
* CEs [40] --> Loop 26 
* CEs [41] --> Loop 27 
* CEs [37,38] --> Loop 28 

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

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


### Specialization of cost equations (div)/3 
* CE 23 is refined into CE [42] 
* CE 22 is refined into CE [43,44,45,46] 
* CE 24 is refined into CE [47,48,49,50] 
* CE 26 is refined into CE [51,52,53,54,55,56,57,58,59,60] 
* CE 25 is refined into CE [61,62,63,64,65,66] 


### Cost equations --> "Loop" of (div)/3 
* CEs [66] --> Loop 29 
* CEs [65] --> Loop 30 
* CEs [64] --> Loop 31 
* CEs [63] --> Loop 32 
* CEs [62] --> Loop 33 
* CEs [61] --> Loop 34 
* CEs [59] --> Loop 35 
* CEs [49,57] --> Loop 36 
* CEs [42] --> Loop 37 
* CEs [43] --> Loop 38 
* CEs [53] --> Loop 39 
* CEs [48,56] --> Loop 40 
* CEs [44,45,46,47,50,51,52,54,55,58,60] --> Loop 41 

### Ranking functions of CR div(V1,V,Out) 
* RF of phase [29]: [V1/2-1,V1/2-V/2]
* RF of phase [32]: [V1-1]

#### Partial ranking functions of CR div(V1,V,Out) 
* Partial RF of phase [29]:
  - RF of loop [29:1]:
    V1/2-1
    V1/2-V/2
* Partial RF of phase [32]:
  - RF of loop [32:1]:
    V1-1


### Specialization of cost equations plus/3 
* CE 27 is refined into CE [67] 
* CE 30 is refined into CE [68] 
* CE 29 is refined into CE [69] 
* CE 28 is refined into CE [70] 


### Cost equations --> "Loop" of plus/3 
* CEs [69] --> Loop 42 
* CEs [70] --> Loop 43 
* CEs [67,68] --> Loop 44 

### Ranking functions of CR plus(V1,V,Out) 
* RF of phase [42]: [V1]
* RF of phase [43]: [V]

#### Partial ranking functions of CR plus(V1,V,Out) 
* Partial RF of phase [42]:
  - RF of loop [42:1]:
    V1
* Partial RF of phase [43]:
  - RF of loop [43:1]:
    V


### Specialization of cost equations start/3 
* CE 3 is refined into CE [71,72,73,74] 
* CE 4 is refined into CE [75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96] 
* CE 5 is refined into CE [97,98,99,100,101,102,103,104,105,106] 
* CE 6 is refined into CE [107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123] 
* CE 1 is refined into CE [124] 
* CE 2 is refined into CE [125] 
* CE 7 is refined into CE [126,127,128,129,130,131,132,133,134,135] 
* CE 8 is refined into CE [136,137,138] 
* CE 9 is refined into CE [139,140,141,142] 
* CE 10 is refined into CE [143,144,145,146,147,148,149,150,151,152,153,154,155] 


### Cost equations --> "Loop" of start/3 
* CEs [132,151] --> Loop 45 
* CEs [148,149] --> Loop 46 
* CEs [84,105] --> Loop 47 
* CEs [73,103] --> Loop 48 
* CEs [87,88,89,90,114,115,116,117] --> Loop 49 
* CEs [72,100] --> Loop 50 
* CEs [71,98] --> Loop 51 
* CEs [74,75,76,77,78,79,80,81,82,83,85,86,91,92,93,94,95,96,97,99,101,102,104,106,107,108,109,110,111,112,113,118,119,120,121,122,123] --> Loop 52 
* CEs [125] --> Loop 53 
* CEs [134,144,145,150,152] --> Loop 54 
* CEs [127,129,139] --> Loop 55 
* CEs [124,126,128,130,131,133,135,136,137,138,140,141,142,143,146,147,153,154,155] --> Loop 56 

### Ranking functions of CR start(V1,V,V16) 

#### Partial ranking functions of CR start(V1,V,V16) 


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

#### Cost of chains of ge(V1,V,Out):
* Chain [[21],23]: 1*it(21)+1
  Such that:it(21) =< V

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

* Chain [[21],22]: 1*it(21)+0
  Such that:it(21) =< V

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

* Chain [[20],24]: 1*it(20)+1
  Such that:it(20) =< V1

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

* Chain [[20],22]: 1*it(20)+0
  Such that:it(20) =< V1

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

* Chain [[19],[21],23]: 1*it(19)+1*it(21)+1
  Such that:it(21) =< -V1+V
it(19) =< V1

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

* Chain [[19],[21],22]: 1*it(19)+1*it(21)+0
  Such that:it(21) =< -V1+V
it(19) =< V1

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

* Chain [[19],[20],24]: 1*it(19)+1*it(20)+1
  Such that:it(20) =< V1-V
it(19) =< V

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

* Chain [[19],[20],22]: 1*it(19)+1*it(20)+0
  Such that:it(20) =< V1-V
it(19) =< V

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

* Chain [[19],24]: 1*it(19)+1
  Such that:it(19) =< V1

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

* Chain [[19],23]: 1*it(19)+1
  Such that:it(19) =< V1

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

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

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

* Chain [24]: 1
  with precondition: [V1=0,V=0,Out=2] 

* Chain [23]: 1
  with precondition: [V1=0,V=1,Out=1] 

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


#### Cost of chains of minus(V1,V,Out):
* Chain [[27],28]: 1*it(27)+1
  Such that:it(27) =< V

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

* Chain [[26],28]: 1*it(26)+1
  Such that:it(26) =< Out

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

* Chain [[25],[27],28]: 1*it(25)+1*it(27)+1
  Such that:it(27) =< -V1+V
it(25) =< V1

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

* Chain [[25],[26],28]: 1*it(25)+1*it(26)+1
  Such that:it(25) =< V
it(26) =< Out

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

* Chain [[25],28]: 1*it(25)+1
  Such that:it(25) =< V

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

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


#### Cost of chains of div(V1,V,Out):
* Chain [[32],41]: 17*it(32)+28*s(12)+1*s(59)+1*s(60)+5
  Such that:aux(21) =< 1
aux(22) =< V1
s(12) =< aux(21)
it(32) =< aux(22)
aux(17) =< aux(22)-1
s(59) =< it(32)*aux(22)
s(60) =< it(32)*aux(17)

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

* Chain [[32],39]: 9*it(32)+1*s(59)+1*s(60)+2*s(62)+4
  Such that:aux(23) =< 1
aux(24) =< V1
s(62) =< aux(23)
it(32) =< aux(24)
aux(17) =< aux(24)-1
s(59) =< it(32)*aux(24)
s(60) =< it(32)*aux(17)

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

* Chain [[32],34,41]: 9*it(32)+37*s(12)+1*s(59)+1*s(60)+11
  Such that:aux(27) =< 1
aux(28) =< V1
s(12) =< aux(27)
it(32) =< aux(28)
aux(17) =< aux(28)-1
s(59) =< it(32)*aux(28)
s(60) =< it(32)*aux(17)

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

* Chain [[32],33,41]: 11*it(32)+36*s(12)+1*s(59)+1*s(60)+11
  Such that:aux(32) =< 1
aux(33) =< V1
s(12) =< aux(32)
it(32) =< aux(33)
aux(17) =< aux(33)-1
s(59) =< it(32)*aux(33)
s(60) =< it(32)*aux(17)

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

* Chain [[29],41]: 6*it(29)+1*s(11)+14*s(12)+17*s(15)+9*s(23)+2*s(38)+1*s(89)+1*s(90)+1*s(91)+5
  Such that:aux(9) =< 1
aux(12) =< V1-2*V-2*Out+2
aux(36) =< V1-V
aux(38) =< V1/2
aux(39) =< V1/2-V/2
s(11) =< -V+1
aux(42) =< V1
aux(43) =< V
s(15) =< aux(9)
s(12) =< aux(43)
s(23) =< aux(42)
s(38) =< aux(12)
aux(35) =< aux(38)
it(29) =< aux(38)
aux(35) =< aux(39)
it(29) =< aux(39)
aux(35) =< aux(42)
it(29) =< aux(42)
aux(37) =< aux(36)
s(90) =< it(29)*aux(36)
s(89) =< aux(35)
s(91) =< it(29)*aux(37)

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

* Chain [[29],36]: 6*it(29)+3*s(88)+1*s(89)+1*s(90)+1*s(91)+4*s(93)+2*s(94)+5
  Such that:aux(46) =< 1
aux(36) =< V1-V
s(92) =< V1-V+1
aux(38) =< V1/2
aux(39) =< V1/2-V/2
aux(47) =< V
aux(48) =< V1/2-V/2+1/2
s(94) =< aux(46)
s(93) =< aux(47)
aux(35) =< aux(38)
it(29) =< aux(38)
aux(35) =< aux(39)
it(29) =< aux(39)
aux(35) =< aux(48)
it(29) =< aux(48)
aux(37) =< aux(36)
s(90) =< it(29)*aux(36)
s(89) =< aux(35)
s(91) =< it(29)*aux(37)
s(88) =< s(92)

  with precondition: [V>=2,Out>=1,V1+3>=2*Out+2*V] 

* Chain [[29],35]: 6*it(29)+3*s(88)+1*s(89)+1*s(90)+1*s(91)+2*s(99)+1*s(100)+4
  Such that:s(100) =< 1
aux(38) =< V1/2
aux(49) =< V
aux(50) =< V1-V
aux(51) =< V1/2-V/2
s(99) =< aux(49)
aux(35) =< aux(38)
it(29) =< aux(38)
aux(35) =< aux(51)
it(29) =< aux(51)
aux(37) =< aux(50)
s(90) =< it(29)*aux(50)
s(89) =< aux(35)
s(91) =< it(29)*aux(37)
s(88) =< aux(50)

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

* Chain [[29],31,41]: 6*it(29)+1*s(11)+19*s(12)+19*s(15)+2*s(38)+3*s(88)+1*s(89)+1*s(90)+1*s(91)+11
  Such that:aux(53) =< 1
aux(38) =< V1/2
aux(12) =< -V
s(11) =< -V+1
aux(54) =< V
aux(55) =< V1-V
aux(56) =< V1/2-V/2
s(15) =< aux(53)
s(12) =< aux(54)
s(38) =< aux(12)
aux(35) =< aux(38)
it(29) =< aux(38)
aux(35) =< aux(56)
it(29) =< aux(56)
aux(37) =< aux(55)
s(90) =< it(29)*aux(55)
s(89) =< aux(35)
s(91) =< it(29)*aux(37)
s(88) =< aux(55)

  with precondition: [V>=2,Out>=2,V1+4>=2*Out+2*V] 

* Chain [[29],31,40]: 6*it(29)+3*s(88)+1*s(89)+1*s(90)+1*s(91)+9*s(102)+3*s(103)+11
  Such that:aux(61) =< 1
aux(38) =< V1/2
aux(62) =< V
aux(63) =< V1-V
aux(64) =< V1/2-V/2
s(103) =< aux(61)
s(102) =< aux(62)
aux(35) =< aux(38)
it(29) =< aux(38)
aux(35) =< aux(64)
it(29) =< aux(64)
aux(37) =< aux(63)
s(90) =< it(29)*aux(63)
s(89) =< aux(35)
s(91) =< it(29)*aux(37)
s(88) =< aux(63)

  with precondition: [V>=2,Out>=2,V1+4>=2*Out+2*V] 

* Chain [[29],30,41]: 6*it(29)+1*s(11)+18*s(12)+19*s(15)+2*s(38)+4*s(88)+1*s(89)+1*s(90)+1*s(91)+1*s(117)+11
  Such that:aux(66) =< 1
aux(38) =< V1/2
aux(39) =< V1/2-V/2
aux(12) =< -V
s(11) =< -V+1
aux(67) =< V
aux(68) =< V1
aux(69) =< V1-V
s(88) =< aux(68)
s(117) =< aux(69)
s(15) =< aux(66)
s(12) =< aux(67)
s(38) =< aux(12)
aux(35) =< aux(38)
it(29) =< aux(38)
aux(35) =< aux(39)
it(29) =< aux(39)
aux(35) =< aux(68)
it(29) =< aux(68)
aux(37) =< aux(69)
s(90) =< it(29)*aux(69)
s(89) =< aux(35)
s(91) =< it(29)*aux(37)

  with precondition: [V>=2,Out>=2,V1+3>=2*Out+2*V] 

* Chain [[29],30,40]: 6*it(29)+4*s(88)+1*s(89)+1*s(90)+1*s(91)+8*s(109)+3*s(110)+1*s(117)+11
  Such that:aux(70) =< 1
aux(38) =< V1/2
aux(39) =< V1/2-V/2
aux(71) =< V
aux(72) =< V1
aux(73) =< V1-V
s(88) =< aux(72)
s(117) =< aux(73)
s(110) =< aux(70)
s(109) =< aux(71)
aux(35) =< aux(38)
it(29) =< aux(38)
aux(35) =< aux(39)
it(29) =< aux(39)
aux(35) =< aux(72)
it(29) =< aux(72)
aux(37) =< aux(73)
s(90) =< it(29)*aux(73)
s(89) =< aux(35)
s(91) =< it(29)*aux(37)

  with precondition: [V>=2,Out>=2,V1+3>=2*Out+2*V] 

* Chain [41]: 1*s(11)+11*s(12)+17*s(15)+3*s(22)+6*s(23)+1*s(26)+2*s(38)+5
  Such that:s(26) =< -V1+1
s(11) =< -V+1
aux(9) =< 1
aux(10) =< -V1+V
aux(11) =< V1
aux(12) =< V1-V
aux(13) =< V
s(15) =< aux(9)
s(22) =< aux(10)
s(23) =< aux(11)
s(38) =< aux(12)
s(12) =< aux(13)

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

* Chain [40]: 4*s(109)+2*s(110)+5
  Such that:aux(59) =< 1
aux(60) =< V
s(110) =< aux(59)
s(109) =< aux(60)

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

* Chain [39]: 2*s(62)+4
  Such that:aux(23) =< 1
s(62) =< aux(23)

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

* Chain [38]: 2
  with precondition: [V=0,Out=0,V1>=0] 

* Chain [37]: 3
  with precondition: [V=0,Out=1,V1>=0] 

* Chain [36]: 4*s(93)+2*s(94)+5
  Such that:aux(46) =< 1
aux(47) =< V
s(94) =< aux(46)
s(93) =< aux(47)

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

* Chain [35]: 2*s(99)+1*s(100)+4
  Such that:s(100) =< 1
aux(49) =< V
s(99) =< aux(49)

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

* Chain [34,41]: 37*s(12)+11
  Such that:aux(27) =< 1
s(12) =< aux(27)

  with precondition: [V1=1,V=1,Out=1] 

* Chain [33,41]: 36*s(12)+2*s(71)+1*s(73)+11
  Such that:s(73) =< -V1+1
aux(30) =< V1
aux(32) =< 1
s(12) =< aux(32)
s(71) =< aux(30)

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

* Chain [31,41]: 1*s(11)+19*s(12)+19*s(15)+2*s(38)+11
  Such that:aux(12) =< -V1
s(11) =< -V1+1
aux(53) =< 1
aux(54) =< V1
s(15) =< aux(53)
s(12) =< aux(54)
s(38) =< aux(12)

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

* Chain [31,40]: 9*s(102)+3*s(103)+11
  Such that:aux(61) =< 1
aux(62) =< V1
s(103) =< aux(61)
s(102) =< aux(62)

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

* Chain [30,41]: 1*s(11)+18*s(12)+19*s(15)+2*s(38)+1*s(117)+1*s(119)+1*s(120)+11
  Such that:s(119) =< -V1+V
s(120) =< V1
s(117) =< V1-V
aux(12) =< -V
s(11) =< -V+1
aux(66) =< 1
aux(67) =< V
s(15) =< aux(66)
s(12) =< aux(67)
s(38) =< aux(12)

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

* Chain [30,40]: 8*s(109)+3*s(110)+1*s(117)+1*s(119)+1*s(120)+11
  Such that:s(119) =< -V1+V
s(120) =< V1
s(117) =< V1-V
aux(70) =< 1
aux(71) =< V
s(110) =< aux(70)
s(109) =< aux(71)

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


#### Cost of chains of plus(V1,V,Out):
* Chain [[43],44]: 1*it(43)+1
  Such that:it(43) =< Out

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

* Chain [[42],[43],44]: 1*it(42)+1*it(43)+1
  Such that:it(43) =< -V1+Out
it(42) =< V1

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

* Chain [[42],44]: 1*it(42)+1
  Such that:it(42) =< Out

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

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


#### Cost of chains of start(V1,V,V16):
* Chain [56]: 8*s(306)+33*s(307)+18*s(308)+123*s(310)+1*s(327)+5*s(331)+105*s(334)+18*s(356)+3*s(358)+3*s(359)+3*s(360)+6*s(361)+2*s(362)+18*s(373)+3*s(375)+3*s(376)+3*s(377)+6*s(380)+1*s(381)+1*s(382)+1*s(383)+3*s(384)+11
  Such that:s(327) =< -V1+1
s(339) =< V1-2*V
s(363) =< V1-V+1
s(364) =< V1/2-V/2+1/2
aux(99) =< 1
aux(100) =< -V1+V
aux(101) =< V1
aux(102) =< V1-V
aux(103) =< V1/2
aux(104) =< V1/2-V/2
aux(105) =< -V
aux(106) =< -V+1
aux(107) =< V
s(306) =< aux(100)
s(307) =< aux(101)
s(308) =< aux(102)
s(331) =< aux(106)
s(310) =< aux(107)
s(334) =< aux(99)
s(355) =< aux(103)
s(356) =< aux(103)
s(355) =< aux(104)
s(356) =< aux(104)
s(355) =< aux(101)
s(356) =< aux(101)
s(357) =< aux(102)
s(358) =< s(356)*aux(102)
s(359) =< s(355)
s(360) =< s(356)*s(357)
s(361) =< aux(105)
s(362) =< s(339)
s(372) =< aux(103)
s(373) =< aux(103)
s(372) =< aux(104)
s(373) =< aux(104)
s(375) =< s(373)*aux(102)
s(376) =< s(372)
s(377) =< s(373)*s(357)
s(379) =< aux(103)
s(380) =< aux(103)
s(379) =< aux(104)
s(380) =< aux(104)
s(379) =< s(364)
s(380) =< s(364)
s(381) =< s(380)*aux(102)
s(382) =< s(379)
s(383) =< s(380)*s(357)
s(384) =< s(363)

  with precondition: [V1>=0,V>=0] 

* Chain [55]: 2*s(402)+1
  Such that:aux(108) =< V
s(402) =< aux(108)

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

* Chain [54]: 31*s(404)+62*s(406)+1*s(413)+2*s(418)+11
  Such that:s(412) =< -V
s(413) =< -V+1
aux(109) =< 1
aux(110) =< V
s(406) =< aux(109)
s(404) =< aux(110)
s(418) =< s(412)

  with precondition: [V1=V,V1>=1] 

* Chain [53]: 1
  with precondition: [V1=1,V>=0,V16>=0] 

* Chain [52]: 5*s(419)+40*s(420)+382*s(425)+5*s(446)+68*s(490)+376*s(491)+14*s(500)+20*s(507)+30*s(523)+36*s(571)+6*s(573)+6*s(574)+6*s(575)+4*s(577)+36*s(592)+6*s(594)+6*s(595)+6*s(596)+12*s(599)+2*s(600)+2*s(601)+2*s(602)+6*s(603)+15
  Such that:aux(152) =< 1
aux(153) =< -V
aux(154) =< -V+V16
aux(155) =< V
aux(156) =< V-3*V16
aux(157) =< V-2*V16
aux(158) =< V-2*V16+1
aux(159) =< V-V16
aux(160) =< V/2-V16
aux(161) =< V/2-V16+1/2
aux(162) =< V/2-V16/2
aux(163) =< -V16
aux(164) =< -V16+1
aux(165) =< V16
s(425) =< aux(152)
s(446) =< aux(153)
s(419) =< aux(154)
s(420) =< aux(155)
s(490) =< aux(159)
s(500) =< aux(164)
s(491) =< aux(165)
s(523) =< aux(157)
s(507) =< aux(163)
s(570) =< aux(162)
s(571) =< aux(162)
s(570) =< aux(160)
s(571) =< aux(160)
s(570) =< aux(159)
s(571) =< aux(159)
s(572) =< aux(157)
s(573) =< s(571)*aux(157)
s(574) =< s(570)
s(575) =< s(571)*s(572)
s(577) =< aux(156)
s(591) =< aux(162)
s(592) =< aux(162)
s(591) =< aux(160)
s(592) =< aux(160)
s(594) =< s(592)*aux(157)
s(595) =< s(591)
s(596) =< s(592)*s(572)
s(598) =< aux(162)
s(599) =< aux(162)
s(598) =< aux(160)
s(599) =< aux(160)
s(598) =< aux(161)
s(599) =< aux(161)
s(600) =< s(599)*aux(157)
s(601) =< s(598)
s(602) =< s(599)*s(572)
s(603) =< aux(158)

  with precondition: [V1=2,V>=0,V16>=0] 

* Chain [51]: 3
  with precondition: [V1=2,V=0,V16=1] 

* Chain [50]: 2*s(778)+3
  Such that:aux(166) =< V16
s(778) =< aux(166)

  with precondition: [V1=2,V=0,V16>=2] 

* Chain [49]: 104*s(780)+372*s(781)+8*s(802)+8*s(803)+15
  Such that:aux(179) =< 1
aux(180) =< V
s(780) =< aux(180)
s(781) =< aux(179)
s(801) =< aux(180)-1
s(802) =< s(780)*aux(180)
s(803) =< s(780)*s(801)

  with precondition: [V1=2,V16=1,V>=2] 

* Chain [48]: 2*s(842)+3
  Such that:aux(181) =< V16
s(842) =< aux(181)

  with precondition: [V1=2,V+1=V16,V>=1] 

* Chain [47]: 23*s(844)+20*s(849)+1*s(853)+2*s(860)+9
  Such that:aux(183) =< 1
s(852) =< -V16
s(853) =< -V16+1
aux(185) =< V16
s(844) =< aux(185)
s(849) =< aux(183)
s(860) =< s(852)

  with precondition: [V1=2,V=V16,V>=1] 

* Chain [46]: 1*s(862)+139*s(865)+48*s(866)+4*s(868)+4*s(869)+11
  Such that:s(862) =< -V1+1
aux(186) =< 1
aux(187) =< V1
s(865) =< aux(186)
s(866) =< aux(187)
s(867) =< aux(187)-1
s(868) =< s(866)*aux(187)
s(869) =< s(866)*s(867)

  with precondition: [V=1,V1>=2] 

* Chain [45]: 5*s(877)+2*s(880)+5
  Such that:s(878) =< 1
aux(188) =< V
s(877) =< aux(188)
s(880) =< s(878)

  with precondition: [V1+1=V,V1>=1] 


Closed-form bounds of start(V1,V,V16): 
-------------------------------------
* Chain [56] with precondition: [V1>=0,V>=0] 
    - Upper bound: 33*V1+123*V+116+nat(-V1+V)*8+nat(-V1+1)+nat(-V+1)*5+nat(V1-V+1)*3+nat(V1-V)*18+V1/2*(nat(V1-V)*14)+nat(V1-2*V)*2+49/2*V1 
    - Complexity: n^2 
* Chain [55] with precondition: [V1=0,V>=1] 
    - Upper bound: 2*V+1 
    - Complexity: n 
* Chain [54] with precondition: [V1=V,V1>=1] 
    - Upper bound: 31*V+73 
    - Complexity: n 
* Chain [53] with precondition: [V1=1,V>=0,V16>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [52] with precondition: [V1=2,V>=0,V16>=0] 
    - Upper bound: 40*V+376*V16+397+nat(-V+V16)*5+nat(-V16+1)*14+nat(V-2*V16+1)*6+nat(V-V16)*68+nat(V-2*V16)*30+nat(V-2*V16)*28*nat(V/2-V16/2)+nat(V-3*V16)*4+nat(V/2-V16/2)*98 
    - Complexity: n^2 
* Chain [51] with precondition: [V1=2,V=0,V16=1] 
    - Upper bound: 3 
    - Complexity: constant 
* Chain [50] with precondition: [V1=2,V=0,V16>=2] 
    - Upper bound: 2*V16+3 
    - Complexity: n 
* Chain [49] with precondition: [V1=2,V16=1,V>=2] 
    - Upper bound: 104*V+387+8*V*V+(V-1)*(8*V) 
    - Complexity: n^2 
* Chain [48] with precondition: [V1=2,V+1=V16,V>=1] 
    - Upper bound: 2*V16+3 
    - Complexity: n 
* Chain [47] with precondition: [V1=2,V=V16,V>=1] 
    - Upper bound: 23*V16+29 
    - Complexity: n 
* Chain [46] with precondition: [V=1,V1>=2] 
    - Upper bound: 48*V1+150+4*V1*V1+(V1-1)*(4*V1) 
    - Complexity: n^2 
* Chain [45] with precondition: [V1+1=V,V1>=1] 
    - Upper bound: 5*V+7 
    - Complexity: n 

### Maximum cost of start(V1,V,V16): max([max([max([2,48*V1+149+4*V1*V1+4*V1*nat(V1-1)]),nat(V16)*21+26+(nat(V16)*2+2)]),9*V+43+max([64*V+max([8*V*V+271+8*V*nat(V-1),33*V1+19*V+nat(-V1+V)*8+nat(-V1+1)+nat(-V+1)*5+nat(V1-V+1)*3+nat(V1-V)*18+V1/2*(nat(V1-V)*14)+nat(V1-2*V)*2+49/2*V1]),nat(V16)*376+281+nat(-V+V16)*5+nat(-V16+1)*14+nat(V-2*V16+1)*6+nat(V-V16)*68+nat(V-2*V16)*30+nat(V-2*V16)*28*nat(V/2-V16/2)+nat(V-3*V16)*4+nat(V/2-V16/2)*98])+(26*V+66)+(3*V+6)+2*V])+1 
Asymptotic class: n^2 
* Total analysis performed in 1628 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^1, INF).


The TRS R consists of the following rules:

   ge(0', 0') -> true
   ge(s(x), 0') -> ge(x, 0')
   ge(0', s(0')) -> false
   ge(0', s(s(x))) -> ge(0', s(x))
   ge(s(x), s(y)) -> ge(x, y)
   minus(0', 0') -> 0'
   minus(0', s(x)) -> minus(0', x)
   minus(s(x), 0') -> s(minus(x, 0'))
   minus(s(x), s(y)) -> minus(x, y)
   plus(0', 0') -> 0'
   plus(0', s(x)) -> s(plus(0', x))
   plus(s(x), y) -> s(plus(x, y))
   div(x, y) -> ify(ge(y, s(0')), x, y)
   ify(false, x, y) -> divByZeroError
   ify(true, x, y) -> if(ge(x, y), x, y)
   if(false, x, y) -> 0'
   if(true, x, y) -> s(div(minus(x, y), y))

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

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

(14)
Obligation:
Innermost TRS:
Rules:
ge(0', 0') -> true
ge(s(x), 0') -> ge(x, 0')
ge(0', s(0')) -> false
ge(0', s(s(x))) -> ge(0', s(x))
ge(s(x), s(y)) -> ge(x, y)
minus(0', 0') -> 0'
minus(0', s(x)) -> minus(0', x)
minus(s(x), 0') -> s(minus(x, 0'))
minus(s(x), s(y)) -> minus(x, y)
plus(0', 0') -> 0'
plus(0', s(x)) -> s(plus(0', x))
plus(s(x), y) -> s(plus(x, y))
div(x, y) -> ify(ge(y, s(0')), x, y)
ify(false, x, y) -> divByZeroError
ify(true, x, y) -> if(ge(x, y), x, y)
if(false, x, y) -> 0'
if(true, x, y) -> s(div(minus(x, y), y))

Types:
ge :: 0':s:divByZeroError -> 0':s:divByZeroError -> true:false
0' :: 0':s:divByZeroError
true :: true:false
s :: 0':s:divByZeroError -> 0':s:divByZeroError
false :: true:false
minus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
plus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
div :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
ify :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
divByZeroError :: 0':s:divByZeroError
if :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
hole_true:false1_0 :: true:false
hole_0':s:divByZeroError2_0 :: 0':s:divByZeroError
gen_0':s:divByZeroError3_0 :: Nat -> 0':s:divByZeroError

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

(15) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
ge, minus, plus, div

They will be analysed ascendingly in the following order:
ge < div
minus < div

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

(16)
Obligation:
Innermost TRS:
Rules:
ge(0', 0') -> true
ge(s(x), 0') -> ge(x, 0')
ge(0', s(0')) -> false
ge(0', s(s(x))) -> ge(0', s(x))
ge(s(x), s(y)) -> ge(x, y)
minus(0', 0') -> 0'
minus(0', s(x)) -> minus(0', x)
minus(s(x), 0') -> s(minus(x, 0'))
minus(s(x), s(y)) -> minus(x, y)
plus(0', 0') -> 0'
plus(0', s(x)) -> s(plus(0', x))
plus(s(x), y) -> s(plus(x, y))
div(x, y) -> ify(ge(y, s(0')), x, y)
ify(false, x, y) -> divByZeroError
ify(true, x, y) -> if(ge(x, y), x, y)
if(false, x, y) -> 0'
if(true, x, y) -> s(div(minus(x, y), y))

Types:
ge :: 0':s:divByZeroError -> 0':s:divByZeroError -> true:false
0' :: 0':s:divByZeroError
true :: true:false
s :: 0':s:divByZeroError -> 0':s:divByZeroError
false :: true:false
minus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
plus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
div :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
ify :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
divByZeroError :: 0':s:divByZeroError
if :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
hole_true:false1_0 :: true:false
hole_0':s:divByZeroError2_0 :: 0':s:divByZeroError
gen_0':s:divByZeroError3_0 :: Nat -> 0':s:divByZeroError


Generator Equations:
gen_0':s:divByZeroError3_0(0) <=> 0'
gen_0':s:divByZeroError3_0(+(x, 1)) <=> s(gen_0':s:divByZeroError3_0(x))


The following defined symbols remain to be analysed:
ge, minus, plus, div

They will be analysed ascendingly in the following order:
ge < div
minus < div

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
ge(gen_0':s:divByZeroError3_0(n5_0), gen_0':s:divByZeroError3_0(0)) -> true, rt in Omega(1 + n5_0)

Induction Base:
ge(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(0)) ->_R^Omega(1)
true

Induction Step:
ge(gen_0':s:divByZeroError3_0(+(n5_0, 1)), gen_0':s:divByZeroError3_0(0)) ->_R^Omega(1)
ge(gen_0':s:divByZeroError3_0(n5_0), 0') ->_IH
true

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:
ge(0', 0') -> true
ge(s(x), 0') -> ge(x, 0')
ge(0', s(0')) -> false
ge(0', s(s(x))) -> ge(0', s(x))
ge(s(x), s(y)) -> ge(x, y)
minus(0', 0') -> 0'
minus(0', s(x)) -> minus(0', x)
minus(s(x), 0') -> s(minus(x, 0'))
minus(s(x), s(y)) -> minus(x, y)
plus(0', 0') -> 0'
plus(0', s(x)) -> s(plus(0', x))
plus(s(x), y) -> s(plus(x, y))
div(x, y) -> ify(ge(y, s(0')), x, y)
ify(false, x, y) -> divByZeroError
ify(true, x, y) -> if(ge(x, y), x, y)
if(false, x, y) -> 0'
if(true, x, y) -> s(div(minus(x, y), y))

Types:
ge :: 0':s:divByZeroError -> 0':s:divByZeroError -> true:false
0' :: 0':s:divByZeroError
true :: true:false
s :: 0':s:divByZeroError -> 0':s:divByZeroError
false :: true:false
minus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
plus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
div :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
ify :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
divByZeroError :: 0':s:divByZeroError
if :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
hole_true:false1_0 :: true:false
hole_0':s:divByZeroError2_0 :: 0':s:divByZeroError
gen_0':s:divByZeroError3_0 :: Nat -> 0':s:divByZeroError


Generator Equations:
gen_0':s:divByZeroError3_0(0) <=> 0'
gen_0':s:divByZeroError3_0(+(x, 1)) <=> s(gen_0':s:divByZeroError3_0(x))


The following defined symbols remain to be analysed:
ge, minus, plus, div

They will be analysed ascendingly in the following order:
ge < div
minus < div

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

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

(21)
BOUNDS(n^1, INF)

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

(22)
Obligation:
Innermost TRS:
Rules:
ge(0', 0') -> true
ge(s(x), 0') -> ge(x, 0')
ge(0', s(0')) -> false
ge(0', s(s(x))) -> ge(0', s(x))
ge(s(x), s(y)) -> ge(x, y)
minus(0', 0') -> 0'
minus(0', s(x)) -> minus(0', x)
minus(s(x), 0') -> s(minus(x, 0'))
minus(s(x), s(y)) -> minus(x, y)
plus(0', 0') -> 0'
plus(0', s(x)) -> s(plus(0', x))
plus(s(x), y) -> s(plus(x, y))
div(x, y) -> ify(ge(y, s(0')), x, y)
ify(false, x, y) -> divByZeroError
ify(true, x, y) -> if(ge(x, y), x, y)
if(false, x, y) -> 0'
if(true, x, y) -> s(div(minus(x, y), y))

Types:
ge :: 0':s:divByZeroError -> 0':s:divByZeroError -> true:false
0' :: 0':s:divByZeroError
true :: true:false
s :: 0':s:divByZeroError -> 0':s:divByZeroError
false :: true:false
minus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
plus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
div :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
ify :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
divByZeroError :: 0':s:divByZeroError
if :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
hole_true:false1_0 :: true:false
hole_0':s:divByZeroError2_0 :: 0':s:divByZeroError
gen_0':s:divByZeroError3_0 :: Nat -> 0':s:divByZeroError


Lemmas:
ge(gen_0':s:divByZeroError3_0(n5_0), gen_0':s:divByZeroError3_0(0)) -> true, rt in Omega(1 + n5_0)


Generator Equations:
gen_0':s:divByZeroError3_0(0) <=> 0'
gen_0':s:divByZeroError3_0(+(x, 1)) <=> s(gen_0':s:divByZeroError3_0(x))


The following defined symbols remain to be analysed:
minus, plus, div

They will be analysed ascendingly in the following order:
minus < div

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

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
minus(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(n6998_0)) -> gen_0':s:divByZeroError3_0(0), rt in Omega(1 + n6998_0)

Induction Base:
minus(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(0)) ->_R^Omega(1)
0'

Induction Step:
minus(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(+(n6998_0, 1))) ->_R^Omega(1)
minus(0', gen_0':s:divByZeroError3_0(n6998_0)) ->_IH
gen_0':s:divByZeroError3_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:
ge(0', 0') -> true
ge(s(x), 0') -> ge(x, 0')
ge(0', s(0')) -> false
ge(0', s(s(x))) -> ge(0', s(x))
ge(s(x), s(y)) -> ge(x, y)
minus(0', 0') -> 0'
minus(0', s(x)) -> minus(0', x)
minus(s(x), 0') -> s(minus(x, 0'))
minus(s(x), s(y)) -> minus(x, y)
plus(0', 0') -> 0'
plus(0', s(x)) -> s(plus(0', x))
plus(s(x), y) -> s(plus(x, y))
div(x, y) -> ify(ge(y, s(0')), x, y)
ify(false, x, y) -> divByZeroError
ify(true, x, y) -> if(ge(x, y), x, y)
if(false, x, y) -> 0'
if(true, x, y) -> s(div(minus(x, y), y))

Types:
ge :: 0':s:divByZeroError -> 0':s:divByZeroError -> true:false
0' :: 0':s:divByZeroError
true :: true:false
s :: 0':s:divByZeroError -> 0':s:divByZeroError
false :: true:false
minus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
plus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
div :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
ify :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
divByZeroError :: 0':s:divByZeroError
if :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
hole_true:false1_0 :: true:false
hole_0':s:divByZeroError2_0 :: 0':s:divByZeroError
gen_0':s:divByZeroError3_0 :: Nat -> 0':s:divByZeroError


Lemmas:
ge(gen_0':s:divByZeroError3_0(n5_0), gen_0':s:divByZeroError3_0(0)) -> true, rt in Omega(1 + n5_0)
minus(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(n6998_0)) -> gen_0':s:divByZeroError3_0(0), rt in Omega(1 + n6998_0)


Generator Equations:
gen_0':s:divByZeroError3_0(0) <=> 0'
gen_0':s:divByZeroError3_0(+(x, 1)) <=> s(gen_0':s:divByZeroError3_0(x))


The following defined symbols remain to be analysed:
plus, div
----------------------------------------

(25) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
plus(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(n10341_0)) -> gen_0':s:divByZeroError3_0(n10341_0), rt in Omega(1 + n10341_0)

Induction Base:
plus(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(0)) ->_R^Omega(1)
0'

Induction Step:
plus(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(+(n10341_0, 1))) ->_R^Omega(1)
s(plus(0', gen_0':s:divByZeroError3_0(n10341_0))) ->_IH
s(gen_0':s:divByZeroError3_0(c10342_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:
ge(0', 0') -> true
ge(s(x), 0') -> ge(x, 0')
ge(0', s(0')) -> false
ge(0', s(s(x))) -> ge(0', s(x))
ge(s(x), s(y)) -> ge(x, y)
minus(0', 0') -> 0'
minus(0', s(x)) -> minus(0', x)
minus(s(x), 0') -> s(minus(x, 0'))
minus(s(x), s(y)) -> minus(x, y)
plus(0', 0') -> 0'
plus(0', s(x)) -> s(plus(0', x))
plus(s(x), y) -> s(plus(x, y))
div(x, y) -> ify(ge(y, s(0')), x, y)
ify(false, x, y) -> divByZeroError
ify(true, x, y) -> if(ge(x, y), x, y)
if(false, x, y) -> 0'
if(true, x, y) -> s(div(minus(x, y), y))

Types:
ge :: 0':s:divByZeroError -> 0':s:divByZeroError -> true:false
0' :: 0':s:divByZeroError
true :: true:false
s :: 0':s:divByZeroError -> 0':s:divByZeroError
false :: true:false
minus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
plus :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
div :: 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
ify :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
divByZeroError :: 0':s:divByZeroError
if :: true:false -> 0':s:divByZeroError -> 0':s:divByZeroError -> 0':s:divByZeroError
hole_true:false1_0 :: true:false
hole_0':s:divByZeroError2_0 :: 0':s:divByZeroError
gen_0':s:divByZeroError3_0 :: Nat -> 0':s:divByZeroError


Lemmas:
ge(gen_0':s:divByZeroError3_0(n5_0), gen_0':s:divByZeroError3_0(0)) -> true, rt in Omega(1 + n5_0)
minus(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(n6998_0)) -> gen_0':s:divByZeroError3_0(0), rt in Omega(1 + n6998_0)
plus(gen_0':s:divByZeroError3_0(0), gen_0':s:divByZeroError3_0(n10341_0)) -> gen_0':s:divByZeroError3_0(n10341_0), rt in Omega(1 + n10341_0)


Generator Equations:
gen_0':s:divByZeroError3_0(0) <=> 0'
gen_0':s:divByZeroError3_0(+(x, 1)) <=> s(gen_0':s:divByZeroError3_0(x))


The following defined symbols remain to be analysed:
div