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


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


WORST_CASE(?, O(n^2))
proof of /export/starexec/sandbox/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), 161 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) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(12) CpxTypedWeightedTrs
(13) CompletionProof [UPPER BOUND(ID), 0 ms]
(14) CpxTypedWeightedCompleteTrs
(15) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
(16) CpxRNTS
(17) CompleteCoflocoProof [FINISHED, 2133 ms]
(18) 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:

   f(f(x, y, z), u, f(x, y, v)) -> f(x, y, f(z, u, v))
   f(x, y, y) -> y
   f(x, y, g(y)) -> x
   f(x, x, y) -> x
   f(g(x), x, y) -> y

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(g(x_1)) -> g(encArg(x_1))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_g(x_1) -> g(encArg(x_1))


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

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

   f(f(x, y, z), u, f(x, y, v)) -> f(x, y, f(z, u, v))
   f(x, y, y) -> y
   f(x, y, g(y)) -> x
   f(x, x, y) -> x
   f(g(x), x, y) -> y

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

   encArg(g(x_1)) -> g(encArg(x_1))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_g(x_1) -> g(encArg(x_1))

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:

   f(f(x, y, z), u, f(x, y, v)) -> f(x, y, f(z, u, v))
   f(x, y, y) -> y
   f(x, y, g(y)) -> x
   f(x, x, y) -> x
   f(g(x), x, y) -> y

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

   encArg(g(x_1)) -> g(encArg(x_1))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_g(x_1) -> g(encArg(x_1))

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:

   f(x, y, y) -> y
   f(x, y, g(y)) -> x
   f(x, x, y) -> x
   f(g(x), x, y) -> y
   f(c_f(x, y, z), u, c_f(x, y, v)) -> f(x, y, f(z, u, v))

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

   encArg(g(x_1)) -> g(encArg(x_1))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_g(x_1) -> g(encArg(x_1))
   f(x0, x1, x2) -> c_f(x0, x1, x2)

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:

   f(x, y, y) -> y
   f(x, y, g(y)) -> x
   f(x, x, y) -> x
   f(g(x), x, y) -> y
   f(c_f(x, y, z), u, c_f(x, y, v)) -> f(x, y, f(z, u, v))

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

   encArg(g(x_1)) -> g(encArg(x_1))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_g(x_1) -> g(encArg(x_1))
   f(x0, x1, x2) -> c_f(x0, x1, x2)

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:

   f(x, y, y) -> y [1]
   f(x, y, g(y)) -> x [1]
   f(x, x, y) -> x [1]
   f(g(x), x, y) -> y [1]
   f(c_f(x, y, z), u, c_f(x, y, v)) -> f(x, y, f(z, u, v)) [1]
   encArg(g(x_1)) -> g(encArg(x_1)) [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_g(x_1) -> g(encArg(x_1)) [0]
   f(x0, x1, x2) -> c_f(x0, x1, x2) [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:

   f(x, y, y) -> y [1]
   f(x, y, g(y)) -> x [1]
   f(x, x, y) -> x [1]
   f(g(x), x, y) -> y [1]
   f(c_f(x, y, z), u, c_f(x, y, v)) -> f(x, y, f(z, u, v)) [1]
   encArg(g(x_1)) -> g(encArg(x_1)) [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_g(x_1) -> g(encArg(x_1)) [0]
   f(x0, x1, x2) -> c_f(x0, x1, x2) [0]

The TRS has the following type information:
f :: g:c_f:cons_f -> g:c_f:cons_f -> g:c_f:cons_f -> g:c_f:cons_f
g :: g:c_f:cons_f -> g:c_f:cons_f
c_f :: g:c_f:cons_f -> g:c_f:cons_f -> g:c_f:cons_f -> g:c_f:cons_f
encArg :: g:c_f:cons_f -> g:c_f:cons_f
cons_f :: g:c_f:cons_f -> g:c_f:cons_f -> g:c_f:cons_f -> g:c_f:cons_f
encode_f :: g:c_f:cons_f -> g:c_f:cons_f -> g:c_f:cons_f -> g:c_f:cons_f
encode_g :: g:c_f:cons_f -> g:c_f:cons_f

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_f(v0, v1, v2) -> null_encode_f [0]
   encode_g(v0) -> null_encode_g [0]
   f(v0, v1, v2) -> null_f [0]

And the following fresh constants:    null_encArg, null_encode_f, null_encode_g, null_f

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

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

   f(x, y, y) -> y [1]
   f(x, y, g(y)) -> x [1]
   f(x, x, y) -> x [1]
   f(g(x), x, y) -> y [1]
   f(c_f(x, y, z), u, c_f(x, y, v)) -> f(x, y, f(z, u, v)) [1]
   encArg(g(x_1)) -> g(encArg(x_1)) [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_g(x_1) -> g(encArg(x_1)) [0]
   f(x0, x1, x2) -> c_f(x0, x1, x2) [0]
   encArg(v0) -> null_encArg [0]
   encode_f(v0, v1, v2) -> null_encode_f [0]
   encode_g(v0) -> null_encode_g [0]
   f(v0, v1, v2) -> null_f [0]

The TRS has the following type information:
f :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
g :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
c_f :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
encArg :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
cons_f :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
encode_f :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
encode_g :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f -> g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
null_encArg :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
null_encode_f :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
null_encode_g :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f
null_f :: g:c_f:cons_f:null_encArg:null_encode_f:null_encode_g:null_f

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:

   null_encArg => 0
   null_encode_f => 0
   null_encode_g => 0
   null_f => 0

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

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

   encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encArg(z') -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z' = 1 + x_1
   encode_f(z', z'', z1) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z1 = x_3, z' = x_1, x_3 >= 0, x_2 >= 0, z'' = x_2
   encode_f(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0
   encode_g(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encode_g(z') -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z' = x_1
   f(z', z'', z1) -{ 1 }-> x :|: z' = x, z'' = y, x >= 0, y >= 0, z1 = 1 + y
   f(z', z'', z1) -{ 1 }-> x :|: z1 = y, z' = x, x >= 0, y >= 0, z'' = x
   f(z', z'', z1) -{ 1 }-> y :|: z1 = y, z' = x, z'' = y, x >= 0, y >= 0
   f(z', z'', z1) -{ 1 }-> y :|: z' = 1 + x, z1 = y, x >= 0, y >= 0, z'' = x
   f(z', z'', z1) -{ 1 }-> f(x, y, f(z, u, v)) :|: z1 = 1 + x + y + v, z >= 0, v >= 0, x >= 0, y >= 0, z' = 1 + x + y + z, z'' = u, u >= 0
   f(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0
   f(z', z'', z1) -{ 0 }-> 1 + x0 + x1 + x2 :|: z'' = x1, x0 >= 0, x1 >= 0, z1 = x2, x2 >= 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, V4),0,[f(V, V2, V4, Out)],[V >= 0,V2 >= 0,V4 >= 0]).
eq(start(V, V2, V4),0,[encArg(V, Out)],[V >= 0]).
eq(start(V, V2, V4),0,[fun(V, V2, V4, Out)],[V >= 0,V2 >= 0,V4 >= 0]).
eq(start(V, V2, V4),0,[fun1(V, Out)],[V >= 0]).
eq(f(V, V2, V4, Out),1,[],[Out = V3,V4 = V3,V = V1,V2 = V3,V1 >= 0,V3 >= 0]).
eq(f(V, V2, V4, Out),1,[],[Out = V5,V = V5,V2 = V6,V5 >= 0,V6 >= 0,V4 = 1 + V6]).
eq(f(V, V2, V4, Out),1,[],[Out = V7,V4 = V8,V = V7,V7 >= 0,V8 >= 0,V2 = V7]).
eq(f(V, V2, V4, Out),1,[],[Out = V9,V = 1 + V10,V4 = V9,V10 >= 0,V9 >= 0,V2 = V10]).
eq(f(V, V2, V4, Out),1,[f(V15, V12, V13, Ret2),f(V14, V11, Ret2, Ret)],[Out = Ret,V4 = 1 + V11 + V13 + V14,V15 >= 0,V13 >= 0,V14 >= 0,V11 >= 0,V = 1 + V11 + V14 + V15,V2 = V12,V12 >= 0]).
eq(encArg(V, Out),0,[encArg(V16, Ret1)],[Out = 1 + Ret1,V16 >= 0,V = 1 + V16]).
eq(encArg(V, Out),0,[encArg(V18, Ret0),encArg(V19, Ret11),encArg(V17, Ret21),f(Ret0, Ret11, Ret21, Ret3)],[Out = Ret3,V18 >= 0,V = 1 + V17 + V18 + V19,V17 >= 0,V19 >= 0]).
eq(fun(V, V2, V4, Out),0,[encArg(V20, Ret01),encArg(V22, Ret12),encArg(V21, Ret22),f(Ret01, Ret12, Ret22, Ret4)],[Out = Ret4,V20 >= 0,V4 = V21,V = V20,V21 >= 0,V22 >= 0,V2 = V22]).
eq(fun1(V, Out),0,[encArg(V23, Ret13)],[Out = 1 + Ret13,V23 >= 0,V = V23]).
eq(f(V, V2, V4, Out),0,[],[Out = 1 + V24 + V25 + V26,V2 = V25,V26 >= 0,V25 >= 0,V4 = V24,V24 >= 0,V = V26]).
eq(encArg(V, Out),0,[],[Out = 0,V27 >= 0,V = V27]).
eq(fun(V, V2, V4, Out),0,[],[Out = 0,V29 >= 0,V4 = V30,V28 >= 0,V2 = V28,V30 >= 0,V = V29]).
eq(fun1(V, Out),0,[],[Out = 0,V31 >= 0,V = V31]).
eq(f(V, V2, V4, Out),0,[],[Out = 0,V32 >= 0,V4 = V33,V34 >= 0,V2 = V34,V33 >= 0,V = V32]).
input_output_vars(f(V,V2,V4,Out),[V,V2,V4],[Out]).
input_output_vars(encArg(V,Out),[V],[Out]).
input_output_vars(fun(V,V2,V4,Out),[V,V2,V4],[Out]).
input_output_vars(fun1(V,Out),[V],[Out]).


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

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

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into f/4
1. SCC is partially evaluated into encArg/2
2. SCC is partially evaluated into fun/4
3. SCC is partially evaluated into fun1/2
4. SCC is partially evaluated into start/3

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

### Specialization of cost equations f/4 
* CE 10 is refined into CE [19] 
* CE 5 is refined into CE [20] 
* CE 6 is refined into CE [21] 
* CE 7 is refined into CE [22] 
* CE 8 is refined into CE [23] 
* CE 11 is refined into CE [24] 
* CE 9 is refined into CE [25] 


### Cost equations --> "Loop" of f/4 
* CEs [25] --> Loop 14 
* CEs [19] --> Loop 15 
* CEs [20] --> Loop 16 
* CEs [21] --> Loop 17 
* CEs [22] --> Loop 18 
* CEs [23] --> Loop 19 
* CEs [24] --> Loop 20 

### Ranking functions of CR f(V,V2,V4,Out) 
* RF of phase [14]: [V,V+V2]

#### Partial ranking functions of CR f(V,V2,V4,Out) 
* Partial RF of phase [14]:
  - RF of loop [14:1]:
    V4 depends on loops [14:2] 
  - RF of loop [14:1,14:2]:
    V
  - RF of loop [14:2]:
    V+V2


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


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

### Ranking functions of CR encArg(V,Out) 
* RF of phase [21,22,23,24,25,26,27,28]: [V]

#### Partial ranking functions of CR encArg(V,Out) 
* Partial RF of phase [21,22,23,24,25,26,27,28]:
  - RF of loop [21:1,22:1,22:2,22:3,23:1,23:2,23:3,24:1,24:2,24:3,25:1,25:2,25:3,26:1,26:2,26:3,27:1,27:2,27:3,28:1,28:2,28:3]:
    V


### Specialization of cost equations fun/4 
* CE 15 is refined into CE [35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76] 
* CE 16 is refined into CE [77] 


### Cost equations --> "Loop" of fun/4 
* CEs [75] --> Loop 30 
* CEs [76] --> Loop 31 
* CEs [69] --> Loop 32 
* CEs [66] --> Loop 33 
* CEs [63] --> Loop 34 
* CEs [60] --> Loop 35 
* CEs [61,64,71,72,73] --> Loop 36 
* CEs [57] --> Loop 37 
* CEs [52] --> Loop 38 
* CEs [51,74] --> Loop 39 
* CEs [47] --> Loop 40 
* CEs [43] --> Loop 41 
* CEs [38] --> Loop 42 
* CEs [35,36,37,39,40,41,42,44,45,46,48,49,50,53,54,55,56,58,59,62,65,67,68,70,77] --> Loop 43 

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

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


### Specialization of cost equations fun1/2 
* CE 17 is refined into CE [78,79] 
* CE 18 is refined into CE [80] 


### Cost equations --> "Loop" of fun1/2 
* CEs [79] --> Loop 44 
* CEs [78] --> Loop 45 
* CEs [80] --> Loop 46 

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

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


### Specialization of cost equations start/3 
* CE 1 is refined into CE [81,82,83,84,85,86,87] 
* CE 2 is refined into CE [88,89] 
* CE 3 is refined into CE [90,91,92,93,94,95,96,97,98,99,100,101,102] 
* CE 4 is refined into CE [103,104,105] 


### Cost equations --> "Loop" of start/3 
* CEs [85] --> Loop 47 
* CEs [84] --> Loop 48 
* CEs [82] --> Loop 49 
* CEs [81,83,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105] --> Loop 50 

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

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


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

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

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

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

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

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

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

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

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


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

* Chain [multiple([21,22,23,24,25,26,27,28],[[29]])]: 2*it(24)+2*it(25)+1*s(12)+3*s(13)+1*s(14)+0
  Such that:aux(13) =< V
aux(14) =< 3/5*V
it(21) =< aux(13)
it(24) =< aux(13)
it(25) =< aux(13)
it(25) =< aux(14)
aux(6) =< aux(13)
s(15) =< it(21)*aux(13)
aux(7) =< it(21)*aux(6)
s(12) =< aux(7)*(1/2)
s(13) =< aux(7)
s(12) =< aux(7)
s(14) =< s(15)
s(12) =< s(15)
s(13) =< s(15)

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


#### Cost of chains of fun(V,V2,V4,Out):
* Chain [43]: 22*s(20)+22*s(21)+11*s(25)+33*s(26)+11*s(27)+20*s(64)+20*s(65)+10*s(69)+30*s(70)+10*s(71)+22*s(163)+22*s(164)+11*s(168)+33*s(169)+11*s(170)+1
  Such that:aux(15) =< V
aux(16) =< 3/5*V
aux(17) =< V2
aux(18) =< 3/5*V2
aux(19) =< V4
aux(20) =< 3/5*V4
s(163) =< aux(15)
s(164) =< aux(15)
s(164) =< aux(16)
s(165) =< aux(15)
s(166) =< aux(15)*aux(15)
s(167) =< aux(15)*s(165)
s(168) =< s(167)*(1/2)
s(169) =< s(167)
s(168) =< s(167)
s(170) =< s(166)
s(168) =< s(166)
s(169) =< s(166)
s(20) =< aux(19)
s(21) =< aux(19)
s(21) =< aux(20)
s(22) =< aux(19)
s(23) =< aux(19)*aux(19)
s(24) =< aux(19)*s(22)
s(25) =< s(24)*(1/2)
s(26) =< s(24)
s(25) =< s(24)
s(27) =< s(23)
s(25) =< s(23)
s(26) =< s(23)
s(64) =< aux(17)
s(65) =< aux(17)
s(65) =< aux(18)
s(66) =< aux(17)
s(67) =< aux(17)*aux(17)
s(68) =< aux(17)*s(66)
s(69) =< s(68)*(1/2)
s(70) =< s(68)
s(69) =< s(68)
s(71) =< s(67)
s(69) =< s(67)
s(70) =< s(67)

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

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

* Chain [41]: 2*s(372)+2*s(373)+1*s(377)+3*s(378)+1*s(379)+0
  Such that:s(369) =< V4
s(370) =< 3/5*V4
s(372) =< s(369)
s(373) =< s(369)
s(373) =< s(370)
s(374) =< s(369)
s(375) =< s(369)*s(369)
s(376) =< s(369)*s(374)
s(377) =< s(376)*(1/2)
s(378) =< s(376)
s(377) =< s(376)
s(379) =< s(375)
s(377) =< s(375)
s(378) =< s(375)

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

* Chain [40]: 2*s(383)+2*s(384)+1*s(388)+3*s(389)+1*s(390)+0
  Such that:s(380) =< V2
s(381) =< 3/5*V2
s(383) =< s(380)
s(384) =< s(380)
s(384) =< s(381)
s(385) =< s(380)
s(386) =< s(380)*s(380)
s(387) =< s(380)*s(385)
s(388) =< s(387)*(1/2)
s(389) =< s(387)
s(388) =< s(387)
s(390) =< s(386)
s(388) =< s(386)
s(389) =< s(386)

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

* Chain [39]: 4*s(394)+4*s(395)+2*s(399)+6*s(400)+2*s(401)+4*s(405)+4*s(406)+2*s(410)+6*s(411)+2*s(412)+2*s(416)+2*s(417)+1*s(421)+3*s(422)+1*s(423)+1
  Such that:s(413) =< V
s(414) =< 3/5*V
aux(21) =< V2
aux(22) =< 3/5*V2
aux(23) =< V4
aux(24) =< 3/5*V4
s(405) =< aux(23)
s(406) =< aux(23)
s(406) =< aux(24)
s(407) =< aux(23)
s(408) =< aux(23)*aux(23)
s(409) =< aux(23)*s(407)
s(410) =< s(409)*(1/2)
s(411) =< s(409)
s(410) =< s(409)
s(412) =< s(408)
s(410) =< s(408)
s(411) =< s(408)
s(394) =< aux(21)
s(395) =< aux(21)
s(395) =< aux(22)
s(396) =< aux(21)
s(397) =< aux(21)*aux(21)
s(398) =< aux(21)*s(396)
s(399) =< s(398)*(1/2)
s(400) =< s(398)
s(399) =< s(398)
s(401) =< s(397)
s(399) =< s(397)
s(400) =< s(397)
s(416) =< s(413)
s(417) =< s(413)
s(417) =< s(414)
s(418) =< s(413)
s(419) =< s(413)*s(413)
s(420) =< s(413)*s(418)
s(421) =< s(420)*(1/2)
s(422) =< s(420)
s(421) =< s(420)
s(423) =< s(419)
s(421) =< s(419)
s(422) =< s(419)

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

* Chain [38]: 2*s(449)+2*s(450)+1*s(454)+3*s(455)+1*s(456)+2*s(460)+2*s(461)+1*s(465)+3*s(466)+1*s(467)+0
  Such that:s(446) =< V2
s(447) =< 3/5*V2
s(457) =< V4
s(458) =< 3/5*V4
s(460) =< s(457)
s(461) =< s(457)
s(461) =< s(458)
s(462) =< s(457)
s(463) =< s(457)*s(457)
s(464) =< s(457)*s(462)
s(465) =< s(464)*(1/2)
s(466) =< s(464)
s(465) =< s(464)
s(467) =< s(463)
s(465) =< s(463)
s(466) =< s(463)
s(449) =< s(446)
s(450) =< s(446)
s(450) =< s(447)
s(451) =< s(446)
s(452) =< s(446)*s(446)
s(453) =< s(446)*s(451)
s(454) =< s(453)*(1/2)
s(455) =< s(453)
s(454) =< s(453)
s(456) =< s(452)
s(454) =< s(452)
s(455) =< s(452)

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

* Chain [37]: 2*s(471)+2*s(472)+1*s(476)+3*s(477)+1*s(478)+0
  Such that:s(468) =< V
s(469) =< 3/5*V
s(471) =< s(468)
s(472) =< s(468)
s(472) =< s(469)
s(473) =< s(468)
s(474) =< s(468)*s(468)
s(475) =< s(468)*s(473)
s(476) =< s(475)*(1/2)
s(477) =< s(475)
s(476) =< s(475)
s(478) =< s(474)
s(476) =< s(474)
s(477) =< s(474)

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

* Chain [36]: 11*s(482)+10*s(483)+5*s(487)+15*s(488)+5*s(489)+10*s(493)+10*s(494)+5*s(498)+15*s(499)+5*s(500)+1*s(523)+3*s(527)+6*s(543)+6*s(544)+3*s(548)+9*s(549)+3*s(550)+1
  Such that:aux(26) =< V+1
s(523) =< V/2+1/2
aux(27) =< V
aux(28) =< 3/5*V
aux(29) =< V2
aux(30) =< 3/5*V2
aux(31) =< V4
aux(32) =< 3/5*V4
s(493) =< aux(31)
s(494) =< aux(31)
s(494) =< aux(32)
s(495) =< aux(31)
s(496) =< aux(31)*aux(31)
s(497) =< aux(31)*s(495)
s(498) =< s(497)*(1/2)
s(499) =< s(497)
s(498) =< s(497)
s(500) =< s(496)
s(498) =< s(496)
s(499) =< s(496)
s(482) =< aux(27)
s(483) =< aux(27)
s(483) =< aux(28)
s(484) =< aux(27)
s(485) =< aux(27)*aux(27)
s(486) =< aux(27)*s(484)
s(487) =< s(486)*(1/2)
s(488) =< s(486)
s(487) =< s(486)
s(489) =< s(485)
s(487) =< s(485)
s(488) =< s(485)
s(543) =< aux(29)
s(544) =< aux(29)
s(544) =< aux(30)
s(545) =< aux(29)
s(546) =< aux(29)*aux(29)
s(547) =< aux(29)*s(545)
s(548) =< s(547)*(1/2)
s(549) =< s(547)
s(548) =< s(547)
s(550) =< s(546)
s(548) =< s(546)
s(549) =< s(546)
s(527) =< aux(26)
s(523) =< aux(26)
s(523) =< aux(27)

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

* Chain [35]: 2*s(631)+2*s(632)+1*s(636)+3*s(637)+1*s(638)+2*s(642)+2*s(643)+1*s(647)+3*s(648)+1*s(649)+1
  Such that:s(628) =< V
s(629) =< 3/5*V
s(639) =< V4
s(640) =< 3/5*V4
s(642) =< s(639)
s(643) =< s(639)
s(643) =< s(640)
s(644) =< s(639)
s(645) =< s(639)*s(639)
s(646) =< s(639)*s(644)
s(647) =< s(646)*(1/2)
s(648) =< s(646)
s(647) =< s(646)
s(649) =< s(645)
s(647) =< s(645)
s(648) =< s(645)
s(631) =< s(628)
s(632) =< s(628)
s(632) =< s(629)
s(633) =< s(628)
s(634) =< s(628)*s(628)
s(635) =< s(628)*s(633)
s(636) =< s(635)*(1/2)
s(637) =< s(635)
s(636) =< s(635)
s(638) =< s(634)
s(636) =< s(634)
s(637) =< s(634)

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

* Chain [34]: 2*s(653)+2*s(654)+1*s(658)+3*s(659)+1*s(660)+2*s(664)+2*s(665)+1*s(669)+3*s(670)+1*s(671)+0
  Such that:s(650) =< V
s(651) =< 3/5*V
s(661) =< V4
s(662) =< 3/5*V4
s(664) =< s(661)
s(665) =< s(661)
s(665) =< s(662)
s(666) =< s(661)
s(667) =< s(661)*s(661)
s(668) =< s(661)*s(666)
s(669) =< s(668)*(1/2)
s(670) =< s(668)
s(669) =< s(668)
s(671) =< s(667)
s(669) =< s(667)
s(670) =< s(667)
s(653) =< s(650)
s(654) =< s(650)
s(654) =< s(651)
s(655) =< s(650)
s(656) =< s(650)*s(650)
s(657) =< s(650)*s(655)
s(658) =< s(657)*(1/2)
s(659) =< s(657)
s(658) =< s(657)
s(660) =< s(656)
s(658) =< s(656)
s(659) =< s(656)

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

* Chain [33]: 2*s(675)+2*s(676)+1*s(680)+3*s(681)+1*s(682)+2*s(686)+2*s(687)+1*s(691)+3*s(692)+1*s(693)+1
  Such that:s(672) =< V
s(673) =< 3/5*V
s(683) =< V2
s(684) =< 3/5*V2
s(686) =< s(683)
s(687) =< s(683)
s(687) =< s(684)
s(688) =< s(683)
s(689) =< s(683)*s(683)
s(690) =< s(683)*s(688)
s(691) =< s(690)*(1/2)
s(692) =< s(690)
s(691) =< s(690)
s(693) =< s(689)
s(691) =< s(689)
s(692) =< s(689)
s(675) =< s(672)
s(676) =< s(672)
s(676) =< s(673)
s(677) =< s(672)
s(678) =< s(672)*s(672)
s(679) =< s(672)*s(677)
s(680) =< s(679)*(1/2)
s(681) =< s(679)
s(680) =< s(679)
s(682) =< s(678)
s(680) =< s(678)
s(681) =< s(678)

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

* Chain [32]: 2*s(697)+2*s(698)+1*s(702)+3*s(703)+1*s(704)+2*s(708)+2*s(709)+1*s(713)+3*s(714)+1*s(715)+0
  Such that:s(694) =< V
s(695) =< 3/5*V
s(705) =< V2
s(706) =< 3/5*V2
s(708) =< s(705)
s(709) =< s(705)
s(709) =< s(706)
s(710) =< s(705)
s(711) =< s(705)*s(705)
s(712) =< s(705)*s(710)
s(713) =< s(712)*(1/2)
s(714) =< s(712)
s(713) =< s(712)
s(715) =< s(711)
s(713) =< s(711)
s(714) =< s(711)
s(697) =< s(694)
s(698) =< s(694)
s(698) =< s(695)
s(699) =< s(694)
s(700) =< s(694)*s(694)
s(701) =< s(694)*s(699)
s(702) =< s(701)*(1/2)
s(703) =< s(701)
s(702) =< s(701)
s(704) =< s(700)
s(702) =< s(700)
s(703) =< s(700)

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

* Chain [31]: 2*s(719)+2*s(720)+1*s(724)+3*s(725)+1*s(726)+2*s(730)+2*s(731)+1*s(735)+3*s(736)+1*s(737)+2*s(741)+2*s(742)+1*s(746)+3*s(747)+1*s(748)+1*s(749)+3*s(753)+1*s(754)+0
  Such that:s(716) =< V
s(750) =< V+1
s(751) =< V+V2
s(752) =< V+V2+1
s(749) =< V/2+1/2
s(717) =< 3/5*V
s(727) =< V2
s(728) =< 3/5*V2
s(738) =< V4
s(739) =< 3/5*V4
s(753) =< s(750)
s(749) =< s(750)
s(754) =< s(751)
s(749) =< s(751)
s(753) =< s(752)
s(749) =< s(752)
s(741) =< s(738)
s(742) =< s(738)
s(742) =< s(739)
s(743) =< s(738)
s(744) =< s(738)*s(738)
s(745) =< s(738)*s(743)
s(746) =< s(745)*(1/2)
s(747) =< s(745)
s(746) =< s(745)
s(748) =< s(744)
s(746) =< s(744)
s(747) =< s(744)
s(730) =< s(727)
s(731) =< s(727)
s(731) =< s(728)
s(732) =< s(727)
s(733) =< s(727)*s(727)
s(734) =< s(727)*s(732)
s(735) =< s(734)*(1/2)
s(736) =< s(734)
s(735) =< s(734)
s(737) =< s(733)
s(735) =< s(733)
s(736) =< s(733)
s(719) =< s(716)
s(720) =< s(716)
s(720) =< s(717)
s(721) =< s(716)
s(722) =< s(716)*s(716)
s(723) =< s(716)*s(721)
s(724) =< s(723)*(1/2)
s(725) =< s(723)
s(724) =< s(723)
s(726) =< s(722)
s(724) =< s(722)
s(725) =< s(722)

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

* Chain [30]: 2*s(758)+2*s(759)+1*s(763)+3*s(764)+1*s(765)+2*s(769)+2*s(770)+1*s(774)+3*s(775)+1*s(776)+2*s(780)+2*s(781)+1*s(785)+3*s(786)+1*s(787)+0
  Such that:s(755) =< V
s(756) =< 3/5*V
s(766) =< V2
s(767) =< 3/5*V2
s(777) =< V4
s(778) =< 3/5*V4
s(780) =< s(777)
s(781) =< s(777)
s(781) =< s(778)
s(782) =< s(777)
s(783) =< s(777)*s(777)
s(784) =< s(777)*s(782)
s(785) =< s(784)*(1/2)
s(786) =< s(784)
s(785) =< s(784)
s(787) =< s(783)
s(785) =< s(783)
s(786) =< s(783)
s(769) =< s(766)
s(770) =< s(766)
s(770) =< s(767)
s(771) =< s(766)
s(772) =< s(766)*s(766)
s(773) =< s(766)*s(771)
s(774) =< s(773)*(1/2)
s(775) =< s(773)
s(774) =< s(773)
s(776) =< s(772)
s(774) =< s(772)
s(775) =< s(772)
s(758) =< s(755)
s(759) =< s(755)
s(759) =< s(756)
s(760) =< s(755)
s(761) =< s(755)*s(755)
s(762) =< s(755)*s(760)
s(763) =< s(762)*(1/2)
s(764) =< s(762)
s(763) =< s(762)
s(765) =< s(761)
s(763) =< s(761)
s(764) =< s(761)

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


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

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

* Chain [44]: 2*s(844)+2*s(845)+1*s(849)+3*s(850)+1*s(851)+0
  Such that:s(841) =< V
s(842) =< 3/5*V
s(844) =< s(841)
s(845) =< s(841)
s(845) =< s(842)
s(846) =< s(841)
s(847) =< s(841)*s(841)
s(848) =< s(841)*s(846)
s(849) =< s(848)*(1/2)
s(850) =< s(848)
s(849) =< s(848)
s(851) =< s(847)
s(849) =< s(847)
s(850) =< s(847)

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


#### Cost of chains of start(V,V2,V4):
* Chain [50]: 2*s(852)+6*s(856)+2*s(857)+53*s(861)+52*s(862)+26*s(866)+78*s(867)+26*s(868)+48*s(883)+48*s(884)+24*s(888)+72*s(889)+24*s(890)+42*s(891)+42*s(892)+21*s(896)+63*s(897)+21*s(898)+1*s(980)+3*s(1011)+1
  Such that:aux(37) =< V
aux(38) =< V+1
aux(39) =< V+V2
aux(40) =< V+V2+1
aux(41) =< V/2+1/2
aux(42) =< 3/5*V
aux(43) =< V2
aux(44) =< 3/5*V2
aux(45) =< V4
aux(46) =< 3/5*V4
s(852) =< aux(41)
s(980) =< aux(41)
s(861) =< aux(37)
s(862) =< aux(37)
s(862) =< aux(42)
s(863) =< aux(37)
s(864) =< aux(37)*aux(37)
s(865) =< aux(37)*s(863)
s(866) =< s(865)*(1/2)
s(867) =< s(865)
s(866) =< s(865)
s(868) =< s(864)
s(866) =< s(864)
s(867) =< s(864)
s(883) =< aux(45)
s(884) =< aux(45)
s(884) =< aux(46)
s(885) =< aux(45)
s(886) =< aux(45)*aux(45)
s(887) =< aux(45)*s(885)
s(888) =< s(887)*(1/2)
s(889) =< s(887)
s(888) =< s(887)
s(890) =< s(886)
s(888) =< s(886)
s(889) =< s(886)
s(891) =< aux(43)
s(892) =< aux(43)
s(892) =< aux(44)
s(893) =< aux(43)
s(894) =< aux(43)*aux(43)
s(895) =< aux(43)*s(893)
s(896) =< s(895)*(1/2)
s(897) =< s(895)
s(896) =< s(895)
s(898) =< s(894)
s(896) =< s(894)
s(897) =< s(894)
s(1011) =< aux(38)
s(980) =< aux(38)
s(980) =< aux(37)
s(856) =< aux(38)
s(852) =< aux(38)
s(857) =< aux(39)
s(852) =< aux(39)
s(856) =< aux(40)
s(852) =< aux(40)

  with precondition: [V>=0] 

* Chain [49]: 1
  with precondition: [V=V2,V>=0,V4>=0] 

* Chain [48]: 1
  with precondition: [V2+1=V4,V>=0,V2>=0] 

* Chain [47]: 1
  with precondition: [V2=V4,V>=0,V2>=0] 


Closed-form bounds of start(V,V2,V4): 
-------------------------------------
* Chain [50] with precondition: [V>=0] 
    - Upper bound: 105*V+1+117*V*V+nat(V2)*84+189/2*nat(V2)*nat(V2)+nat(V4)*96+nat(V4)*108*nat(V4)+nat(V+V2)*2+(9*V+9)+(3/2*V+3/2) 
    - Complexity: n^2 
* Chain [49] with precondition: [V=V2,V>=0,V4>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [48] with precondition: [V2+1=V4,V>=0,V2>=0] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [47] with precondition: [V2=V4,V>=0,V2>=0] 
    - Upper bound: 1 
    - Complexity: constant 

### Maximum cost of start(V,V2,V4): 117*V*V+105*V+nat(V2)*84+189/2*nat(V2)*nat(V2)+nat(V4)*96+nat(V4)*108*nat(V4)+nat(V+V2)*2+(9*V+9)+(3/2*V+3/2)+1 
Asymptotic class: n^2 
* Total analysis performed in 1870 ms.


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

(18)
BOUNDS(1, n^2)