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


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

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


The TRS R consists of the following rules:

   f(X) -> if(X, c, n__f(true))
   if(true, X, Y) -> X
   if(false, X, Y) -> activate(Y)
   f(X) -> n__f(X)
   activate(n__f(X)) -> f(X)
   activate(X) -> X

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(c) -> c
   encArg(n__f(x_1)) -> n__f(encArg(x_1))
   encArg(true) -> true
   encArg(false) -> false
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_activate(x_1)) -> activate(encArg(x_1))
   encode_f(x_1) -> f(encArg(x_1))
   encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_c -> c
   encode_n__f(x_1) -> n__f(encArg(x_1))
   encode_true -> true
   encode_false -> false
   encode_activate(x_1) -> activate(encArg(x_1))


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

(2)
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(X) -> if(X, c, n__f(true))
   if(true, X, Y) -> X
   if(false, X, Y) -> activate(Y)
   f(X) -> n__f(X)
   activate(n__f(X)) -> f(X)
   activate(X) -> X

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

   encArg(c) -> c
   encArg(n__f(x_1)) -> n__f(encArg(x_1))
   encArg(true) -> true
   encArg(false) -> false
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_activate(x_1)) -> activate(encArg(x_1))
   encode_f(x_1) -> f(encArg(x_1))
   encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_c -> c
   encode_n__f(x_1) -> n__f(encArg(x_1))
   encode_true -> true
   encode_false -> false
   encode_activate(x_1) -> activate(encArg(x_1))

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


The TRS R consists of the following rules:

   f(X) -> if(X, c, n__f(true))
   if(true, X, Y) -> X
   if(false, X, Y) -> activate(Y)
   f(X) -> n__f(X)
   activate(n__f(X)) -> f(X)
   activate(X) -> X

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

   encArg(c) -> c
   encArg(n__f(x_1)) -> n__f(encArg(x_1))
   encArg(true) -> true
   encArg(false) -> false
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_activate(x_1)) -> activate(encArg(x_1))
   encode_f(x_1) -> f(encArg(x_1))
   encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_c -> c
   encode_n__f(x_1) -> n__f(encArg(x_1))
   encode_true -> true
   encode_false -> false
   encode_activate(x_1) -> activate(encArg(x_1))

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

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

(6)
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(X) -> if(X, c, n__f(true)) [1]
   if(true, X, Y) -> X [1]
   if(false, X, Y) -> activate(Y) [1]
   f(X) -> n__f(X) [1]
   activate(n__f(X)) -> f(X) [1]
   activate(X) -> X [1]
   encArg(c) -> c [0]
   encArg(n__f(x_1)) -> n__f(encArg(x_1)) [0]
   encArg(true) -> true [0]
   encArg(false) -> false [0]
   encArg(cons_f(x_1)) -> f(encArg(x_1)) [0]
   encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_activate(x_1)) -> activate(encArg(x_1)) [0]
   encode_f(x_1) -> f(encArg(x_1)) [0]
   encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_c -> c [0]
   encode_n__f(x_1) -> n__f(encArg(x_1)) [0]
   encode_true -> true [0]
   encode_false -> false [0]
   encode_activate(x_1) -> activate(encArg(x_1)) [0]

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

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

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

   f(X) -> if(X, c, n__f(true)) [1]
   if(true, X, Y) -> X [1]
   if(false, X, Y) -> activate(Y) [1]
   f(X) -> n__f(X) [1]
   activate(n__f(X)) -> f(X) [1]
   activate(X) -> X [1]
   encArg(c) -> c [0]
   encArg(n__f(x_1)) -> n__f(encArg(x_1)) [0]
   encArg(true) -> true [0]
   encArg(false) -> false [0]
   encArg(cons_f(x_1)) -> f(encArg(x_1)) [0]
   encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_activate(x_1)) -> activate(encArg(x_1)) [0]
   encode_f(x_1) -> f(encArg(x_1)) [0]
   encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_c -> c [0]
   encode_n__f(x_1) -> n__f(encArg(x_1)) [0]
   encode_true -> true [0]
   encode_false -> false [0]
   encode_activate(x_1) -> activate(encArg(x_1)) [0]

