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), 160 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, 693 ms]
    (14) BOUNDS(1, n^2)
(15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(16) CpxRelTRS
    (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) typed CpxTrs
    (19) OrderProof [LOWER BOUND(ID), 0 ms]
    (20) typed CpxTrs
    (21) RewriteLemmaProof [LOWER BOUND(ID), 469 ms]
    (22) BEST
        (23) proven lower bound
            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
            (25) BOUNDS(n^1, INF)
        (26) typed CpxTrs
            (27) RewriteLemmaProof [LOWER BOUND(ID), 402 ms]
            (28) BOUNDS(1, INF)


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

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

   g(f(x, y), z) -> f(x, g(y, z))
   g(h(x, y), z) -> g(x, f(y, z))
   g(x, h(y, z)) -> h(g(x, y), z)

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

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

   encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))


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

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

   g(f(x, y), z) -> f(x, g(y, z))
   g(h(x, y), z) -> g(x, f(y, z))
   g(x, h(y, z)) -> h(g(x, y), z)

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

   encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))

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:

   g(f(x, y), z) -> f(x, g(y, z))
   g(h(x, y), z) -> g(x, f(y, z))
   g(x, h(y, z)) -> h(g(x, y), z)

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

   encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))

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:

   g(f(x, y), z) -> f(x, g(y, z)) [1]
   g(h(x, y), z) -> g(x, f(y, z)) [1]
   g(x, h(y, z)) -> h(g(x, y), z) [1]
   encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2)) [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:

   g(f(x, y), z) -> f(x, g(y, z)) [1]
   g(h(x, y), z) -> g(x, f(y, z)) [1]
   g(x, h(y, z)) -> h(g(x, y), z) [1]
   encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2)) [0]

The TRS has the following type information:
g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encArg :: f:h:cons_g -> f:h:cons_g
cons_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g

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_g(v0, v1) -> null_encode_g [0]
   encode_f(v0, v1) -> null_encode_f [0]
   encode_h(v0, v1) -> null_encode_h [0]
   g(v0, v1) -> null_g [0]

And the following fresh constants:    null_encArg, null_encode_g, null_encode_f, null_encode_h, null_g

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

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

   g(f(x, y), z) -> f(x, g(y, z)) [1]
   g(h(x, y), z) -> g(x, f(y, z)) [1]
   g(x, h(y, z)) -> h(g(x, y), z) [1]
   encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2)) [0]
   encArg(v0) -> null_encArg [0]
   encode_g(v0, v1) -> null_encode_g [0]
   encode_f(v0, v1) -> null_encode_f [0]
   encode_h(v0, v1) -> null_encode_h [0]
   g(v0, v1) -> null_g [0]

