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


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


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


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

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 149 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, 464 ms]
    (14) BOUNDS(1, n^2)
(15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(16) TRS for Loop Detection
    (17) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (18) BEST
        (19) proven lower bound
            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
            (21) BOUNDS(n^1, INF)
        (22) TRS for Loop Detection


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

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


The TRS R consists of the following rules:

   f(0, 1, x) -> f(s(x), x, x)
   f(x, y, s(z)) -> s(f(0, 1, z))

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

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))


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

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


The TRS R consists of the following rules:

   f(0, 1, x) -> f(s(x), x, x)
   f(x, y, s(z)) -> s(f(0, 1, z))

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(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(n^1, n^2).


The TRS R consists of the following rules:

   f(0, 1, x) -> f(s(x), x, x)
   f(x, y, s(z)) -> s(f(0, 1, z))

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(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^2).


The TRS R consists of the following rules:

   f(0, 1, x) -> f(s(x), x, x) [1]
   f(x, y, s(z)) -> s(f(0, 1, z)) [1]
   encArg(0) -> 0 [0]
   encArg(1) -> 1 [0]
   encArg(s(x_1)) -> s(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_0 -> 0 [0]
   encode_1 -> 1 [0]
   encode_s(x_1) -> s(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(0, 1, x) -> f(s(x), x, x) [1]
   f(x, y, s(z)) -> s(f(0, 1, z)) [1]
   encArg(0) -> 0 [0]
   encArg(1) -> 1 [0]
   encArg(s(x_1)) -> s(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_0 -> 0 [0]
   encode_1 -> 1 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]

The TRS has the following type information:
f :: 0:1:s:cons_f -> 0:1:s:cons_f -> 0:1:s:cons_f -> 0:1:s:cons_f
0 :: 0:1:s:cons_f
1 :: 0:1:s:cons_f
s :: 0:1:s:cons_f -> 0:1:s:cons_f
encArg :: 0:1:s:cons_f -> 0:1:s:cons_f
cons_f :: 0:1:s:cons_f -> 0:1:s:cons_f -> 0:1:s:cons_f -> 0:1:s:cons_f
encode_f :: 0:1:s:cons_f -> 0:1:s:cons_f -> 0:1:s:cons_f -> 0:1:s:cons_f
encode_0 :: 0:1:s:cons_f
encode_1 :: 0:1:s:cons_f
encode_s :: 0:1:s:cons_f -> 0:1:s:cons_f

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, v1, v2) -> null_encode_f [0]
   encode_0 -> null_encode_0 [0]
   encode_1 -> null_encode_1 [0]
   encode_s(v0) -> null_encode_s [0]
   f(v0, v1, v2) -> null_f [0]

And the following fresh constants:    null_encArg, null_encode_f, null_encode_0, null_encode_1, null_encode_s, null_f

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

(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(0, 1, x) -> f(s(x), x, x) [1]
   f(x, y, s(z)) -> s(f(0, 1, z)) [1]
   encArg(0) -> 0 [0]
   encArg(1) -> 1 [0]
   encArg(s(x_1)) -> s(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_0 -> 0 [0]
   encode_1 -> 1 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encArg(v0) -> null_encArg [0]
   encode_f(v0, v1, v2) -> null_encode_f [0]
   encode_0 -> null_encode_0 [0]
   encode_1 -> null_encode_1 [0]
   encode_s(v0) -> null_encode_s [0]
   f(v0, v1, v2) -> null_f [0]

The TRS has the following type information:
f :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
0 :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
1 :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
s :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
encArg :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
cons_f :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
encode_f :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
encode_0 :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
encode_1 :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
encode_s :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f -> 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
null_encArg :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
null_encode_f :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
null_encode_0 :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
null_encode_1 :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
null_encode_s :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f
null_f :: 0:1:s:cons_f:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_s:null_f

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:

   0 => 0
   1 => 1
   null_encArg => 0
   null_encode_f => 0
   null_encode_0 => 0
   null_encode_1 => 0
   null_encode_s => 0
   null_f => 0

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

(12)
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 }-> 1 :|: z' = 1
   encArg(z') -{ 0 }-> 0 :|: z' = 0
   encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encArg(z') -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z' = 1 + x_1
   encode_0 -{ 0 }-> 0 :|: 
   encode_1 -{ 0 }-> 1 :|: 
   encode_1 -{ 0 }-> 0 :|: 
   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_s(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encode_s(z') -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z' = x_1
   f(z', z'', z1) -{ 1 }-> f(1 + x, x, x) :|: x >= 0, z'' = 1, z1 = x, z' = 0
   f(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0
   f(z', z'', z1) -{ 1 }-> 1 + f(0, 1, z) :|: z >= 0, z' = x, z'' = y, x >= 0, y >= 0, z1 = 1 + z

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


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

#### Computed strongly connected components 
0. recursive  : [f/4]
1. recursive [non_tail,multiple] : [encArg/2]
2. non_recursive  : [fun/4]
3. non_recursive  : [fun1/1]
4. non_recursive  : [fun2/1]
5. non_recursive  : [fun3/2]
6. 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 completely evaluated into other SCCs
4. SCC is partially evaluated into fun2/1
5. SCC is partially evaluated into fun3/2
6. SCC is partially evaluated into start/3

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

### Specialization of cost equations f/4 
* CE 9 is refined into CE [20] 
* CE 8 is refined into CE [21] 
* CE 7 is refined into CE [22] 


### Cost equations --> "Loop" of f/4 
* CEs [21] --> Loop 13 
* CEs [22] --> Loop 14 
* CEs [20] --> Loop 15 

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

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


### Specialization of cost equations encArg/2 
* CE 10 is refined into CE [23] 
* CE 11 is refined into CE [24] 
* CE 13 is refined into CE [25,26] 
* CE 12 is refined into CE [27] 


### Cost equations --> "Loop" of encArg/2 
* CEs [27] --> Loop 16 
* CEs [26] --> Loop 17 
* CEs [25] --> Loop 18 
* CEs [23] --> Loop 19 
* CEs [24] --> Loop 20 

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

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


### Specialization of cost equations fun/4 
* CE 14 is refined into CE [28,29,30,31,32,33,34,35,36,37,38,39,40,41] 
* CE 15 is refined into CE [42] 


### Cost equations --> "Loop" of fun/4 
* CEs [29,36] --> Loop 21 
* CEs [33,40] --> Loop 22 
* CEs [28,30,31,32,34,35,37,38,39,41,42] --> Loop 23 

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

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


### Specialization of cost equations fun2/1 
* CE 16 is refined into CE [43] 
* CE 17 is refined into CE [44] 


### Cost equations --> "Loop" of fun2/1 
* CEs [43] --> Loop 24 
* CEs [44] --> Loop 25 

### Ranking functions of CR fun2(Out) 

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


### Specialization of cost equations fun3/2 
* CE 18 is refined into CE [45,46] 
* CE 19 is refined into CE [47] 


### Cost equations --> "Loop" of fun3/2 
* CEs [45] --> Loop 26 
* CEs [46] --> Loop 27 
* CEs [47] --> Loop 28 

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

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


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


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

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

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


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

#### Cost of chains of f(V,V1,V3,Out):
* Chain [[13,14],15]: 1*it(13)+1*it(14)+0
  Such that:aux(2) =< -V+1
aux(4) =< -V/2+V1/2
aux(7) =< V3
aux(8) =< Out
aux(5) =< aux(7)
it(13) =< aux(7)
aux(5) =< aux(8)
it(13) =< aux(8)
aux(3) =< aux(5)*(1/2)
it(14) =< aux(3)+aux(4)
it(14) =< aux(5)+aux(2)

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

* Chain [15]: 0
  with precondition: [Out=0,V>=0,V1>=0,V3>=0] 


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

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

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

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


#### Cost of chains of fun(V,V1,V3,Out):
* Chain [23]: 5*s(35)+5*s(37)+6*s(43)+6*s(45)+4*s(51)+4*s(53)+2*s(93)+0
  Such that:aux(23) =< 1
aux(24) =< V
aux(25) =< V/2
aux(26) =< V1
aux(27) =< V1/2
aux(28) =< V3
aux(29) =< V3/2
s(93) =< aux(27)
s(93) =< aux(23)
s(40) =< aux(27)*2
s(41) =< aux(26)*aux(27)
s(42) =< aux(26)*s(40)
s(43) =< s(42)
s(44) =< s(42)*(1/2)
s(45) =< s(44)+s(41)
s(45) =< s(42)+aux(26)
s(32) =< aux(25)*2
s(33) =< aux(24)*aux(25)
s(34) =< aux(24)*s(32)
s(35) =< s(34)
s(36) =< s(34)*(1/2)
s(37) =< s(36)+s(33)
s(37) =< s(34)+aux(24)
s(48) =< aux(29)*2
s(49) =< aux(28)*aux(29)
s(50) =< aux(28)*s(48)
s(51) =< s(50)
s(52) =< s(50)*(1/2)
s(53) =< s(52)+s(49)
s(53) =< s(50)+aux(28)

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

* Chain [22]: 1*s(171)+1*s(173)+2*s(179)+2*s(181)+2*s(187)+2*s(189)+0
  Such that:s(166) =< V
s(167) =< V/2
aux(32) =< 1
aux(33) =< V3
aux(34) =< V3/2
s(187) =< aux(33)
s(188) =< aux(33)*(1/2)
s(189) =< s(188)
s(189) =< aux(33)+aux(32)
s(176) =< aux(34)*2
s(177) =< aux(33)*aux(34)
s(178) =< aux(33)*s(176)
s(179) =< s(178)
s(180) =< s(178)*(1/2)
s(181) =< s(180)+s(177)
s(181) =< s(178)+aux(33)
s(168) =< s(167)*2
s(169) =< s(166)*s(167)
s(170) =< s(166)*s(168)
s(171) =< s(170)
s(172) =< s(170)*(1/2)
s(173) =< s(172)+s(169)
s(173) =< s(170)+s(166)

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

* Chain [21]: 1*s(211)+1*s(213)+2*s(219)+2*s(221)+2*s(227)+2*s(229)+2*s(235)+2*s(237)+0
  Such that:s(206) =< V
s(207) =< V/2
aux(39) =< 1
aux(40) =< V1
aux(41) =< V1/2
aux(42) =< V3
aux(43) =< V3/2
s(235) =< aux(42)
s(236) =< aux(42)*(1/2)
s(237) =< s(236)+aux(41)
s(237) =< aux(42)+aux(39)
s(224) =< aux(43)*2
s(225) =< aux(42)*aux(43)
s(226) =< aux(42)*s(224)
s(227) =< s(226)
s(228) =< s(226)*(1/2)
s(229) =< s(228)+s(225)
s(229) =< s(226)+aux(42)
s(216) =< aux(41)*2
s(217) =< aux(40)*aux(41)
s(218) =< aux(40)*s(216)
s(219) =< s(218)
s(220) =< s(218)*(1/2)
s(221) =< s(220)+s(217)
s(221) =< s(218)+aux(40)
s(208) =< s(207)*2
s(209) =< s(206)*s(207)
s(210) =< s(206)*s(208)
s(211) =< s(210)
s(212) =< s(210)*(1/2)
s(213) =< s(212)+s(209)
s(213) =< s(210)+s(206)

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


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

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


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

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

* Chain [26]: 1*s(267)+1*s(269)+0
  Such that:s(262) =< V
s(263) =< V/2
s(264) =< s(263)*2
s(265) =< s(262)*s(263)
s(266) =< s(262)*s(264)
s(267) =< s(266)
s(268) =< s(266)*(1/2)
s(269) =< s(268)+s(265)
s(269) =< s(266)+s(262)

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


#### Cost of chains of start(V,V1,V3):
* Chain [29]: 5*s(275)+1*s(277)+9*s(283)+9*s(285)+2*s(293)+8*s(297)+8*s(299)+8*s(309)+8*s(311)+2*s(319)+2*s(341)+0
  Such that:s(270) =< -V+1
s(271) =< -V/2+V1/2
aux(45) =< 1
aux(46) =< V
aux(47) =< V/2
aux(48) =< V1
aux(49) =< V1/2
aux(50) =< V3
aux(51) =< V3/2
s(293) =< aux(49)
s(293) =< aux(45)
s(294) =< aux(49)*2
s(295) =< aux(48)*aux(49)
s(296) =< aux(48)*s(294)
s(297) =< s(296)
s(298) =< s(296)*(1/2)
s(299) =< s(298)+s(295)
s(299) =< s(296)+aux(48)
s(280) =< aux(47)*2
s(281) =< aux(46)*aux(47)
s(282) =< aux(46)*s(280)
s(283) =< s(282)
s(284) =< s(282)*(1/2)
s(285) =< s(284)+s(281)
s(285) =< s(282)+aux(46)
s(306) =< aux(51)*2
s(307) =< aux(50)*aux(51)
s(308) =< aux(50)*s(306)
s(309) =< s(308)
s(310) =< s(308)*(1/2)
s(311) =< s(310)+s(307)
s(311) =< s(308)+aux(50)
s(275) =< aux(50)
s(276) =< aux(50)*(1/2)
s(319) =< s(276)
s(319) =< aux(50)+aux(45)
s(341) =< s(276)+aux(49)
s(341) =< aux(50)+aux(45)
s(277) =< s(276)+s(271)
s(277) =< aux(50)+s(270)

  with precondition: [] 


Closed-form bounds of start(V,V1,V3): 
-------------------------------------
* Chain [29] with precondition: [] 
    - Upper bound: nat(V)*36*nat(V/2)+2+nat(V1)*32*nat(V1/2)+15/2*nat(V3)+nat(V3)*32*nat(V3/2)+nat(-V/2+V1/2)+nat(V1/2)*2 
    - Complexity: n^2 

### Maximum cost of start(V,V1,V3): nat(V)*36*nat(V/2)+2+nat(V1)*32*nat(V1/2)+15/2*nat(V3)+nat(V3)*32*nat(V3/2)+nat(-V/2+V1/2)+nat(V1/2)*2 
Asymptotic class: n^2 
* Total analysis performed in 577 ms.


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

(14)
BOUNDS(1, n^2)

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

(15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

(16)
Obligation:
Analyzing the following TRS for decreasing loops:

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


The TRS R consists of the following rules:

   f(0, 1, x) -> f(s(x), x, x)
   f(x, y, s(z)) -> s(f(0, 1, z))

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))

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

(17) DecreasingLoopProof (LOWER BOUND(ID))
The following loop(s) give(s) rise to the lower bound Omega(n^1):

The rewrite sequence

f(x, y, s(z)) ->^+ s(f(0, 1, z))

gives rise to a decreasing loop by considering the right hand sides subterm at position [0].

The pumping substitution is [z / s(z)].

The result substitution is [x / 0, y / 1].




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

(18)
Complex Obligation (BEST)

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

(19)
Obligation:
Proved the lower bound n^1 for the following obligation:

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


The TRS R consists of the following rules:

   f(0, 1, x) -> f(s(x), x, x)
   f(x, y, s(z)) -> s(f(0, 1, z))

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))

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

(20) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(21)
BOUNDS(n^1, INF)

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

(22)
Obligation:
Analyzing the following TRS for decreasing loops:

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


The TRS R consists of the following rules:

   f(0, 1, x) -> f(s(x), x, x)
   f(x, y, s(z)) -> s(f(0, 1, z))

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))

Rewrite Strategy: INNERMOST