The TRS has the following type information:
f :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
if :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
c :: c:true:n__f:false:cons_f:cons_if:cons_activate
n__f :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
true :: c:true:n__f:false:cons_f:cons_if:cons_activate
false :: c:true:n__f:false:cons_f:cons_if:cons_activate
activate :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
encArg :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
cons_f :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
cons_if :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
cons_activate :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
encode_f :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
encode_if :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
encode_c :: c:true:n__f:false:cons_f:cons_if:cons_activate
encode_n__f :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate
encode_true :: c:true:n__f:false:cons_f:cons_if:cons_activate
encode_false :: c:true:n__f:false:cons_f:cons_if:cons_activate
encode_activate :: c:true:n__f:false:cons_f:cons_if:cons_activate -> c:true:n__f:false:cons_f:cons_if:cons_activate

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

(9) 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) -> null_encode_f [0]
   encode_if(v0, v1, v2) -> null_encode_if [0]
   encode_c -> null_encode_c [0]
   encode_n__f(v0) -> null_encode_n__f [0]
   encode_true -> null_encode_true [0]
   encode_false -> null_encode_false [0]
   encode_activate(v0) -> null_encode_activate [0]
   if(v0, v1, v2) -> null_if [0]

And the following fresh constants:    null_encArg, null_encode_f, null_encode_if, null_encode_c, null_encode_n__f, null_encode_true, null_encode_false, null_encode_activate, null_if

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

(10)
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) -> if(X, c, n__f(true)) [1]
   if(true, X, Y) -> X [1]
   if(false, X, Y) -> activate(Y) [1]
   f(X) -> n__f(X) [1]
   activate(n__f(X)) -> f(X) [1]
   activate(X) -> X [1]
   encArg(c) -> c [0]
   encArg(n__f(x_1)) -> n__f(encArg(x_1)) [0]
   encArg(true) -> true [0]
   encArg(false) -> false [0]
   encArg(cons_f(x_1)) -> f(encArg(x_1)) [0]
   encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_activate(x_1)) -> activate(encArg(x_1)) [0]
   encode_f(x_1) -> f(encArg(x_1)) [0]
   encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_c -> c [0]
   encode_n__f(x_1) -> n__f(encArg(x_1)) [0]
   encode_true -> true [0]
   encode_false -> false [0]
   encode_activate(x_1) -> activate(encArg(x_1)) [0]
   encArg(v0) -> null_encArg [0]
   encode_f(v0) -> null_encode_f [0]
   encode_if(v0, v1, v2) -> null_encode_if [0]
   encode_c -> null_encode_c [0]
   encode_n__f(v0) -> null_encode_n__f [0]
   encode_true -> null_encode_true [0]
   encode_false -> null_encode_false [0]
   encode_activate(v0) -> null_encode_activate [0]
   if(v0, v1, v2) -> null_if [0]