The TRS has the following type information:
g :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
f :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
h :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
encArg :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
cons_g :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
encode_g :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
encode_f :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
encode_h :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g -> f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
null_encArg :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
null_encode_g :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
null_encode_f :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
null_encode_h :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g
null_g :: f:h:cons_g:null_encArg:null_encode_g:null_encode_f:null_encode_h:null_g

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:

   null_encArg => 0
   null_encode_g => 0
   null_encode_f => 0
   null_encode_h => 0
   null_g => 0

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

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

   encArg(z') -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2
   encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encArg(z') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2
   encode_f(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   encode_f(z', z'') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2
   encode_g(z', z'') -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2
   encode_g(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   encode_h(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   encode_h(z', z'') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2
   g(z', z'') -{ 1 }-> g(x, 1 + y + z) :|: z'' = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0
   g(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   g(z', z'') -{ 1 }-> 1 + x + g(y, z) :|: z'' = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0
   g(z', z'') -{ 1 }-> 1 + g(x, y) + z :|: z >= 0, z' = x, x >= 0, y >= 0, z'' = 1 + y + 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),0,[g(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1),0,[encArg(V, Out)],[V >= 0]).
eq(start(V, V1),0,[fun(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1),0,[fun1(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1),0,[fun2(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(g(V, V1, Out),1,[g(V2, V4, Ret1)],[Out = 1 + Ret1 + V3,V1 = V4,V4 >= 0,V = 1 + V2 + V3,V3 >= 0,V2 >= 0]).
eq(g(V, V1, Out),1,[g(V5, 1 + V7 + V6, Ret)],[Out = Ret,V1 = V6,V6 >= 0,V = 1 + V5 + V7,V5 >= 0,V7 >= 0]).
eq(g(V, V1, Out),1,[g(V9, V8, Ret01)],[Out = 1 + Ret01 + V10,V10 >= 0,V = V9,V9 >= 0,V8 >= 0,V1 = 1 + V10 + V8]).
eq(encArg(V, Out),0,[encArg(V12, Ret011),encArg(V11, Ret11)],[Out = 1 + Ret011 + Ret11,V12 >= 0,V11 >= 0,V = 1 + V11 + V12]).
eq(encArg(V, Out),0,[encArg(V13, Ret0),encArg(V14, Ret12),g(Ret0, Ret12, Ret2)],[Out = Ret2,V13 >= 0,V14 >= 0,V = 1 + V13 + V14]).
eq(fun(V, V1, Out),0,[encArg(V16, Ret02),encArg(V15, Ret13),g(Ret02, Ret13, Ret3)],[Out = Ret3,V16 >= 0,V = V16,V15 >= 0,V1 = V15]).
eq(fun1(V, V1, Out),0,[encArg(V18, Ret012),encArg(V17, Ret14)],[Out = 1 + Ret012 + Ret14,V18 >= 0,V = V18,V17 >= 0,V1 = V17]).
eq(fun2(V, V1, Out),0,[encArg(V20, Ret013),encArg(V19, Ret15)],[Out = 1 + Ret013 + Ret15,V20 >= 0,V = V20,V19 >= 0,V1 = V19]).
eq(encArg(V, Out),0,[],[Out = 0,V21 >= 0,V = V21]).
eq(fun(V, V1, Out),0,[],[Out = 0,V23 >= 0,V22 >= 0,V1 = V22,V = V23]).
eq(fun1(V, V1, Out),0,[],[Out = 0,V25 >= 0,V24 >= 0,V1 = V24,V = V25]).
eq(fun2(V, V1, Out),0,[],[Out = 0,V26 >= 0,V27 >= 0,V1 = V27,V = V26]).
eq(g(V, V1, Out),0,[],[Out = 0,V28 >= 0,V29 >= 0,V1 = V29,V = V28]).
input_output_vars(g(V,V1,Out),[V,V1],[Out]).
input_output_vars(encArg(V,Out),[V],[Out]).
input_output_vars(fun(V,V1,Out),[V,V1],[Out]).
input_output_vars(fun1(V,V1,Out),[V,V1],[Out]).
input_output_vars(fun2(V,V1,Out),[V,V1],[Out]).


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

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

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

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

### Specialization of cost equations g/3 
* CE 9 is refined into CE [19] 
* CE 7 is refined into CE [20] 
* CE 6 is refined into CE [21] 
* CE 8 is refined into CE [22] 


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

### Ranking functions of CR g(V,V1,Out) 
* RF of phase [11,12,13]: [2*V+V1]

#### Partial ranking functions of CR g(V,V1,Out) 
* Partial RF of phase [11,12,13]:
  - RF of loop [11:1,12:1]:
    V
  - RF of loop [13:1]:
    V1 depends on loops [11:1] 


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


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

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

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


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


### Cost equations --> "Loop" of fun/3 
* CEs [33] --> Loop 19 
* CEs [31] --> Loop 20 
* CEs [29] --> Loop 21 
* CEs [27,28,30,32,34] --> Loop 22 

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

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


### Specialization of cost equations fun1/3 
* CE 15 is refined into CE [35,36,37,38] 
* CE 16 is refined into CE [39] 


### Cost equations --> "Loop" of fun1/3 
* CEs [38] --> Loop 23 
* CEs [37] --> Loop 24 
* CEs [36] --> Loop 25 
* CEs [35] --> Loop 26 
* CEs [39] --> Loop 27 

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

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


### Specialization of cost equations fun2/3 
* CE 17 is refined into CE [40,41,42,43] 
* CE 18 is refined into CE [44] 


### Cost equations --> "Loop" of fun2/3 
* CEs [43] --> Loop 28 
* CEs [42] --> Loop 29 
* CEs [41] --> Loop 30 
* CEs [40] --> Loop 31 
* CEs [44] --> Loop 32 

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

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


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


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

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

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


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

#### Cost of chains of g(V,V1,Out):
* Chain [[11,12,13],14]: 2*it(11)+1*it(13)+0
  Such that:aux(9) =< V+Out
aux(8) =< 2*V+V1
aux(10) =< V
aux(11) =< V1
it(11) =< aux(10)
it(11) =< aux(8)
it(13) =< aux(8)
it(11) =< aux(9)
it(13) =< aux(9)
it(13) =< aux(10)+aux(11)

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

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


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

* Chain [multiple([15,16,17],[[18]])]: 2*s(12)+1*s(13)+0
  Such that:it([18]) =< V+1
aux(17) =< V
aux(18) =< 2/3*V
it(15) =< aux(18)
aux(16) =< aux(17)-1
aux(15) =< aux(17)*2
it(15) =< it([18])*(1/3)+aux(18)
s(14) =< it(15)*aux(16)
s(16) =< it(15)*aux(15)
s(15) =< it(15)*aux(17)
s(12) =< s(15)
s(12) =< s(16)
s(13) =< s(16)
s(13) =< s(15)+s(14)

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


#### Cost of chains of fun(V,V1,Out):
* Chain [22]: 4*s(26)+2*s(27)+4*s(37)+2*s(38)+0
  Such that:aux(19) =< V
aux(20) =< V+1
aux(21) =< 2/3*V
aux(22) =< V1
aux(23) =< V1+1
aux(24) =< 2/3*V1
s(31) =< aux(21)
s(32) =< aux(19)-1
s(33) =< aux(19)*2
s(31) =< aux(20)*(1/3)+aux(21)
s(34) =< s(31)*s(32)
s(35) =< s(31)*s(33)
s(36) =< s(31)*aux(19)
s(37) =< s(36)
s(37) =< s(35)
s(38) =< s(35)
s(38) =< s(36)+s(34)
s(20) =< aux(24)
s(21) =< aux(22)-1
s(22) =< aux(22)*2
s(20) =< aux(23)*(1/3)+aux(24)
s(23) =< s(20)*s(21)
s(24) =< s(20)*s(22)
s(25) =< s(20)*aux(22)
s(26) =< s(25)
s(26) =< s(24)
s(27) =< s(24)
s(27) =< s(25)+s(23)

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

* Chain [21]: 2*s(70)+1*s(71)+1*s(77)+0
  Such that:s(61) =< V1+1
s(63) =< 2/3*V1
aux(25) =< V1
s(77) =< aux(25)
s(77) =< aux(25)
s(64) =< s(63)
s(65) =< aux(25)-1
s(66) =< aux(25)*2
s(64) =< s(61)*(1/3)+s(63)
s(67) =< s(64)*s(65)
s(68) =< s(64)*s(66)
s(69) =< s(64)*aux(25)
s(70) =< s(69)
s(70) =< s(68)
s(71) =< s(68)
s(71) =< s(69)+s(67)

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

* Chain [20]: 2*s(87)+1*s(88)+2*s(93)+1*s(94)+0
  Such that:s(78) =< V+1
s(80) =< 2/3*V
aux(26) =< V
aux(27) =< 2*V
s(93) =< aux(26)
s(93) =< aux(27)
s(94) =< aux(27)
s(94) =< aux(26)
s(81) =< s(80)
s(82) =< aux(26)-1
s(83) =< aux(26)*2
s(81) =< s(78)*(1/3)+s(80)
s(84) =< s(81)*s(82)
s(85) =< s(81)*s(83)
s(86) =< s(81)*aux(26)
s(87) =< s(86)
s(87) =< s(85)
s(88) =< s(85)
s(88) =< s(86)+s(84)

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

* Chain [19]: 2*s(104)+1*s(105)+2*s(115)+1*s(116)+2*s(121)+1*s(122)+0
  Such that:s(95) =< V+1
s(97) =< 2/3*V
s(106) =< V1+1
s(108) =< 2/3*V1
aux(28) =< V
aux(29) =< 2*V+V1
aux(30) =< V1
s(121) =< aux(28)
s(121) =< aux(29)
s(122) =< aux(29)
s(122) =< aux(28)+aux(30)
s(109) =< s(108)
s(110) =< aux(30)-1
s(111) =< aux(30)*2
s(109) =< s(106)*(1/3)+s(108)
s(112) =< s(109)*s(110)
s(113) =< s(109)*s(111)
s(114) =< s(109)*aux(30)
s(115) =< s(114)
s(115) =< s(113)
s(116) =< s(113)
s(116) =< s(114)+s(112)
s(98) =< s(97)
s(99) =< aux(28)-1
s(100) =< aux(28)*2
s(98) =< s(95)*(1/3)+s(97)
s(101) =< s(98)*s(99)
s(102) =< s(98)*s(100)
s(103) =< s(98)*aux(28)
s(104) =< s(103)
s(104) =< s(102)
s(105) =< s(102)
s(105) =< s(103)+s(101)

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


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

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

* Chain [25]: 2*s(132)+1*s(133)+0
  Such that:s(124) =< V1
s(123) =< V1+1
s(125) =< 2/3*V1
s(126) =< s(125)
s(127) =< s(124)-1
s(128) =< s(124)*2
s(126) =< s(123)*(1/3)+s(125)
s(129) =< s(126)*s(127)
s(130) =< s(126)*s(128)
s(131) =< s(126)*s(124)
s(132) =< s(131)
s(132) =< s(130)
s(133) =< s(130)
s(133) =< s(131)+s(129)

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

* Chain [24]: 2*s(143)+1*s(144)+0
  Such that:s(135) =< V
s(134) =< V+1
s(136) =< 2/3*V
s(137) =< s(136)
s(138) =< s(135)-1
s(139) =< s(135)*2
s(137) =< s(134)*(1/3)+s(136)
s(140) =< s(137)*s(138)
s(141) =< s(137)*s(139)
s(142) =< s(137)*s(135)
s(143) =< s(142)
s(143) =< s(141)
s(144) =< s(141)
s(144) =< s(142)+s(140)

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

* Chain [23]: 2*s(154)+1*s(155)+2*s(165)+1*s(166)+0
  Such that:s(146) =< V
s(145) =< V+1
s(147) =< 2/3*V
s(157) =< V1
s(156) =< V1+1
s(158) =< 2/3*V1
s(159) =< s(158)
s(160) =< s(157)-1
s(161) =< s(157)*2
s(159) =< s(156)*(1/3)+s(158)
s(162) =< s(159)*s(160)
s(163) =< s(159)*s(161)
s(164) =< s(159)*s(157)
s(165) =< s(164)
s(165) =< s(163)
s(166) =< s(163)
s(166) =< s(164)+s(162)
s(148) =< s(147)
s(149) =< s(146)-1
s(150) =< s(146)*2
s(148) =< s(145)*(1/3)+s(147)
s(151) =< s(148)*s(149)
s(152) =< s(148)*s(150)
s(153) =< s(148)*s(146)
s(154) =< s(153)
s(154) =< s(152)
s(155) =< s(152)
s(155) =< s(153)+s(151)

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


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

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

* Chain [30]: 2*s(176)+1*s(177)+0
  Such that:s(168) =< V1
s(167) =< V1+1
s(169) =< 2/3*V1
s(170) =< s(169)
s(171) =< s(168)-1
s(172) =< s(168)*2
s(170) =< s(167)*(1/3)+s(169)
s(173) =< s(170)*s(171)
s(174) =< s(170)*s(172)
s(175) =< s(170)*s(168)
s(176) =< s(175)
s(176) =< s(174)
s(177) =< s(174)
s(177) =< s(175)+s(173)

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

* Chain [29]: 2*s(187)+1*s(188)+0
  Such that:s(179) =< V
s(178) =< V+1
s(180) =< 2/3*V
s(181) =< s(180)
s(182) =< s(179)-1
s(183) =< s(179)*2
s(181) =< s(178)*(1/3)+s(180)
s(184) =< s(181)*s(182)
s(185) =< s(181)*s(183)
s(186) =< s(181)*s(179)
s(187) =< s(186)
s(187) =< s(185)
s(188) =< s(185)
s(188) =< s(186)+s(184)

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

* Chain [28]: 2*s(198)+1*s(199)+2*s(209)+1*s(210)+0
  Such that:s(190) =< V
s(189) =< V+1
s(191) =< 2/3*V
s(201) =< V1
s(200) =< V1+1
s(202) =< 2/3*V1
s(203) =< s(202)
s(204) =< s(201)-1
s(205) =< s(201)*2
s(203) =< s(200)*(1/3)+s(202)
s(206) =< s(203)*s(204)
s(207) =< s(203)*s(205)
s(208) =< s(203)*s(201)
s(209) =< s(208)
s(209) =< s(207)
s(210) =< s(207)
s(210) =< s(208)+s(206)
s(192) =< s(191)
s(193) =< s(190)-1
s(194) =< s(190)*2
s(192) =< s(189)*(1/3)+s(191)
s(195) =< s(192)*s(193)
s(196) =< s(192)*s(194)
s(197) =< s(192)*s(190)
s(198) =< s(197)
s(198) =< s(196)
s(199) =< s(196)
s(199) =< s(197)+s(195)

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


#### Cost of chains of start(V,V1):
* Chain [33]: 4*s(215)+2*s(216)+18*s(226)+9*s(227)+16*s(248)+8*s(249)+1*s(253)+3*s(266)+0
  Such that:s(265) =< 2*V
aux(32) =< V
aux(33) =< V+1
aux(34) =< 2*V+V1
aux(35) =< 2/3*V
aux(36) =< V1
aux(37) =< V1+1
aux(38) =< 2/3*V1
s(215) =< aux(32)
s(215) =< aux(34)
s(216) =< aux(34)
s(216) =< aux(32)+aux(36)
s(220) =< aux(35)
s(221) =< aux(32)-1
s(222) =< aux(32)*2
s(220) =< aux(33)*(1/3)+aux(35)
s(223) =< s(220)*s(221)
s(224) =< s(220)*s(222)
s(225) =< s(220)*aux(32)
s(226) =< s(225)
s(226) =< s(224)
s(227) =< s(224)
s(227) =< s(225)+s(223)
s(242) =< aux(38)
s(243) =< aux(36)-1
s(244) =< aux(36)*2
s(242) =< aux(37)*(1/3)+aux(38)
s(245) =< s(242)*s(243)
s(246) =< s(242)*s(244)
s(247) =< s(242)*aux(36)
s(248) =< s(247)
s(248) =< s(246)
s(249) =< s(246)
s(249) =< s(247)+s(245)
s(266) =< aux(32)
s(266) =< s(265)
s(253) =< aux(36)

  with precondition: [V>=0] 


Closed-form bounds of start(V,V1): 
-------------------------------------
* Chain [33] with precondition: [V>=0] 
    - Upper bound: 2/3*V*(36*V)+7*V+nat(V1)+nat(V1)*32*nat(2/3*V1)+nat(2*V+V1)*2 
    - Complexity: n^2 

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


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

(14)
BOUNDS(1, n^2)

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

(15) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

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


The TRS R consists of the following rules:

   g(f(x, y), z) -> f(x, g(y, z))
   g(h(x, y), z) -> g(x, f(y, z))
   g(x, h(y, z)) -> h(g(x, y), z)

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

   encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))

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

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

(18)
Obligation:
Innermost TRS:
Rules:
g(f(x, y), z) -> f(x, g(y, z))
g(h(x, y), z) -> g(x, f(y, z))
g(x, h(y, z)) -> h(g(x, y), z)
encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))

Types:
g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encArg :: f:h:cons_g -> f:h:cons_g
cons_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
hole_f:h:cons_g1_0 :: f:h:cons_g
gen_f:h:cons_g2_0 :: Nat -> f:h:cons_g

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

(19) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
g, encArg

They will be analysed ascendingly in the following order:
g < encArg

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

(20)
Obligation:
Innermost TRS:
Rules:
g(f(x, y), z) -> f(x, g(y, z))
g(h(x, y), z) -> g(x, f(y, z))
g(x, h(y, z)) -> h(g(x, y), z)
encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))

Types:
g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encArg :: f:h:cons_g -> f:h:cons_g
cons_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
hole_f:h:cons_g1_0 :: f:h:cons_g
gen_f:h:cons_g2_0 :: Nat -> f:h:cons_g


Generator Equations:
gen_f:h:cons_g2_0(0) <=> hole_f:h:cons_g1_0
gen_f:h:cons_g2_0(+(x, 1)) <=> f(hole_f:h:cons_g1_0, gen_f:h:cons_g2_0(x))


The following defined symbols remain to be analysed:
g, encArg

They will be analysed ascendingly in the following order:
g < encArg

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

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
g(gen_f:h:cons_g2_0(+(1, n4_0)), gen_f:h:cons_g2_0(b)) -> *3_0, rt in Omega(n4_0)

Induction Base:
g(gen_f:h:cons_g2_0(+(1, 0)), gen_f:h:cons_g2_0(b))

Induction Step:
g(gen_f:h:cons_g2_0(+(1, +(n4_0, 1))), gen_f:h:cons_g2_0(b)) ->_R^Omega(1)
f(hole_f:h:cons_g1_0, g(gen_f:h:cons_g2_0(+(1, n4_0)), gen_f:h:cons_g2_0(b))) ->_IH
f(hole_f:h:cons_g1_0, *3_0)

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(22)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
g(f(x, y), z) -> f(x, g(y, z))
g(h(x, y), z) -> g(x, f(y, z))
g(x, h(y, z)) -> h(g(x, y), z)
encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))

Types:
g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encArg :: f:h:cons_g -> f:h:cons_g
cons_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
hole_f:h:cons_g1_0 :: f:h:cons_g
gen_f:h:cons_g2_0 :: Nat -> f:h:cons_g


Generator Equations:
gen_f:h:cons_g2_0(0) <=> hole_f:h:cons_g1_0
gen_f:h:cons_g2_0(+(x, 1)) <=> f(hole_f:h:cons_g1_0, gen_f:h:cons_g2_0(x))


The following defined symbols remain to be analysed:
g, encArg

They will be analysed ascendingly in the following order:
g < encArg

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

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

(25)
BOUNDS(n^1, INF)

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

(26)
Obligation:
Innermost TRS:
Rules:
g(f(x, y), z) -> f(x, g(y, z))
g(h(x, y), z) -> g(x, f(y, z))
g(x, h(y, z)) -> h(g(x, y), z)
encArg(f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))

Types:
g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encArg :: f:h:cons_g -> f:h:cons_g
cons_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_g :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_f :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
encode_h :: f:h:cons_g -> f:h:cons_g -> f:h:cons_g
hole_f:h:cons_g1_0 :: f:h:cons_g
gen_f:h:cons_g2_0 :: Nat -> f:h:cons_g


Lemmas:
g(gen_f:h:cons_g2_0(+(1, n4_0)), gen_f:h:cons_g2_0(b)) -> *3_0, rt in Omega(n4_0)


Generator Equations:
gen_f:h:cons_g2_0(0) <=> hole_f:h:cons_g1_0
gen_f:h:cons_g2_0(+(x, 1)) <=> f(hole_f:h:cons_g1_0, gen_f:h:cons_g2_0(x))


The following defined symbols remain to be analysed:
encArg
----------------------------------------

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_f:h:cons_g2_0(+(1, n1237_0))) -> *3_0, rt in Omega(0)

Induction Base:
encArg(gen_f:h:cons_g2_0(+(1, 0)))

Induction Step:
encArg(gen_f:h:cons_g2_0(+(1, +(n1237_0, 1)))) ->_R^Omega(0)
f(encArg(hole_f:h:cons_g1_0), encArg(gen_f:h:cons_g2_0(+(1, n1237_0)))) ->_IH
f(encArg(hole_f:h:cons_g1_0), *3_0)

We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0).
----------------------------------------

(28)
BOUNDS(1, INF)