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


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


WORST_CASE(?, O(n^1))
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^1).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 178 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, 1034 ms]
(18) BOUNDS(1, n^1)


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

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


The TRS R consists of the following rules:

   f(a, x) -> f(b, f(c, x))
   f(a, f(b, x)) -> f(b, f(a, x))
   f(d, f(c, x)) -> f(d, f(a, x))
   f(a, f(c, x)) -> f(c, f(a, x))

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(a) -> a
   encArg(b) -> b
   encArg(c) -> c
   encArg(d) -> d
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_a -> a
   encode_b -> b
   encode_c -> c
   encode_d -> d


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

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


The TRS R consists of the following rules:

   f(a, x) -> f(b, f(c, x))
   f(a, f(b, x)) -> f(b, f(a, x))
   f(d, f(c, x)) -> f(d, f(a, x))
   f(a, f(c, x)) -> f(c, f(a, x))

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

   encArg(a) -> a
   encArg(b) -> b
   encArg(c) -> c
   encArg(d) -> d
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_a -> a
   encode_b -> b
   encode_c -> c
   encode_d -> d

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^1).


The TRS R consists of the following rules:

   f(a, x) -> f(b, f(c, x))
   f(a, f(b, x)) -> f(b, f(a, x))
   f(d, f(c, x)) -> f(d, f(a, x))
   f(a, f(c, x)) -> f(c, f(a, x))

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

   encArg(a) -> a
   encArg(b) -> b
   encArg(c) -> c
   encArg(d) -> d
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_a -> a
   encode_b -> b
   encode_c -> c
   encode_d -> d

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^1).


The TRS R consists of the following rules:

   f(a, x) -> f(b, f(c, x))
   f(a, c_f(b, x)) -> f(b, f(a, x))
   f(d, c_f(c, x)) -> f(d, f(a, x))
   f(a, c_f(c, x)) -> f(c, f(a, x))

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

   encArg(a) -> a
   encArg(b) -> b
   encArg(c) -> c
   encArg(d) -> d
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_a -> a
   encode_b -> b
   encode_c -> c
   encode_d -> d
   f(x0, x1) -> c_f(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^1).


The TRS R consists of the following rules:

   f(a, x) -> f(b, f(c, x))
   f(a, c_f(b, x)) -> f(b, f(a, x))
   f(d, c_f(c, x)) -> f(d, f(a, x))
   f(a, c_f(c, x)) -> f(c, f(a, x))

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

   encArg(a) -> a
   encArg(b) -> b
   encArg(c) -> c
   encArg(d) -> d
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_a -> a
   encode_b -> b
   encode_c -> c
   encode_d -> d
   f(x0, x1) -> c_f(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^1).


