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


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


WORST_CASE(?, O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(1, n^2).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 142 ms]
(4) CpxRelTRS
(5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
(6) CpxRelTRS
(7) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
(8) CpxRelTRS
(9) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(10) CpxWeightedTrs
(11) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(12) CpxWeightedTrs
(13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(14) CpxTypedWeightedTrs
(15) CompletionProof [UPPER BOUND(ID), 0 ms]
(16) CpxTypedWeightedCompleteTrs
(17) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
(18) CpxRNTS
(19) CompleteCoflocoProof [FINISHED, 644 ms]
(20) BOUNDS(1, n^2)


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

(0)
Obligation:
The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   *(i(x), x) -> 1
   *(1, y) -> y
   *(x, 0) -> 0
   *(*(x, y), z) -> *(x, *(y, z))

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

(1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID))
The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem:

   encArg(i(x_1)) -> i(encArg(x_1))
   encArg(1) -> 1
   encArg(0) -> 0
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   encode_i(x_1) -> i(encArg(x_1))
   encode_1 -> 1
   encode_0 -> 0


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

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


The TRS R consists of the following rules:

   *(i(x), x) -> 1
   *(1, y) -> y
   *(x, 0) -> 0
   *(*(x, y), z) -> *(x, *(y, z))

The (relative) TRS S consists of the following rules:

   encArg(i(x_1)) -> i(encArg(x_1))
   encArg(1) -> 1
   encArg(0) -> 0
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   encode_i(x_1) -> i(encArg(x_1))
   encode_1 -> 1
   encode_0 -> 0

Rewrite Strategy: FULL
----------------------------------------

(3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

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


The TRS R consists of the following rules:

   *(i(x), x) -> 1
   *(1, y) -> y
   *(x, 0) -> 0
   *(*(x, y), z) -> *(x, *(y, z))

The (relative) TRS S consists of the following rules:

   encArg(i(x_1)) -> i(encArg(x_1))
   encArg(1) -> 1
   encArg(0) -> 0
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   encode_i(x_1) -> i(encArg(x_1))
   encode_1 -> 1
   encode_0 -> 0

Rewrite Strategy: FULL
----------------------------------------

(5) NonCtorToCtorProof (UPPER BOUND(ID))
transformed non-ctor to ctor-system
----------------------------------------

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


The TRS R consists of the following rules:

   *(i(x), x) -> 1
   *(1, y) -> y
   *(x, 0) -> 0
   *(c_*(x, y), z) -> *(x, *(y, z))

The (relative) TRS S consists of the following rules:

   encArg(i(x_1)) -> i(encArg(x_1))
   encArg(1) -> 1
   encArg(0) -> 0
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   encode_i(x_1) -> i(encArg(x_1))
   encode_1 -> 1
   encode_0 -> 0
   *(x0, x1) -> c_*(x0, x1)

Rewrite Strategy: FULL
----------------------------------------

(7) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

As the TRS is a non-duplicating overlay system, we have rc = irc.
----------------------------------------

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


The TRS R consists of the following rules:

   *(i(x), x) -> 1
   *(1, y) -> y
   *(x, 0) -> 0
   *(c_*(x, y), z) -> *(x, *(y, z))

The (relative) TRS S consists of the following rules:

   encArg(i(x_1)) -> i(encArg(x_1))
   encArg(1) -> 1
   encArg(0) -> 0
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   encode_i(x_1) -> i(encArg(x_1))
   encode_1 -> 1
   encode_0 -> 0
   *(x0, x1) -> c_*(x0, x1)

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

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

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

   *(i(x), x) -> 1 [1]
   *(1, y) -> y [1]
   *(x, 0) -> 0 [1]
   *(c_*(x, y), z) -> *(x, *(y, z)) [1]
   encArg(i(x_1)) -> i(encArg(x_1)) [0]
   encArg(1) -> 1 [0]
   encArg(0) -> 0 [0]
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2)) [0]
   encode_i(x_1) -> i(encArg(x_1)) [0]
   encode_1 -> 1 [0]
   encode_0 -> 0 [0]
   *(x0, x1) -> c_*(x0, x1) [0]

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

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