The TRS has the following type information:
f :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
if :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
c :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
n__f :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
true :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
false :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
activate :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
encArg :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
cons_f :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
cons_if :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
cons_activate :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
encode_f :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
encode_if :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
encode_c :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
encode_n__f :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
encode_true :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
encode_false :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
encode_activate :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if -> c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
null_encArg :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
null_encode_f :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
null_encode_if :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
null_encode_c :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
null_encode_n__f :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
null_encode_true :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
null_encode_false :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
null_encode_activate :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if
null_if :: c:true:n__f:false:cons_f:cons_if:cons_activate:null_encArg:null_encode_f:null_encode_if:null_encode_c:null_encode_n__f:null_encode_true:null_encode_false:null_encode_activate:null_if

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

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

   c => 0
   true => 2
   false => 1
   null_encArg => 0
   null_encode_f => 0
   null_encode_if => 0
   null_encode_c => 0
   null_encode_n__f => 0
   null_encode_true => 0
   null_encode_false => 0
   null_encode_activate => 0
   null_if => 0

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

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

   activate(z) -{ 1 }-> X :|: X >= 0, z = X
   activate(z) -{ 1 }-> f(X) :|: z = 1 + X, X >= 0
   encArg(z) -{ 0 }-> if(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 }-> f(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0
   encArg(z) -{ 0 }-> activate(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0
   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
   encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0
   encode_activate(z) -{ 0 }-> activate(encArg(x_1)) :|: x_1 >= 0, z = x_1
   encode_activate(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_c -{ 0 }-> 0 :|: 
   encode_f(z) -{ 0 }-> f(encArg(x_1)) :|: x_1 >= 0, z = x_1
   encode_f(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_false -{ 0 }-> 1 :|: 
   encode_false -{ 0 }-> 0 :|: 
   encode_if(z, z', z'') -{ 0 }-> if(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, x_3 >= 0, x_2 >= 0, z = x_1, z' = x_2, z'' = x_3
   encode_if(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   encode_n__f(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_n__f(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1
   encode_true -{ 0 }-> 2 :|: 
   encode_true -{ 0 }-> 0 :|: 
   f(z) -{ 1 }-> if(X, 0, 1 + 2) :|: X >= 0, z = X
   f(z) -{ 1 }-> 1 + X :|: X >= 0, z = X
   if(z, z', z'') -{ 1 }-> X :|: z = 2, z' = X, Y >= 0, z'' = Y, X >= 0
   if(z, z', z'') -{ 1 }-> activate(Y) :|: z' = X, Y >= 0, z = 1, z'' = Y, X >= 0
   if(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V, V1, V2),0,[f(V, Out)],[V >= 0]).
eq(start(V, V1, V2),0,[if(V, V1, V2, Out)],[V >= 0,V1 >= 0,V2 >= 0]).
eq(start(V, V1, V2),0,[activate(V, Out)],[V >= 0]).
eq(start(V, V1, V2),0,[encArg(V, Out)],[V >= 0]).
eq(start(V, V1, V2),0,[fun(V, Out)],[V >= 0]).
eq(start(V, V1, V2),0,[fun1(V, V1, V2, Out)],[V >= 0,V1 >= 0,V2 >= 0]).
eq(start(V, V1, V2),0,[fun2(Out)],[]).
eq(start(V, V1, V2),0,[fun3(V, Out)],[V >= 0]).
eq(start(V, V1, V2),0,[fun4(Out)],[]).
eq(start(V, V1, V2),0,[fun5(Out)],[]).
eq(start(V, V1, V2),0,[fun6(V, Out)],[V >= 0]).
eq(f(V, Out),1,[if(X1, 0, 1 + 2, Ret)],[Out = Ret,X1 >= 0,V = X1]).
eq(if(V, V1, V2, Out),1,[],[Out = X2,V = 2,V1 = X2,Y1 >= 0,V2 = Y1,X2 >= 0]).
eq(if(V, V1, V2, Out),1,[activate(Y2, Ret1)],[Out = Ret1,V1 = X3,Y2 >= 0,V = 1,V2 = Y2,X3 >= 0]).
eq(f(V, Out),1,[],[Out = 1 + X4,X4 >= 0,V = X4]).
eq(activate(V, Out),1,[f(X5, Ret2)],[Out = Ret2,V = 1 + X5,X5 >= 0]).
eq(activate(V, Out),1,[],[Out = X6,X6 >= 0,V = X6]).
eq(encArg(V, Out),0,[],[Out = 0,V = 0]).
eq(encArg(V, Out),0,[encArg(V3, Ret11)],[Out = 1 + Ret11,V = 1 + V3,V3 >= 0]).
eq(encArg(V, Out),0,[],[Out = 2,V = 2]).
eq(encArg(V, Out),0,[],[Out = 1,V = 1]).
eq(encArg(V, Out),0,[encArg(V4, Ret0),f(Ret0, Ret3)],[Out = Ret3,V = 1 + V4,V4 >= 0]).
eq(encArg(V, Out),0,[encArg(V6, Ret01),encArg(V7, Ret12),encArg(V5, Ret21),if(Ret01, Ret12, Ret21, Ret4)],[Out = Ret4,V6 >= 0,V = 1 + V5 + V6 + V7,V5 >= 0,V7 >= 0]).
eq(encArg(V, Out),0,[encArg(V8, Ret02),activate(Ret02, Ret5)],[Out = Ret5,V = 1 + V8,V8 >= 0]).
eq(fun(V, Out),0,[encArg(V9, Ret03),f(Ret03, Ret6)],[Out = Ret6,V9 >= 0,V = V9]).
eq(fun1(V, V1, V2, Out),0,[encArg(V12, Ret04),encArg(V11, Ret13),encArg(V10, Ret22),if(Ret04, Ret13, Ret22, Ret7)],[Out = Ret7,V12 >= 0,V10 >= 0,V11 >= 0,V = V12,V1 = V11,V2 = V10]).
eq(fun2(Out),0,[],[Out = 0]).
eq(fun3(V, Out),0,[encArg(V13, Ret14)],[Out = 1 + Ret14,V13 >= 0,V = V13]).
eq(fun4(Out),0,[],[Out = 2]).
eq(fun5(Out),0,[],[Out = 1]).
eq(fun6(V, Out),0,[encArg(V14, Ret05),activate(Ret05, Ret8)],[Out = Ret8,V14 >= 0,V = V14]).
eq(encArg(V, Out),0,[],[Out = 0,V15 >= 0,V = V15]).
eq(fun(V, Out),0,[],[Out = 0,V16 >= 0,V = V16]).
eq(fun1(V, V1, V2, Out),0,[],[Out = 0,V18 >= 0,V2 = V19,V17 >= 0,V = V18,V1 = V17,V19 >= 0]).
eq(fun3(V, Out),0,[],[Out = 0,V20 >= 0,V = V20]).
eq(fun4(Out),0,[],[Out = 0]).
eq(fun5(Out),0,[],[Out = 0]).
eq(fun6(V, Out),0,[],[Out = 0,V21 >= 0,V = V21]).
eq(if(V, V1, V2, Out),0,[],[Out = 0,V22 >= 0,V2 = V23,V24 >= 0,V = V22,V1 = V24,V23 >= 0]).
input_output_vars(f(V,Out),[V],[Out]).
input_output_vars(if(V,V1,V2,Out),[V,V1,V2],[Out]).
input_output_vars(activate(V,Out),[V],[Out]).
input_output_vars(encArg(V,Out),[V],[Out]).
input_output_vars(fun(V,Out),[V],[Out]).
input_output_vars(fun1(V,V1,V2,Out),[V,V1,V2],[Out]).
input_output_vars(fun2(Out),[],[Out]).
input_output_vars(fun3(V,Out),[V],[Out]).
input_output_vars(fun4(Out),[],[Out]).
input_output_vars(fun5(Out),[],[Out]).
input_output_vars(fun6(V,Out),[V],[Out]).


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

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

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

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

### Specialization of cost equations f/2 
* CE 18 is refined into CE [46] 
* CE 14 is refined into CE [47] 
* CE 15 is refined into CE [48] 
* CE 17 is refined into CE [49] 
* CE 16 is refined into CE [50] 


### Cost equations --> "Loop" of f/2 
* CEs [50] --> Loop 23 
* CEs [46] --> Loop 24 
* CEs [47,48] --> Loop 25 
* CEs [49] --> Loop 26 

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

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


### Specialization of cost equations encArg/2 
* CE 25 is refined into CE [51] 
* CE 27 is refined into CE [52] 
* CE 28 is refined into CE [53] 
* CE 26 is refined into CE [54] 
* CE 23 is refined into CE [55] 
* CE 24 is refined into CE [56,57,58] 
* CE 29 is refined into CE [59,60,61] 
* CE 20 is refined into CE [62] 
* CE 21 is refined into CE [63,64,65] 
* CE 22 is refined into CE [66] 
* CE 19 is refined into CE [67] 


### Cost equations --> "Loop" of encArg/2 
* CEs [62] --> Loop 27 
* CEs [65,66] --> Loop 28 
* CEs [64] --> Loop 29 
* CEs [63,67] --> Loop 30 
* CEs [55,58] --> Loop 31 
* CEs [54,57,61] --> Loop 32 
* CEs [60] --> Loop 33 
* CEs [56,59] --> Loop 34 
* CEs [51] --> Loop 35 
* CEs [52] --> Loop 36 
* CEs [53] --> Loop 37 

### Ranking functions of CR encArg(V,Out) 
* RF of phase [27,28,29,30,31,32,33,34]: [V]

#### Partial ranking functions of CR encArg(V,Out) 
* Partial RF of phase [27,28,29,30,31,32,33,34]:
  - RF of loop [27:1,27:2,27:3,28:1,28:2,28:3,29:1,29:2,29:3,30:1,30:2,30:3,31:1,32:1,33:1,34:1]:
    V


### Specialization of cost equations fun/2 
* CE 30 is refined into CE [68,69,70,71,72,73,74] 
* CE 31 is refined into CE [75] 


### Cost equations --> "Loop" of fun/2 
* CEs [74] --> Loop 38 
* CEs [69,70,72] --> Loop 39 
* CEs [68,71,73,75] --> Loop 40 

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

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


### Specialization of cost equations fun1/4 
* CE 32 is refined into CE [76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102] 
* CE 33 is refined into CE [103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120] 
* CE 34 is refined into CE [121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138] 
* CE 35 is refined into CE [139,140,141,142,143,144,145,146,147] 
* CE 36 is refined into CE [148] 


### Cost equations --> "Loop" of fun1/4 
* CEs [122,125,134,137] --> Loop 41 
* CEs [126,138,140,146] --> Loop 42 
* CEs [128,129,131,142] --> Loop 43 
* CEs [106,107,108,132,143] --> Loop 44 
* CEs [79,80,81,97,98,99,127,130,144] --> Loop 45 
* CEs [104,113,135,145] --> Loop 46 
* CEs [77,83,86,92,95,101,110,119,124,136] --> Loop 47 
* CEs [103,105,112,114,115,116,117,123,139] --> Loop 48 
* CEs [76,78,82,84,85,87,88,89,90,91,93,94,96,100,102,109,111,118,120,121,133,141,147,148] --> Loop 49 

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

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


### Specialization of cost equations fun3/2 
* CE 37 is refined into CE [149,150,151] 
* CE 38 is refined into CE [152] 


### Cost equations --> "Loop" of fun3/2 
* CEs [151] --> Loop 50 
* CEs [152] --> Loop 51 
* CEs [149,150] --> Loop 52 

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

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


### Specialization of cost equations fun4/1 
* CE 39 is refined into CE [153] 
* CE 40 is refined into CE [154] 


### Cost equations --> "Loop" of fun4/1 
* CEs [153] --> Loop 53 
* CEs [154] --> Loop 54 

### Ranking functions of CR fun4(Out) 

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


### Specialization of cost equations fun5/1 
* CE 41 is refined into CE [155] 
* CE 42 is refined into CE [156] 


### Cost equations --> "Loop" of fun5/1 
* CEs [155] --> Loop 55 
* CEs [156] --> Loop 56 

### Ranking functions of CR fun5(Out) 

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


### Specialization of cost equations fun6/2 
* CE 43 is refined into CE [157,158,159] 
* CE 44 is refined into CE [160,161,162,163,164,165] 
* CE 45 is refined into CE [166] 


### Cost equations --> "Loop" of fun6/2 
* CEs [161,164] --> Loop 57 
* CEs [157,158,162,165] --> Loop 58 
* CEs [159,160,163,166] --> Loop 59 

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

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


### Specialization of cost equations start/3 
* CE 1 is refined into CE [167] 
* CE 2 is refined into CE [168] 
* CE 3 is refined into CE [169,170,171] 
* CE 4 is refined into CE [172] 
* CE 5 is refined into CE [173,174,175] 
* CE 6 is refined into CE [176,177,178] 
* CE 7 is refined into CE [179,180,181] 
* CE 8 is refined into CE [182,183,184] 
* CE 9 is refined into CE [185,186,187,188,189,190] 
* CE 10 is refined into CE [191,192,193] 
* CE 11 is refined into CE [194,195] 
* CE 12 is refined into CE [196,197] 
* CE 13 is refined into CE [198,199] 


### Cost equations --> "Loop" of start/3 
* CEs [167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199] --> Loop 60 

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

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


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

#### Cost of chains of f(V,Out):
* Chain [26]: 3
  with precondition: [V=1,Out=3] 

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

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

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

* Chain [23,24]: 4
  with precondition: [V=1,Out=3] 


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

* Chain [36]: 0
  with precondition: [V=2,Out=2] 

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

* Chain [multiple([27,28,29,30,31,32,33,34],[[37],[36],[35]])]: 34*it(27)+0
  Such that:aux(1) =< V
it(27) =< aux(1)

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


#### Cost of chains of fun(V,Out):
* Chain [40]: 34*s(4)+5
  Such that:s(3) =< V
s(4) =< s(3)

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

* Chain [39]: 68*s(6)+4
  Such that:aux(3) =< V
s(6) =< aux(3)

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

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


#### Cost of chains of fun1(V,V1,V2,Out):
* Chain [49]: 340*s(10)+272*s(12)+374*s(14)+7
  Such that:aux(4) =< V
aux(5) =< V1
aux(6) =< V2
s(14) =< aux(6)
s(12) =< aux(5)
s(10) =< aux(4)

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

* Chain [48]: 136*s(68)+204*s(70)+170*s(72)+3
  Such that:aux(7) =< V
aux(8) =< V1
aux(9) =< V2
s(72) =< aux(9)
s(70) =< aux(8)
s(68) =< aux(7)

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

* Chain [47]: 170*s(98)+136*s(100)+7
  Such that:aux(10) =< V
aux(11) =< V1
s(100) =< aux(11)
s(98) =< aux(10)

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

* Chain [46]: 102*s(116)+68*s(118)+68*s(124)+3
  Such that:aux(12) =< V
aux(13) =< V1
aux(14) =< V2
s(118) =< aux(13)
s(116) =< aux(12)
s(124) =< aux(14)

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

* Chain [45]: 204*s(130)+102*s(132)+7
  Such that:aux(15) =< V
aux(16) =< V2
s(132) =< aux(16)
s(130) =< aux(15)

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

* Chain [44]: 170*s(148)+34*s(150)+3
  Such that:s(149) =< V2
aux(17) =< V
s(150) =< s(149)
s(148) =< aux(17)

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

* Chain [43]: 136*s(160)+102*s(162)+6
  Such that:aux(18) =< V
aux(19) =< V2
s(162) =< aux(19)
s(160) =< aux(18)

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

* Chain [42]: 136*s(174)+68*s(176)+3
  Such that:aux(20) =< V
aux(21) =< V1
s(176) =< aux(21)
s(174) =< aux(20)

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

* Chain [41]: 136*s(186)+68*s(188)+68*s(190)+6
  Such that:aux(22) =< V
aux(23) =< V1
aux(24) =< V2
s(190) =< aux(24)
s(188) =< aux(23)
s(186) =< aux(22)

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


#### Cost of chains of fun3(V,Out):
* Chain [52]: 34*s(232)+0
  Such that:s(231) =< V
s(232) =< s(231)

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

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

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


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

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


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

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


#### Cost of chains of fun6(V,Out):
* Chain [59]: 34*s(234)+6
  Such that:s(233) =< V
s(234) =< s(233)

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

* Chain [58]: 68*s(236)+2
  Such that:aux(31) =< V
s(236) =< aux(31)

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

* Chain [57]: 34*s(240)+5
  Such that:s(239) =< V
s(240) =< s(239)

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


#### Cost of chains of start(V,V1,V2):
* Chain [60]: 1836*s(246)+918*s(254)+816*s(256)+7
  Such that:aux(33) =< V
aux(34) =< V1
aux(35) =< V2
s(246) =< aux(33)
s(254) =< aux(35)
s(256) =< aux(34)

  with precondition: [] 


Closed-form bounds of start(V,V1,V2): 
-------------------------------------
* Chain [60] with precondition: [] 
    - Upper bound: nat(V)*1836+7+nat(V1)*816+nat(V2)*918 
    - Complexity: n 

### Maximum cost of start(V,V1,V2): nat(V)*1836+7+nat(V1)*816+nat(V2)*918 
Asymptotic class: n 
* Total analysis performed in 769 ms.


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

(14)
BOUNDS(1, n^1)