/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 (innermost) 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), 162 ms]
(4) CpxRelTRS
(5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
(6) CpxRelTRS
(7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(8) CpxWeightedTrs
(9) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(10) CpxWeightedTrs
(11) TypeInferenceProof [BOTH BOUNDS(ID, ID), 1 ms]
(12) CpxTypedWeightedTrs
(13) CompletionProof [UPPER BOUND(ID), 0 ms]
(14) CpxTypedWeightedCompleteTrs
(15) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
(16) CpxRNTS
(17) CompleteCoflocoProof [FINISHED, 453 ms]
(18) BOUNDS(1, n^2)


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

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


The TRS R consists of the following rules:

   +(*(x, y), *(a, y)) -> *(+(x, a), y)
   *(*(x, y), z) -> *(x, *(y, z))

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

(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(a) -> a
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   encode_a -> a


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

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

   +(*(x, y), *(a, y)) -> *(+(x, a), y)
   *(*(x, y), z) -> *(x, *(y, z))

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

   encArg(a) -> a
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   encode_a -> a

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

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

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

   +(*(x, y), *(a, y)) -> *(+(x, a), y)
   *(*(x, y), z) -> *(x, *(y, z))

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

   encArg(a) -> a
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   encode_a -> a

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

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

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

   +(c_*(x, y), c_*(a, y)) -> *(+(x, a), y)
   *(c_*(x, y), z) -> *(x, *(y, z))

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

   encArg(a) -> a
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encArg(cons_*(x_1, x_2)) -> *(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2))
   encode_a -> a
   *(x0, x1) -> c_*(x0, x1)

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

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

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

   +(c_*(x, y), c_*(a, y)) -> *(+(x, a), y) [1]
   *(c_*(x, y), z) -> *(x, *(y, z)) [1]
   encArg(a) -> a [0]
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) [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_*(x_1, x_2) -> *(encArg(x_1), encArg(x_2)) [0]
   encode_a -> a [0]
   *(x0, x1) -> c_*(x0, x1) [0]

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

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

+ => plus
* => times

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

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

   plus(c_*(x, y), c_*(a, y)) -> times(plus(x, a), y) [1]
   times(c_*(x, y), z) -> times(x, times(y, z)) [1]
   encArg(a) -> a [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_*(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_a -> a [0]
   times(x0, x1) -> c_*(x0, x1) [0]

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

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

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

   plus(c_*(x, y), c_*(a, y)) -> times(plus(x, a), y) [1]
   times(c_*(x, y), z) -> times(x, times(y, z)) [1]
   encArg(a) -> a [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_*(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_a -> a [0]
   times(x0, x1) -> c_*(x0, x1) [0]

The TRS has the following type information:
plus :: c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_*
c_* :: c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_*
a :: c_*:a:cons_+:cons_*
times :: c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_*
encArg :: c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_*
cons_+ :: c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_*
cons_* :: c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_*
encode_+ :: c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_*
encode_* :: c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_* -> c_*:a:cons_+:cons_*
encode_a :: c_*:a:cons_+:cons_*

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

(13) 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_*(v0, v1) -> null_encode_* [0]
   encode_a -> null_encode_a [0]
   times(v0, v1) -> null_times [0]
   plus(v0, v1) -> null_plus [0]

And the following fresh constants:    null_encArg, null_encode_+, null_encode_*, null_encode_a, null_times, null_plus

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

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

   plus(c_*(x, y), c_*(a, y)) -> times(plus(x, a), y) [1]
   times(c_*(x, y), z) -> times(x, times(y, z)) [1]
   encArg(a) -> a [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_*(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_*(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) [0]
   encode_a -> a [0]
   times(x0, x1) -> c_*(x0, x1) [0]
   encArg(v0) -> null_encArg [0]
   encode_+(v0, v1) -> null_encode_+ [0]
   encode_*(v0, v1) -> null_encode_* [0]
   encode_a -> null_encode_a [0]
   times(v0, v1) -> null_times [0]
   plus(v0, v1) -> null_plus [0]

The TRS has the following type information:
plus :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
c_* :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
a :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
times :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
encArg :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
cons_+ :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
cons_* :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
encode_+ :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
encode_* :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus -> c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
encode_a :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
null_encArg :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
null_encode_+ :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
null_encode_* :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
null_encode_a :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
null_times :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus
null_plus :: c_*:a:cons_+:cons_*:null_encArg:null_encode_+:null_encode_*:null_encode_a:null_times:null_plus

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

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

   a => 0
   null_encArg => 0
   null_encode_+ => 0
   null_encode_* => 0
   null_encode_a => 0
   null_times => 0
   null_plus => 0

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

(16)
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 }-> plus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2
   encArg(z') -{ 0 }-> 0 :|: z' = 0
   encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   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_+(z', z'') -{ 0 }-> plus(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_a -{ 0 }-> 0 :|: 
   plus(z', z'') -{ 1 }-> times(plus(x, 0), y) :|: z' = 1 + x + y, x >= 0, y >= 0, z'' = 1 + 0 + y
   plus(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   times(z', z'') -{ 1 }-> times(x, times(y, z)) :|: z'' = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 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.

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

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

eq(start(V, V2),0,[plus(V, V2, Out)],[V >= 0,V2 >= 0]).
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, V2, Out)],[V >= 0,V2 >= 0]).
eq(start(V, V2),0,[fun2(Out)],[]).
eq(plus(V, V2, Out),1,[plus(V1, 0, Ret0),times(Ret0, V3, Ret)],[Out = Ret,V = 1 + V1 + V3,V1 >= 0,V3 >= 0,V2 = 1 + V3]).
eq(times(V, V2, Out),1,[times(V5, V6, Ret1),times(V4, Ret1, Ret2)],[Out = Ret2,V2 = V6,V6 >= 0,V = 1 + V4 + V5,V4 >= 0,V5 >= 0]).
eq(encArg(V, Out),0,[],[Out = 0,V = 0]).
eq(encArg(V, Out),0,[encArg(V8, Ret01),encArg(V7, Ret11),plus(Ret01, Ret11, Ret3)],[Out = Ret3,V8 >= 0,V7 >= 0,V = 1 + V7 + V8]).
eq(encArg(V, Out),0,[encArg(V9, Ret02),encArg(V10, Ret12),times(Ret02, Ret12, Ret4)],[Out = Ret4,V9 >= 0,V10 >= 0,V = 1 + V10 + V9]).
eq(fun(V, V2, Out),0,[encArg(V12, Ret03),encArg(V11, Ret13),plus(Ret03, Ret13, Ret5)],[Out = Ret5,V12 >= 0,V = V12,V11 >= 0,V2 = V11]).
eq(fun1(V, V2, Out),0,[encArg(V14, Ret04),encArg(V13, Ret14),times(Ret04, Ret14, Ret6)],[Out = Ret6,V14 >= 0,V = V14,V13 >= 0,V2 = V13]).
eq(fun2(Out),0,[],[Out = 0]).
eq(times(V, V2, Out),0,[],[Out = 1 + V15 + V16,V2 = V15,V16 >= 0,V15 >= 0,V = V16]).
eq(encArg(V, Out),0,[],[Out = 0,V17 >= 0,V = V17]).
eq(fun(V, V2, Out),0,[],[Out = 0,V19 >= 0,V18 >= 0,V2 = V18,V = V19]).
eq(fun1(V, V2, Out),0,[],[Out = 0,V21 >= 0,V20 >= 0,V2 = V20,V = V21]).
eq(times(V, V2, Out),0,[],[Out = 0,V22 >= 0,V23 >= 0,V2 = V23,V = V22]).
eq(plus(V, V2, Out),0,[],[Out = 0,V24 >= 0,V25 >= 0,V2 = V25,V = V24]).
input_output_vars(plus(V,V2,Out),[V,V2],[Out]).
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,V2,Out),[V,V2],[Out]).
input_output_vars(fun2(Out),[],[Out]).


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

#### Computed strongly connected components 
0. recursive [multiple] : [times/3]
1. recursive [non_tail] : [plus/3]
2. recursive [non_tail,multiple] : [encArg/2]
3. non_recursive  : [fun/3]
4. non_recursive  : [fun1/3]
5. non_recursive  : [fun2/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 plus/3
2. SCC is partially evaluated into encArg/2
3. SCC is partially evaluated into fun/3
4. SCC is partially evaluated into fun1/3
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 10 is refined into CE [19] 
* CE 11 is refined into CE [20] 
* CE 9 is refined into CE [21] 


### Cost equations --> "Loop" of times/3 
* CEs [21] --> Loop 11 
* CEs [19] --> Loop 12 
* CEs [20] --> Loop 13 

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

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


### Specialization of cost equations plus/3 
* CE 8 is refined into CE [22] 
* CE 7 is refined into CE [23,24,25] 


### Cost equations --> "Loop" of plus/3 
* CEs [25] --> Loop 14 
* CEs [24] --> Loop 15 
* CEs [23] --> Loop 16 
* CEs [22] --> Loop 17 

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

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


### Specialization of cost equations encArg/2 
* CE 12 is refined into CE [26] 
* CE 13 is refined into CE [27,28] 
* CE 14 is refined into CE [29,30,31] 


### Cost equations --> "Loop" of encArg/2 
* CEs [30] --> Loop 18 
* CEs [28,31] --> Loop 19 
* CEs [27,29] --> Loop 20 
* CEs [26] --> Loop 21 

### Ranking functions of CR encArg(V,Out) 
* RF of phase [18,19,20]: [V]

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


### Specialization of cost equations fun/3 
* CE 15 is refined into CE [32,33,34,35,36] 
* CE 16 is refined into CE [37] 


### Cost equations --> "Loop" of fun/3 
* CEs [36] --> Loop 22 
* CEs [32,33,34,35,37] --> Loop 23 

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

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


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


### Cost equations --> "Loop" of fun1/3 
* CEs [46,47] --> Loop 24 
* CEs [43,44] --> Loop 25 
* CEs [41] --> Loop 26 
* CEs [39] --> Loop 27 
* CEs [38,40,42,45,48] --> Loop 28 

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

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


### Specialization of cost equations start/2 
* CE 1 is refined into CE [49,50] 
* CE 2 is refined into CE [51,52,53] 
* CE 3 is refined into CE [54,55] 
* CE 4 is refined into CE [56,57] 
* CE 5 is refined into CE [58,59,60,61,62] 
* CE 6 is refined into CE [63] 


### Cost equations --> "Loop" of start/2 
* CEs [49,50,51,52,53,54,55,56,57,58,59,60,61,62,63] --> Loop 29 

### 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 [13]: 0
  with precondition: [Out=0,V>=0,V2>=0] 

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

* Chain [multiple([11],[[13],[12]])]: 1*it(11)+0
  Such that:it(11) =< V

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


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

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

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


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

* Chain [multiple([18,19,20],[[21]])]: 2*it(19)+1*s(3)+0
  Such that:aux(3) =< V
aux(4) =< 2*V+1
it(19) =< aux(3)
it(19) =< aux(4)
s(3) =< it(19)*aux(3)

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


#### Cost of chains of fun(V,V2,Out):
* Chain [23]: 4*s(6)+2*s(7)+4*s(10)+2*s(11)+1
  Such that:aux(5) =< V
aux(6) =< 2*V+1
aux(7) =< V2
aux(8) =< 2*V2+1
s(10) =< aux(5)
s(10) =< aux(6)
s(11) =< s(10)*aux(5)
s(6) =< aux(7)
s(6) =< aux(8)
s(7) =< s(6)*aux(7)

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

* Chain [22]: 2*s(22)+1*s(23)+2*s(26)+1*s(27)+1
  Such that:s(20) =< V
s(21) =< 2*V+1
s(24) =< V2
s(25) =< 2*V2+1
s(26) =< s(24)
s(26) =< s(25)
s(27) =< s(26)*s(24)
s(22) =< s(20)
s(22) =< s(21)
s(23) =< s(22)*s(20)

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


#### Cost of chains of fun1(V,V2,Out):
* Chain [28]: 4*s(30)+2*s(31)+4*s(34)+2*s(35)+0
  Such that:aux(9) =< V
aux(10) =< 2*V+1
aux(11) =< V2
aux(12) =< 2*V2+1
s(34) =< aux(9)
s(34) =< aux(10)
s(35) =< s(34)*aux(9)
s(30) =< aux(11)
s(30) =< aux(12)
s(31) =< s(30)*aux(11)

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

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

* Chain [26]: 2*s(46)+1*s(47)+0
  Such that:s(44) =< V2
s(45) =< 2*V2+1
s(46) =< s(44)
s(46) =< s(45)
s(47) =< s(46)*s(44)

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

* Chain [25]: 4*s(50)+2*s(51)+1*s(56)+0
  Such that:aux(14) =< V
aux(15) =< 2*V+1
s(50) =< aux(14)
s(50) =< aux(15)
s(51) =< s(50)*aux(14)
s(56) =< aux(14)

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

* Chain [24]: 4*s(59)+2*s(60)+4*s(63)+2*s(64)+1*s(73)+0
  Such that:aux(17) =< V
aux(18) =< 2*V+1
aux(19) =< V2
aux(20) =< 2*V2+1
s(63) =< aux(19)
s(63) =< aux(20)
s(64) =< s(63)*aux(19)
s(59) =< aux(17)
s(59) =< aux(18)
s(60) =< s(59)*aux(17)
s(73) =< aux(17)

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


#### Cost of chains of start(V,V2):
* Chain [29]: 3*s(74)+20*s(77)+10*s(78)+16*s(85)+8*s(86)+1
  Such that:aux(21) =< V
aux(22) =< 2*V+1
aux(23) =< V2
aux(24) =< 2*V2+1
s(74) =< aux(21)
s(77) =< aux(21)
s(77) =< aux(22)
s(78) =< s(77)*aux(21)
s(85) =< aux(23)
s(85) =< aux(24)
s(86) =< s(85)*aux(23)

  with precondition: [] 


Closed-form bounds of start(V,V2): 
-------------------------------------
* Chain [29] with precondition: [] 
    - Upper bound: nat(V)*23+1+nat(V)*10*nat(V)+nat(V2)*16+nat(V2)*8*nat(V2) 
    - Complexity: n^2 

### Maximum cost of start(V,V2): nat(V)*23+1+nat(V)*10*nat(V)+nat(V2)*16+nat(V2)*8*nat(V2) 
Asymptotic class: n^2 
* Total analysis performed in 368 ms.


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

(18)
BOUNDS(1, n^2)