The TRS R consists of the following rules:

   f(a, x) -> f(b, f(c, x)) [1]
   f(a, c_f(b, x)) -> f(b, f(a, x)) [1]
   f(d, c_f(c, x)) -> f(d, f(a, x)) [1]
   f(a, c_f(c, x)) -> f(c, f(a, x)) [1]
   encArg(a) -> a [0]
   encArg(b) -> b [0]
   encArg(c) -> c [0]
   encArg(d) -> d [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_a -> a [0]
   encode_b -> b [0]
   encode_c -> c [0]
   encode_d -> d [0]
   f(x0, x1) -> c_f(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:

   f(a, x) -> f(b, f(c, x)) [1]
   f(a, c_f(b, x)) -> f(b, f(a, x)) [1]
   f(d, c_f(c, x)) -> f(d, f(a, x)) [1]
   f(a, c_f(c, x)) -> f(c, f(a, x)) [1]
   encArg(a) -> a [0]
   encArg(b) -> b [0]
   encArg(c) -> c [0]
   encArg(d) -> d [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_a -> a [0]
   encode_b -> b [0]
   encode_c -> c [0]
   encode_d -> d [0]
   f(x0, x1) -> c_f(x0, x1) [0]

The TRS has the following type information:
f :: a:b:c:c_f:d:cons_f -> a:b:c:c_f:d:cons_f -> a:b:c:c_f:d:cons_f
a :: a:b:c:c_f:d:cons_f
b :: a:b:c:c_f:d:cons_f
c :: a:b:c:c_f:d:cons_f
c_f :: a:b:c:c_f:d:cons_f -> a:b:c:c_f:d:cons_f -> a:b:c:c_f:d:cons_f
d :: a:b:c:c_f:d:cons_f
encArg :: a:b:c:c_f:d:cons_f -> a:b:c:c_f:d:cons_f
cons_f :: a:b:c:c_f:d:cons_f -> a:b:c:c_f:d:cons_f -> a:b:c:c_f:d:cons_f
encode_f :: a:b:c:c_f:d:cons_f -> a:b:c:c_f:d:cons_f -> a:b:c:c_f:d:cons_f
encode_a :: a:b:c:c_f:d:cons_f
encode_b :: a:b:c:c_f:d:cons_f
encode_c :: a:b:c:c_f:d:cons_f
encode_d :: a:b:c:c_f:d: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) -> null_encode_f [0]
   encode_a -> null_encode_a [0]
   encode_b -> null_encode_b [0]
   encode_c -> null_encode_c [0]
   encode_d -> null_encode_d [0]
   f(v0, v1) -> null_f [0]

And the following fresh constants:    null_encArg, null_encode_f, null_encode_a, null_encode_b, null_encode_c, null_encode_d, 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(a, x) -> f(b, f(c, x)) [1]
   f(a, c_f(b, x)) -> f(b, f(a, x)) [1]
   f(d, c_f(c, x)) -> f(d, f(a, x)) [1]
   f(a, c_f(c, x)) -> f(c, f(a, x)) [1]
   encArg(a) -> a [0]
   encArg(b) -> b [0]
   encArg(c) -> c [0]
   encArg(d) -> d [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_a -> a [0]
   encode_b -> b [0]
   encode_c -> c [0]
   encode_d -> d [0]
   f(x0, x1) -> c_f(x0, x1) [0]
   encArg(v0) -> null_encArg [0]
   encode_f(v0, v1) -> null_encode_f [0]
   encode_a -> null_encode_a [0]
   encode_b -> null_encode_b [0]
   encode_c -> null_encode_c [0]
   encode_d -> null_encode_d [0]
   f(v0, v1) -> null_f [0]

The TRS has the following type information:
f :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f -> a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f -> a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
a :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
b :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
c :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
c_f :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f -> a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f -> a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
d :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
encArg :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f -> a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
cons_f :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f -> a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f -> a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
encode_f :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f -> a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f -> a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
encode_a :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
encode_b :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
encode_c :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
encode_d :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
null_encArg :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
null_encode_f :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
null_encode_a :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
null_encode_b :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
null_encode_c :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
null_encode_d :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d:null_f
null_f :: a:b:c:c_f:d:cons_f:null_encArg:null_encode_f:null_encode_a:null_encode_b:null_encode_c:null_encode_d: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:

   a => 0
   b => 1
   c => 2
   d => 3
   null_encArg => 0
   null_encode_f => 0
   null_encode_a => 0
   null_encode_b => 0
   null_encode_c => 0
   null_encode_d => 0
   null_f => 0

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

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

   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 3 :|: z = 3
   encArg(z) -{ 0 }-> 2 :|: z = 2
   encArg(z) -{ 0 }-> 1 :|: z = 1
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_c -{ 0 }-> 2 :|: 
   encode_c -{ 0 }-> 0 :|: 
   encode_d -{ 0 }-> 3 :|: 
   encode_d -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   f(z, z') -{ 1 }-> f(3, f(0, x)) :|: z' = 1 + 2 + x, z = 3, x >= 0
   f(z, z') -{ 1 }-> f(2, f(0, x)) :|: z' = 1 + 2 + x, x >= 0, z = 0
   f(z, z') -{ 1 }-> f(1, f(2, x)) :|: z' = x, x >= 0, z = 0
   f(z, z') -{ 1 }-> f(1, f(0, x)) :|: z' = 1 + 1 + x, x >= 0, z = 0
   f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   f(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1

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(V1, V),0,[f(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V),0,[encArg(V1, Out)],[V1 >= 0]).
eq(start(V1, V),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V),0,[fun1(Out)],[]).
eq(start(V1, V),0,[fun2(Out)],[]).
eq(start(V1, V),0,[fun3(Out)],[]).
eq(start(V1, V),0,[fun4(Out)],[]).
eq(f(V1, V, Out),1,[f(2, V2, Ret1),f(1, Ret1, Ret)],[Out = Ret,V = V2,V2 >= 0,V1 = 0]).
eq(f(V1, V, Out),1,[f(0, V3, Ret11),f(1, Ret11, Ret2)],[Out = Ret2,V = 2 + V3,V3 >= 0,V1 = 0]).
eq(f(V1, V, Out),1,[f(0, V4, Ret12),f(3, Ret12, Ret3)],[Out = Ret3,V = 3 + V4,V1 = 3,V4 >= 0]).
eq(f(V1, V, Out),1,[f(0, V5, Ret13),f(2, Ret13, Ret4)],[Out = Ret4,V = 3 + V5,V5 >= 0,V1 = 0]).
eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]).
eq(encArg(V1, Out),0,[],[Out = 1,V1 = 1]).
eq(encArg(V1, Out),0,[],[Out = 2,V1 = 2]).
eq(encArg(V1, Out),0,[],[Out = 3,V1 = 3]).
eq(encArg(V1, Out),0,[encArg(V7, Ret0),encArg(V6, Ret14),f(Ret0, Ret14, Ret5)],[Out = Ret5,V7 >= 0,V1 = 1 + V6 + V7,V6 >= 0]).
eq(fun(V1, V, Out),0,[encArg(V8, Ret01),encArg(V9, Ret15),f(Ret01, Ret15, Ret6)],[Out = Ret6,V8 >= 0,V9 >= 0,V1 = V8,V = V9]).
eq(fun1(Out),0,[],[Out = 0]).
eq(fun2(Out),0,[],[Out = 1]).
eq(fun3(Out),0,[],[Out = 2]).
eq(fun4(Out),0,[],[Out = 3]).
eq(f(V1, V, Out),0,[],[Out = 1 + V10 + V11,V1 = V11,V11 >= 0,V10 >= 0,V = V10]).
eq(encArg(V1, Out),0,[],[Out = 0,V12 >= 0,V1 = V12]).
eq(fun(V1, V, Out),0,[],[Out = 0,V14 >= 0,V13 >= 0,V1 = V14,V = V13]).
eq(fun2(Out),0,[],[Out = 0]).
eq(fun3(Out),0,[],[Out = 0]).
eq(fun4(Out),0,[],[Out = 0]).
eq(f(V1, V, Out),0,[],[Out = 0,V16 >= 0,V15 >= 0,V1 = V16,V = V15]).
input_output_vars(f(V1,V,Out),[V1,V],[Out]).
input_output_vars(encArg(V1,Out),[V1],[Out]).
input_output_vars(fun(V1,V,Out),[V1,V],[Out]).
input_output_vars(fun1(Out),[],[Out]).
input_output_vars(fun2(Out),[],[Out]).
input_output_vars(fun3(Out),[],[Out]).
input_output_vars(fun4(Out),[],[Out]).


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

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

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

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

### Specialization of cost equations f/3 
* CE 12 is refined into CE [27] 
* CE 13 is refined into CE [28] 
* CE 10 is refined into CE [29] 
* CE 8 is refined into CE [30] 
* CE 11 is refined into CE [31] 
* CE 9 is refined into CE [32] 


### Cost equations --> "Loop" of f/3 
* CEs [29] --> Loop 20 
* CEs [30] --> Loop 21 
* CEs [31] --> Loop 22 
* CEs [32] --> Loop 23 
* CEs [27] --> Loop 24 
* CEs [28] --> Loop 25 

### Ranking functions of CR f(V1,V,Out) 

#### Partial ranking functions of CR f(V1,V,Out) 
* Partial RF of phase [20]:
  - RF of loop [20:1]:
    V-2 depends on loops [20:2] 
    V1-2
* Partial RF of phase [22,23]:
  - RF of loop [22:1]:
    V-2 depends on loops [22:2,23:2] 
  - RF of loop [22:2]:
    -V1/2+1/2
  - RF of loop [23:1]:
    V-1 depends on loops [22:2,23:2] 
  - RF of loop [23:2]:
    -V1+1


### Specialization of cost equations encArg/2 
* CE 14 is refined into CE [33] 
* CE 17 is refined into CE [34] 
* CE 16 is refined into CE [35] 
* CE 15 is refined into CE [36] 
* CE 18 is refined into CE [37,38,39,40,41] 


### Cost equations --> "Loop" of encArg/2 
* CEs [41] --> Loop 26 
* CEs [40] --> Loop 27 
* CEs [38] --> Loop 28 
* CEs [37] --> Loop 29 
* CEs [39] --> Loop 30 
* CEs [33] --> Loop 31 
* CEs [34] --> Loop 32 
* CEs [35] --> Loop 33 
* CEs [36] --> Loop 34 

### Ranking functions of CR encArg(V1,Out) 
* RF of phase [26,27,28,29,30]: [V1]

#### Partial ranking functions of CR encArg(V1,Out) 
* Partial RF of phase [26,27,28,29,30]:
  - RF of loop [26:1,26:2,27:1,27:2,28:1,28:2,29:1,29:2,30:1,30:2]:
    V1


### Specialization of cost equations fun/3 
* CE 19 is refined into CE [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,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91] 
* CE 20 is refined into CE [92] 


### Cost equations --> "Loop" of fun/3 
* CEs [91] --> Loop 35 
* CEs [88] --> Loop 36 
* CEs [84] --> Loop 37 
* CEs [47,48,49,50,81,82,83] --> Loop 38 
* CEs [76] --> Loop 39 
* CEs [73] --> Loop 40 
* CEs [72] --> Loop 41 
* CEs [68,71] --> Loop 42 
* CEs [67,70,75] --> Loop 43 
* CEs [66] --> Loop 44 
* CEs [58,64] --> Loop 45 
* CEs [51,52,53,54,63,85,86,87] --> Loop 46 
* CEs [42,43,45,60,62,77,78,80] --> Loop 47 
* CEs [44,56,57,59,61,65,79,89,90,92] --> Loop 48 
* CEs [55] --> Loop 49 
* CEs [46,69,74] --> Loop 50 

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

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


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


### Cost equations --> "Loop" of fun2/1 
* CEs [93] --> Loop 51 
* CEs [94] --> Loop 52 

### Ranking functions of CR fun2(Out) 

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


### Specialization of cost equations fun3/1 
* CE 23 is refined into CE [95] 
* CE 24 is refined into CE [96] 


### Cost equations --> "Loop" of fun3/1 
* CEs [95] --> Loop 53 
* CEs [96] --> Loop 54 

### Ranking functions of CR fun3(Out) 

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


### Specialization of cost equations fun4/1 
* CE 25 is refined into CE [97] 
* CE 26 is refined into CE [98] 


### Cost equations --> "Loop" of fun4/1 
* CEs [97] --> Loop 55 
* CEs [98] --> Loop 56 

### Ranking functions of CR fun4(Out) 

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


### Specialization of cost equations start/2 
* CE 1 is refined into CE [99,100,101,102,103] 
* CE 2 is refined into CE [104,105,106,107] 
* CE 3 is refined into CE [108,109,110,111,112,113,114,115,116] 
* CE 4 is refined into CE [117] 
* CE 5 is refined into CE [118,119] 
* CE 6 is refined into CE [120,121] 
* CE 7 is refined into CE [122,123] 


### Cost equations --> "Loop" of start/2 
* CEs [99,100,101,102,104,105,106,107,108,109,110,111,112,113,114,117,118,119,120,121,122,123] --> Loop 57 
* CEs [115] --> Loop 58 
* CEs [103,116] --> Loop 59 

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

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


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

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

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

* Chain [multiple(21,[[25],[24]])]: 1
  with precondition: [V1=0,V>=0,Out>=0,V+5>=Out] 

* Chain [multiple([22,23],[[25],[24],[multiple(21,[[25],[24]])]])]: 1*it(22)+1*it(23)+1*it([multiple(21,[[25],[24]])])+0
  Such that:aux(9) =< 1
aux(10) =< -2*V1+1
aux(11) =< -V1+1
it(23) =< aux(10)
it([multiple(21,[[25],[24]])]) =< aux(10)
it(22) =< aux(11)
it([multiple(21,[[25],[24]])]) =< aux(11)
it([multiple(21,[[25],[24]])]) =< it(23)+it(22)+aux(9)

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

* Chain [multiple([20],[[],[multiple([22,23],[[25],[24],[multiple(21,[[25],[24]])]])],[25],[24],[multiple(21,[[25],[24]])]])]...: 1*it(20)+1*it([multiple(21,[[25],[24]])])+1*s(1)+0
  Such that:aux(17) =< -V1+1
it(20) =< 2/3*V1
aux(19) =< 1
aux(18) =< 1/2
s(5) =< it(20)+aux(17)
it([24]) =< it(20)+aux(19)
it([multiple(21,[[25],[24]])]) =< it(20)+aux(19)
s(5) =< it([24])*aux(18)
s(1) =< s(5)

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


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

* Chain [33]: 0
  with precondition: [V1=2,Out=2] 

* Chain [32]: 0
  with precondition: [V1=3,Out=3] 

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

* Chain [multiple([26,27,28,29,30],[[34],[33],[32],[31]])]: 3*it(29)+1*s(31)+1*s(32)+1*s(33)+1*s(38)+0
  Such that:aux(24) =< V1
it(29) =< aux(24)
s(31) =< aux(24)*2
s(38) =< aux(24)
s(38) =< it(29)+it(29)+aux(24)
s(17) =< 1/2
s(34) =< s(31)
s(35) =< s(31)+aux(24)
s(32) =< s(31)+aux(24)
s(34) =< s(35)*s(17)
s(33) =< s(34)

  with precondition: [V1>=1] 


#### Cost of chains of fun(V1,V,Out):
* Chain [50]...: 3*s(50)+1*s(51)+1*s(52)+1*s(56)+1*s(57)+6*s(59)+2*s(60)+2*s(61)+2*s(65)+2*s(66)+3*s(68)+3*s(73)+3*s(74)+0
  Such that:s(49) =< V1
aux(26) =< 1
aux(27) =< 2
aux(28) =< V
s(68) =< aux(27)
s(53) =< 1/2
s(71) =< s(68)
s(72) =< s(68)+aux(26)
s(73) =< s(68)+aux(26)
s(71) =< s(72)*s(53)
s(74) =< s(71)
s(59) =< aux(28)
s(60) =< aux(28)*2
s(61) =< aux(28)
s(61) =< s(59)+s(59)+aux(28)
s(63) =< s(60)
s(64) =< s(60)+aux(28)
s(65) =< s(60)+aux(28)
s(63) =< s(64)*s(53)
s(66) =< s(63)
s(50) =< s(49)
s(51) =< s(49)*2
s(52) =< s(49)
s(52) =< s(50)+s(50)+s(49)
s(54) =< s(51)
s(55) =< s(51)+s(49)
s(56) =< s(51)+s(49)
s(54) =< s(55)*s(53)
s(57) =< s(54)

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

* Chain [49]...: 3*s(101)+1*s(102)+1*s(103)+1*s(107)+1*s(108)+1*s(110)+1*s(115)+1*s(116)+0
  Such that:s(111) =< 1
s(110) =< 2
s(100) =< V1
s(104) =< 1/2
s(113) =< s(110)
s(114) =< s(110)+s(111)
s(115) =< s(110)+s(111)
s(113) =< s(114)*s(104)
s(116) =< s(113)
s(101) =< s(100)
s(102) =< s(100)*2
s(103) =< s(100)
s(103) =< s(101)+s(101)+s(100)
s(105) =< s(102)
s(106) =< s(102)+s(100)
s(107) =< s(102)+s(100)
s(105) =< s(106)*s(104)
s(108) =< s(105)

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

* Chain [48]: 9*s(118)+3*s(119)+3*s(120)+3*s(124)+3*s(125)+9*s(127)+3*s(128)+3*s(129)+3*s(133)+3*s(134)+1
  Such that:aux(29) =< V1
aux(30) =< V
s(127) =< aux(30)
s(128) =< aux(30)*2
s(129) =< aux(30)
s(129) =< s(127)+s(127)+aux(30)
s(121) =< 1/2
s(131) =< s(128)
s(132) =< s(128)+aux(30)
s(133) =< s(128)+aux(30)
s(131) =< s(132)*s(121)
s(134) =< s(131)
s(118) =< aux(29)
s(119) =< aux(29)*2
s(120) =< aux(29)
s(120) =< s(118)+s(118)+aux(29)
s(122) =< s(119)
s(123) =< s(119)+aux(29)
s(124) =< s(119)+aux(29)
s(122) =< s(123)*s(121)
s(125) =< s(122)

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

* Chain [47]: 9*s(172)+3*s(173)+3*s(174)+3*s(178)+3*s(179)+21*s(181)+7*s(182)+7*s(183)+7*s(187)+7*s(188)+4*s(210)+2*s(211)+1
  Such that:aux(33) =< 1
aux(34) =< V1
aux(35) =< V
s(181) =< aux(35)
s(182) =< aux(35)*2
s(183) =< aux(35)
s(183) =< s(181)+s(181)+aux(35)
s(175) =< 1/2
s(185) =< s(182)
s(186) =< s(182)+aux(35)
s(187) =< s(182)+aux(35)
s(185) =< s(186)*s(175)
s(188) =< s(185)
s(172) =< aux(34)
s(173) =< aux(34)*2
s(174) =< aux(34)
s(174) =< s(172)+s(172)+aux(34)
s(176) =< s(173)
s(177) =< s(173)+aux(34)
s(178) =< s(173)+aux(34)
s(176) =< s(177)*s(175)
s(179) =< s(176)
s(210) =< aux(33)
s(211) =< aux(33)
s(211) =< s(210)+s(210)+aux(33)

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

* Chain [46]: 12*s(274)+4*s(275)+4*s(276)+4*s(280)+4*s(281)+4*s(294)+2*s(295)+1
  Such that:aux(38) =< 1
aux(39) =< V1
s(294) =< aux(38)
s(295) =< aux(38)
s(295) =< s(294)+s(294)+aux(38)
s(274) =< aux(39)
s(275) =< aux(39)*2
s(276) =< aux(39)
s(276) =< s(274)+s(274)+aux(39)
s(277) =< 1/2
s(278) =< s(275)
s(279) =< s(275)+aux(39)
s(280) =< s(275)+aux(39)
s(278) =< s(279)*s(277)
s(281) =< s(278)

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

* Chain [45]: 3*s(322)+1*s(323)+1*s(324)+1*s(328)+1*s(329)+0
  Such that:s(321) =< V1
s(322) =< s(321)
s(323) =< s(321)*2
s(324) =< s(321)
s(324) =< s(322)+s(322)+s(321)
s(325) =< 1/2
s(326) =< s(323)
s(327) =< s(323)+s(321)
s(328) =< s(323)+s(321)
s(326) =< s(327)*s(325)
s(329) =< s(326)

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

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

* Chain [43]: 3*s(331)+1*s(332)+1*s(333)+1*s(337)+1*s(338)+0
  Such that:s(330) =< V
s(331) =< s(330)
s(332) =< s(330)*2
s(333) =< s(330)
s(333) =< s(331)+s(331)+s(330)
s(334) =< 1/2
s(335) =< s(332)
s(336) =< s(332)+s(330)
s(337) =< s(332)+s(330)
s(335) =< s(336)*s(334)
s(338) =< s(335)

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

* Chain [42]: 3*s(340)+1*s(341)+1*s(342)+1*s(346)+1*s(347)+0
  Such that:s(339) =< V
s(340) =< s(339)
s(341) =< s(339)*2
s(342) =< s(339)
s(342) =< s(340)+s(340)+s(339)
s(343) =< 1/2
s(344) =< s(341)
s(345) =< s(341)+s(339)
s(346) =< s(341)+s(339)
s(344) =< s(345)*s(343)
s(347) =< s(344)

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

* Chain [41]: 0
  with precondition: [V1=3,V=3,Out=0] 

* Chain [40]: 0
  with precondition: [V1=3,V=3,Out=7] 

* Chain [39]: 0
  with precondition: [V1=3,Out=4,V>=0] 

* Chain [38]: 12*s(349)+4*s(350)+4*s(351)+4*s(355)+4*s(356)+4*s(369)+2*s(370)+1
  Such that:aux(42) =< 1
aux(43) =< V1
s(369) =< aux(42)
s(370) =< aux(42)
s(370) =< s(369)+s(369)+aux(42)
s(349) =< aux(43)
s(350) =< aux(43)*2
s(351) =< aux(43)
s(351) =< s(349)+s(349)+aux(43)
s(352) =< 1/2
s(353) =< s(350)
s(354) =< s(350)+aux(43)
s(355) =< s(350)+aux(43)
s(353) =< s(354)*s(352)
s(356) =< s(353)

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

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

* Chain [36]: 0
  with precondition: [V=3,Out=4,V1>=0] 

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


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

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


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

* Chain [53]: 0
  with precondition: [Out=2] 


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

* Chain [55]: 0
  with precondition: [Out=3] 


#### Cost of chains of start(V1,V):
* Chain [59]...: 4*s(485)+4*s(490)+4*s(491)+6*s(502)+2*s(503)+2*s(504)+2*s(507)+2*s(508)+3*s(509)+1*s(510)+1*s(511)+1*s(514)+1*s(515)+0
  Such that:s(492) =< V1
s(495) =< V
aux(45) =< 1
aux(46) =< 2
s(485) =< aux(46)
s(487) =< 1/2
s(488) =< s(485)
s(489) =< s(485)+aux(45)
s(490) =< s(485)+aux(45)
s(488) =< s(489)*s(487)
s(491) =< s(488)
s(502) =< s(495)
s(503) =< s(495)*2
s(504) =< s(495)
s(504) =< s(502)+s(502)+s(495)
s(505) =< s(503)
s(506) =< s(503)+s(495)
s(507) =< s(503)+s(495)
s(505) =< s(506)*s(487)
s(508) =< s(505)
s(509) =< s(492)
s(510) =< s(492)*2
s(511) =< s(492)
s(511) =< s(509)+s(509)+s(492)
s(512) =< s(510)
s(513) =< s(510)+s(492)
s(514) =< s(510)+s(492)
s(512) =< s(513)*s(487)
s(515) =< s(512)

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

* Chain [58]...: 1*s(517)+1*s(522)+1*s(523)+3*s(524)+1*s(525)+1*s(526)+1*s(529)+1*s(530)+0
  Such that:s(516) =< 1
s(517) =< 2
s(518) =< V1
s(519) =< 1/2
s(520) =< s(517)
s(521) =< s(517)+s(516)
s(522) =< s(517)+s(516)
s(520) =< s(521)*s(519)
s(523) =< s(520)
s(524) =< s(518)
s(525) =< s(518)*2
s(526) =< s(518)
s(526) =< s(524)+s(524)+s(518)
s(527) =< s(525)
s(528) =< s(525)+s(518)
s(529) =< s(525)+s(518)
s(527) =< s(528)*s(519)
s(530) =< s(527)

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

* Chain [57]: 14*s(534)+7*s(535)+48*s(538)+16*s(539)+16*s(540)+16*s(544)+16*s(545)+36*s(548)+12*s(549)+12*s(550)+12*s(554)+12*s(555)+1
  Such that:aux(48) =< 1
aux(49) =< V1
aux(50) =< V
s(534) =< aux(48)
s(535) =< aux(48)
s(535) =< s(534)+s(534)+aux(48)
s(548) =< aux(50)
s(549) =< aux(50)*2
s(550) =< aux(50)
s(550) =< s(548)+s(548)+aux(50)
s(541) =< 1/2
s(552) =< s(549)
s(553) =< s(549)+aux(50)
s(554) =< s(549)+aux(50)
s(552) =< s(553)*s(541)
s(555) =< s(552)
s(538) =< aux(49)
s(539) =< aux(49)*2
s(540) =< aux(49)
s(540) =< s(538)+s(538)+aux(49)
s(542) =< s(539)
s(543) =< s(539)+aux(49)
s(544) =< s(539)+aux(49)
s(542) =< s(543)*s(541)
s(545) =< s(542)

  with precondition: [] 


Closed-form bounds of start(V1,V): 
-------------------------------------
* Chain [59]... with precondition: [V1>=1,V>=1] 
    - Upper bound: 11*V1+22*V+28 
    - Complexity: n 
* Chain [58]... with precondition: [V=3,V1>=1] 
    - Upper bound: 11*V1+7 
    - Complexity: n 
* Chain [57] with precondition: [] 
    - Upper bound: nat(V1)*176+22+nat(V)*132 
    - Complexity: n 

### Maximum cost of start(V1,V): nat(V)*22+15+max([6,nat(V)*110+nat(V1)*165])+(nat(V1)*11+7) 
Asymptotic class: n 
* Total analysis performed in 883 ms.


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

(18)
BOUNDS(1, n^1)