* => times

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

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

   times(i(x), x) -> 1 [1]
   times(1, y) -> y [1]
   times(x, 0) -> 0 [1]
   times(c_*(x, y), z) -> times(x, times(y, z)) [1]
   encArg(i(x_1)) -> i(encArg(x_1)) [0]
   encArg(1) -> 1 [0]
   encArg(0) -> 0 [0]
   encArg(cons_*(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_i(x_1) -> i(encArg(x_1)) [0]
   encode_1 -> 1 [0]
   encode_0 -> 0 [0]
   times(x0, x1) -> c_*(x0, x1) [0]

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

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

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

   times(i(x), x) -> 1 [1]
   times(1, y) -> y [1]
   times(x, 0) -> 0 [1]
   times(c_*(x, y), z) -> times(x, times(y, z)) [1]
   encArg(i(x_1)) -> i(encArg(x_1)) [0]
   encArg(1) -> 1 [0]
   encArg(0) -> 0 [0]
   encArg(cons_*(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_i(x_1) -> i(encArg(x_1)) [0]
   encode_1 -> 1 [0]
   encode_0 -> 0 [0]
   times(x0, x1) -> c_*(x0, x1) [0]

The TRS has the following type information:
times :: i:1:0:c_*:cons_* -> i:1:0:c_*:cons_* -> i:1:0:c_*:cons_*
i :: i:1:0:c_*:cons_* -> i:1:0:c_*:cons_*
1 :: i:1:0:c_*:cons_*
0 :: i:1:0:c_*:cons_*
c_* :: i:1:0:c_*:cons_* -> i:1:0:c_*:cons_* -> i:1:0:c_*:cons_*
encArg :: i:1:0:c_*:cons_* -> i:1:0:c_*:cons_*
cons_* :: i:1:0:c_*:cons_* -> i:1:0:c_*:cons_* -> i:1:0:c_*:cons_*
encode_* :: i:1:0:c_*:cons_* -> i:1:0:c_*:cons_* -> i:1:0:c_*:cons_*
encode_i :: i:1:0:c_*:cons_* -> i:1:0:c_*:cons_*
encode_1 :: i:1:0:c_*:cons_*
encode_0 :: i:1:0:c_*:cons_*

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

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

   encArg(v0) -> null_encArg [0]
   encode_*(v0, v1) -> null_encode_* [0]
   encode_i(v0) -> null_encode_i [0]
   encode_1 -> null_encode_1 [0]
   encode_0 -> null_encode_0 [0]
   times(v0, v1) -> null_times [0]

And the following fresh constants:    null_encArg, null_encode_*, null_encode_i, null_encode_1, null_encode_0, null_times

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

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

   times(i(x), x) -> 1 [1]
   times(1, y) -> y [1]
   times(x, 0) -> 0 [1]
   times(c_*(x, y), z) -> times(x, times(y, z)) [1]
   encArg(i(x_1)) -> i(encArg(x_1)) [0]
   encArg(1) -> 1 [0]
   encArg(0) -> 0 [0]
   encArg(cons_*(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_i(x_1) -> i(encArg(x_1)) [0]
   encode_1 -> 1 [0]
   encode_0 -> 0 [0]
   times(x0, x1) -> c_*(x0, x1) [0]
   encArg(v0) -> null_encArg [0]
   encode_*(v0, v1) -> null_encode_* [0]
   encode_i(v0) -> null_encode_i [0]
   encode_1 -> null_encode_1 [0]
   encode_0 -> null_encode_0 [0]
   times(v0, v1) -> null_times [0]

The TRS has the following type information:
times :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
i :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
1 :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
0 :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
c_* :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
encArg :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
cons_* :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
encode_* :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
encode_i :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times -> i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
encode_1 :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
encode_0 :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
null_encArg :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
null_encode_* :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
null_encode_i :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
null_encode_1 :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
null_encode_0 :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times
null_times :: i:1:0:c_*:cons_*:null_encArg:null_encode_*:null_encode_i:null_encode_1:null_encode_0:null_times

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

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

   1 => 1
   0 => 0
   null_encArg => 0
   null_encode_* => 0
   null_encode_i => 0
   null_encode_1 => 0
   null_encode_0 => 0
   null_times => 0

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

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

   encArg(z') -{ 0 }-> times(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2
   encArg(z') -{ 0 }-> 1 :|: z' = 1
   encArg(z') -{ 0 }-> 0 :|: z' = 0
   encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encArg(z') -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z' = 1 + x_1
   encode_*(z', z'') -{ 0 }-> times(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2
   encode_*(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   encode_0 -{ 0 }-> 0 :|: 
   encode_1 -{ 0 }-> 1 :|: 
   encode_1 -{ 0 }-> 0 :|: 
   encode_i(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encode_i(z') -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z' = x_1
   times(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 1
   times(z', z'') -{ 1 }-> times(x, times(y, z)) :|: z'' = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0
   times(z', z'') -{ 1 }-> 1 :|: z' = 1 + x, x >= 0, z'' = x
   times(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = x, x >= 0
   times(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   times(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z'' = x1, x0 >= 0, x1 >= 0, z' = x0

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V, V2),0,[times(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(start(V, V2),0,[encArg(V, Out)],[V >= 0]).
eq(start(V, V2),0,[fun(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(start(V, V2),0,[fun1(V, Out)],[V >= 0]).
eq(start(V, V2),0,[fun2(Out)],[]).
eq(start(V, V2),0,[fun3(Out)],[]).
eq(times(V, V2, Out),1,[],[Out = 1,V = 1 + V1,V1 >= 0,V2 = V1]).
eq(times(V, V2, Out),1,[],[Out = V3,V2 = V3,V3 >= 0,V = 1]).
eq(times(V, V2, Out),1,[],[Out = 0,V2 = 0,V = V4,V4 >= 0]).
eq(times(V, V2, Out),1,[times(V6, V7, Ret1),times(V5, Ret1, Ret)],[Out = Ret,V2 = V7,V7 >= 0,V = 1 + V5 + V6,V5 >= 0,V6 >= 0]).
eq(encArg(V, Out),0,[encArg(V8, Ret11)],[Out = 1 + Ret11,V8 >= 0,V = 1 + V8]).
eq(encArg(V, Out),0,[],[Out = 1,V = 1]).
eq(encArg(V, Out),0,[],[Out = 0,V = 0]).
eq(encArg(V, Out),0,[encArg(V9, Ret0),encArg(V10, Ret12),times(Ret0, Ret12, Ret2)],[Out = Ret2,V9 >= 0,V10 >= 0,V = 1 + V10 + V9]).
eq(fun(V, V2, Out),0,[encArg(V11, Ret01),encArg(V12, Ret13),times(Ret01, Ret13, Ret3)],[Out = Ret3,V11 >= 0,V = V11,V12 >= 0,V2 = V12]).
eq(fun1(V, Out),0,[encArg(V13, Ret14)],[Out = 1 + Ret14,V13 >= 0,V = V13]).
eq(fun2(Out),0,[],[Out = 1]).
eq(fun3(Out),0,[],[Out = 0]).
eq(times(V, V2, Out),0,[],[Out = 1 + V14 + V15,V2 = V14,V15 >= 0,V14 >= 0,V = V15]).
eq(encArg(V, Out),0,[],[Out = 0,V16 >= 0,V = V16]).
eq(fun(V, V2, Out),0,[],[Out = 0,V18 >= 0,V17 >= 0,V2 = V17,V = V18]).
eq(fun1(V, Out),0,[],[Out = 0,V19 >= 0,V = V19]).
eq(fun2(Out),0,[],[Out = 0]).
eq(times(V, V2, Out),0,[],[Out = 0,V20 >= 0,V21 >= 0,V2 = V21,V = V20]).
input_output_vars(times(V,V2,Out),[V,V2],[Out]).
input_output_vars(encArg(V,Out),[V],[Out]).
input_output_vars(fun(V,V2,Out),[V,V2],[Out]).
input_output_vars(fun1(V,Out),[V],[Out]).
input_output_vars(fun2(Out),[],[Out]).
input_output_vars(fun3(Out),[],[Out]).


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

#### Computed strongly connected components 
0. recursive [multiple] : [times/3]
1. recursive [non_tail,multiple] : [encArg/2]
2. non_recursive  : [fun/3]
3. non_recursive  : [fun1/2]
4. non_recursive  : [fun2/1]
5. non_recursive  : [fun3/1]
6. non_recursive  : [start/2]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into times/3
1. SCC is partially evaluated into encArg/2
2. SCC is partially evaluated into fun/3
3. SCC is partially evaluated into fun1/2
4. SCC is partially evaluated into fun2/1
5. SCC is completely evaluated into other SCCs
6. SCC is partially evaluated into start/2

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

### Specialization of cost equations times/3 
* CE 11 is refined into CE [23] 
* CE 7 is refined into CE [24] 
* CE 9 is refined into CE [25] 
* CE 12 is refined into CE [26] 
* CE 8 is refined into CE [27] 
* CE 10 is refined into CE [28] 


### Cost equations --> "Loop" of times/3 
* CEs [28] --> Loop 15 
* CEs [23] --> Loop 16 
* CEs [24] --> Loop 17 
* CEs [25,26] --> Loop 18 
* CEs [27] --> Loop 19 

### Ranking functions of CR times(V,V2,Out) 
* RF of phase [15]: [V]

#### Partial ranking functions of CR times(V,V2,Out) 
* Partial RF of phase [15]:
  - RF of loop [15:1,15:2]:
    V


### Specialization of cost equations encArg/2 
* CE 15 is refined into CE [29] 
* CE 14 is refined into CE [30] 
* CE 16 is refined into CE [31,32,33,34] 
* CE 13 is refined into CE [35] 


### Cost equations --> "Loop" of encArg/2 
* CEs [35] --> Loop 20 
* CEs [34] --> Loop 21 
* CEs [31,33] --> Loop 22 
* CEs [32] --> Loop 23 
* CEs [29] --> Loop 24 
* CEs [30] --> Loop 25 

### Ranking functions of CR encArg(V,Out) 
* RF of phase [20,21,22,23]: [V]

#### Partial ranking functions of CR encArg(V,Out) 
* Partial RF of phase [20,21,22,23]:
  - RF of loop [20:1,21:1,21:2,22:1,22:2,23:1,23:2]:
    V


### Specialization of cost equations fun/3 
* CE 17 is refined into CE [36,37,38,39,40,41,42,43,44,45,46,47] 
* CE 18 is refined into CE [48] 


### Cost equations --> "Loop" of fun/3 
* CEs [36,39] --> Loop 26 
* CEs [40,43] --> Loop 27 
* CEs [45] --> Loop 28 
* CEs [38,42,47] --> Loop 29 
* CEs [37,41,44,46,48] --> Loop 30 

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

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


### Specialization of cost equations fun1/2 
* CE 19 is refined into CE [49,50] 
* CE 20 is refined into CE [51] 


### Cost equations --> "Loop" of fun1/2 
* CEs [49] --> Loop 31 
* CEs [50] --> Loop 32 
* CEs [51] --> Loop 33 

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

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


### Specialization of cost equations fun2/1 
* CE 21 is refined into CE [52] 
* CE 22 is refined into CE [53] 


### Cost equations --> "Loop" of fun2/1 
* CEs [52] --> Loop 34 
* CEs [53] --> Loop 35 

### Ranking functions of CR fun2(Out) 

#### Partial ranking functions of CR fun2(Out) 


### Specialization of cost equations start/2 
* CE 1 is refined into CE [54,55,56,57] 
* CE 2 is refined into CE [58,59] 
* CE 3 is refined into CE [60,61,62,63,64] 
* CE 4 is refined into CE [65,66,67] 
* CE 5 is refined into CE [68,69] 
* CE 6 is refined into CE [70] 


### Cost equations --> "Loop" of start/2 
* CEs [54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70] --> Loop 36 

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

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


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

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

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

* Chain [17]: 1
  with precondition: [Out=1,V=V2+1,V>=1] 

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

* Chain [multiple([15],[[19],[18],[17],[16]])]: 1*it(15)+1*it([17])+1*it([18])+1*it([19])+0
  Such that:it([19]) =< V/2+1/2
it([17]) =< V/2-V2/2+1/2
aux(2) =< V
aux(3) =< V+1
it(15) =< aux(2)
it([17]) =< aux(2)
it([19]) =< aux(2)
it([17]) =< aux(3)
it([18]) =< aux(3)
it([19]) =< aux(3)

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


#### Cost of chains of encArg(V,Out):
* Chain [25]: 0
  with precondition: [V=1,Out=1] 

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

* Chain [multiple([20,21,22,23],[[25],[24]])]: 2*it(22)+2*s(19)+1*s(20)+1*s(21)+0
  Such that:aux(13) =< V
aux(14) =< 2*V+1
it(22) =< aux(13)
it(22) =< aux(14)
aux(6) =< aux(13)+1
s(23) =< it(22)*aux(13)
aux(7) =< it(22)*aux(6)
s(24) =< aux(7)*(1/2)
s(19) =< s(24)
s(20) =< s(23)
s(19) =< s(23)
s(19) =< aux(7)
s(21) =< aux(7)

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


#### Cost of chains of fun(V,V2,Out):
* Chain [30]: 4*s(37)+4*s(42)+2*s(43)+2*s(44)+4*s(47)+4*s(52)+2*s(53)+2*s(54)+1
  Such that:aux(15) =< V
aux(16) =< 2*V+1
aux(17) =< V2
aux(18) =< 2*V2+1
s(47) =< aux(17)
s(47) =< aux(18)
s(48) =< aux(17)+1
s(49) =< s(47)*aux(17)
s(50) =< s(47)*s(48)
s(51) =< s(50)*(1/2)
s(52) =< s(51)
s(53) =< s(49)
s(52) =< s(49)
s(52) =< s(50)
s(54) =< s(50)
s(37) =< aux(15)
s(37) =< aux(16)
s(38) =< aux(15)+1
s(39) =< s(37)*aux(15)
s(40) =< s(37)*s(38)
s(41) =< s(40)*(1/2)
s(42) =< s(41)
s(43) =< s(39)
s(42) =< s(39)
s(42) =< s(40)
s(44) =< s(40)

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

* Chain [29]: 4*s(77)+4*s(82)+2*s(83)+2*s(84)+2*s(87)+2*s(92)+1*s(93)+1*s(94)+1
  Such that:s(85) =< V2
s(86) =< 2*V2+1
aux(19) =< V
aux(20) =< 2*V+1
s(87) =< s(85)
s(87) =< s(86)
s(88) =< s(85)+1
s(89) =< s(87)*s(85)
s(90) =< s(87)*s(88)
s(91) =< s(90)*(1/2)
s(92) =< s(91)
s(93) =< s(89)
s(92) =< s(89)
s(92) =< s(90)
s(94) =< s(90)
s(77) =< aux(19)
s(77) =< aux(20)
s(78) =< aux(19)+1
s(79) =< s(77)*aux(19)
s(80) =< s(77)*s(78)
s(81) =< s(80)*(1/2)
s(82) =< s(81)
s(83) =< s(79)
s(82) =< s(79)
s(82) =< s(80)
s(84) =< s(80)

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

* Chain [28]: 2*s(107)+2*s(112)+1*s(113)+1*s(114)+0
  Such that:s(105) =< V2
s(106) =< 2*V2+1
s(107) =< s(105)
s(107) =< s(106)
s(108) =< s(105)+1
s(109) =< s(107)*s(105)
s(110) =< s(107)*s(108)
s(111) =< s(110)*(1/2)
s(112) =< s(111)
s(113) =< s(109)
s(112) =< s(109)
s(112) =< s(110)
s(114) =< s(110)

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

* Chain [27]: 4*s(117)+4*s(122)+2*s(123)+2*s(124)+2*s(127)+1*s(129)+1*s(130)+1
  Such that:s(126) =< V+1
aux(22) =< V/2+1/2
aux(23) =< V
aux(24) =< 2*V+1
s(117) =< aux(23)
s(117) =< aux(24)
s(118) =< aux(23)+1
s(119) =< s(117)*aux(23)
s(120) =< s(117)*s(118)
s(121) =< s(120)*(1/2)
s(122) =< s(121)
s(123) =< s(119)
s(122) =< s(119)
s(122) =< s(120)
s(124) =< s(120)
s(127) =< aux(22)
s(129) =< aux(23)
s(127) =< aux(23)
s(127) =< s(126)
s(130) =< s(126)

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

* Chain [26]: 4*s(143)+4*s(148)+2*s(149)+2*s(150)+4*s(153)+4*s(158)+2*s(159)+2*s(160)+2*s(163)+1*s(165)+1*s(166)+1
  Such that:s(162) =< V+1
aux(26) =< V/2+1/2
aux(27) =< V
aux(28) =< 2*V+1
aux(29) =< V2
aux(30) =< 2*V2+1
s(153) =< aux(29)
s(153) =< aux(30)
s(154) =< aux(29)+1
s(155) =< s(153)*aux(29)
s(156) =< s(153)*s(154)
s(157) =< s(156)*(1/2)
s(158) =< s(157)
s(159) =< s(155)
s(158) =< s(155)
s(158) =< s(156)
s(160) =< s(156)
s(143) =< aux(27)
s(143) =< aux(28)
s(144) =< aux(27)+1
s(145) =< s(143)*aux(27)
s(146) =< s(143)*s(144)
s(147) =< s(146)*(1/2)
s(148) =< s(147)
s(149) =< s(145)
s(148) =< s(145)
s(148) =< s(146)
s(150) =< s(146)
s(163) =< aux(26)
s(165) =< aux(27)
s(163) =< aux(27)
s(163) =< s(162)
s(166) =< s(162)

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


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

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

* Chain [31]: 2*s(189)+2*s(194)+1*s(195)+1*s(196)+0
  Such that:s(187) =< V
s(188) =< 2*V+1
s(189) =< s(187)
s(189) =< s(188)
s(190) =< s(187)+1
s(191) =< s(189)*s(187)
s(192) =< s(189)*s(190)
s(193) =< s(192)*(1/2)
s(194) =< s(193)
s(195) =< s(191)
s(194) =< s(191)
s(194) =< s(192)
s(196) =< s(192)

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


#### Cost of chains of fun2(Out):
* Chain [35]: 0
  with precondition: [Out=0] 

* Chain [34]: 0
  with precondition: [Out=1] 


#### Cost of chains of start(V,V2):
* Chain [36]: 5*s(199)+1*s(200)+3*s(201)+3*s(202)+20*s(205)+20*s(210)+10*s(211)+10*s(212)+12*s(217)+12*s(222)+6*s(223)+6*s(224)+1
  Such that:s(200) =< V/2-V2/2+1/2
aux(31) =< V
aux(32) =< V+1
aux(33) =< 2*V+1
aux(34) =< V/2+1/2
aux(35) =< V2
aux(36) =< 2*V2+1
s(199) =< aux(34)
s(201) =< aux(31)
s(200) =< aux(31)
s(199) =< aux(31)
s(200) =< aux(32)
s(202) =< aux(32)
s(199) =< aux(32)
s(205) =< aux(31)
s(205) =< aux(33)
s(206) =< aux(31)+1
s(207) =< s(205)*aux(31)
s(208) =< s(205)*s(206)
s(209) =< s(208)*(1/2)
s(210) =< s(209)
s(211) =< s(207)
s(210) =< s(207)
s(210) =< s(208)
s(212) =< s(208)
s(217) =< aux(35)
s(217) =< aux(36)
s(218) =< aux(35)+1
s(219) =< s(217)*aux(35)
s(220) =< s(217)*s(218)
s(221) =< s(220)*(1/2)
s(222) =< s(221)
s(223) =< s(219)
s(222) =< s(219)
s(222) =< s(220)
s(224) =< s(220)

  with precondition: [] 


Closed-form bounds of start(V,V2): 
-------------------------------------
* Chain [36] with precondition: [] 
    - Upper bound: nat(V)*43+1+nat(V)*30*nat(V)+nat(V2)*24+nat(V2)*18*nat(V2)+nat(V+1)*3+nat(V/2-V2/2+1/2)+nat(V/2+1/2)*5 
    - Complexity: n^2 

### Maximum cost of start(V,V2): nat(V)*43+1+nat(V)*30*nat(V)+nat(V2)*24+nat(V2)*18*nat(V2)+nat(V+1)*3+nat(V/2-V2/2+1/2)+nat(V/2+1/2)*5 
Asymptotic class: n^2 
* Total analysis performed in 519 ms.


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

(20)
BOUNDS(1, n^2)