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


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


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

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 146 ms]
(4) CpxRelTRS
(5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
(6) CpxRelTRS
    (7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxWeightedTrs
    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CpxTypedWeightedTrs
    (11) CompletionProof [UPPER BOUND(ID), 0 ms]
    (12) CpxTypedWeightedCompleteTrs
    (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (14) CpxRNTS
    (15) CompleteCoflocoProof [FINISHED, 603 ms]
    (16) BOUNDS(1, n^2)
(17) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(18) CpxRelTRS
    (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (20) typed CpxTrs
    (21) OrderProof [LOWER BOUND(ID), 0 ms]
    (22) typed CpxTrs
    (23) RewriteLemmaProof [LOWER BOUND(ID), 265 ms]
    (24) BEST
        (25) proven lower bound
            (26) LowerBoundPropagationProof [FINISHED, 0 ms]
            (27) BOUNDS(n^1, INF)
        (28) typed CpxTrs
            (29) RewriteLemmaProof [LOWER BOUND(ID), 20 ms]
            (30) 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:

   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   ++(++(x, y), z) -> ++(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(nil) -> nil
   encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2))
   encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_.(x_1, x_2) -> .(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:

   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   ++(++(x, y), z) -> ++(x, ++(y, z))

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

   encArg(nil) -> nil
   encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2))
   encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_.(x_1, x_2) -> .(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:

   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   ++(++(x, y), z) -> ++(x, ++(y, z))

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

   encArg(nil) -> nil
   encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2))
   encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2))

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

(5) NonCtorToCtorProof (UPPER BOUND(ID))
transformed non-ctor to ctor-system
----------------------------------------

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


The TRS R consists of the following rules:

   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   ++(c_++(x, y), z) -> ++(x, ++(y, z))

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

   encArg(nil) -> nil
   encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2))
   encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2))
   ++(x0, x1) -> c_++(x0, x1)

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

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

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

   ++(nil, y) -> y [1]
   ++(x, nil) -> x [1]
   ++(.(x, y), z) -> .(x, ++(y, z)) [1]
   ++(c_++(x, y), z) -> ++(x, ++(y, z)) [1]
   encArg(nil) -> nil [0]
   encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0]
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) [0]
   encode_nil -> nil [0]
   encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0]
   ++(x0, x1) -> c_++(x0, x1) [0]

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

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

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

   ++(nil, y) -> y [1]
   ++(x, nil) -> x [1]
   ++(.(x, y), z) -> .(x, ++(y, z)) [1]
   ++(c_++(x, y), z) -> ++(x, ++(y, z)) [1]
   encArg(nil) -> nil [0]
   encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0]
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) [0]
   encode_nil -> nil [0]
   encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0]
   ++(x0, x1) -> c_++(x0, x1) [0]

The TRS has the following type information:
++ :: nil:.:c_++:cons_++ -> nil:.:c_++:cons_++ -> nil:.:c_++:cons_++
nil :: nil:.:c_++:cons_++
. :: nil:.:c_++:cons_++ -> nil:.:c_++:cons_++ -> nil:.:c_++:cons_++
c_++ :: nil:.:c_++:cons_++ -> nil:.:c_++:cons_++ -> nil:.:c_++:cons_++
encArg :: nil:.:c_++:cons_++ -> nil:.:c_++:cons_++
cons_++ :: nil:.:c_++:cons_++ -> nil:.:c_++:cons_++ -> nil:.:c_++:cons_++
encode_++ :: nil:.:c_++:cons_++ -> nil:.:c_++:cons_++ -> nil:.:c_++:cons_++
encode_nil :: nil:.:c_++:cons_++
encode_. :: nil:.:c_++:cons_++ -> nil:.:c_++:cons_++ -> nil:.:c_++:cons_++

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

(11) 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_++(v0, v1) -> null_encode_++ [0]
   encode_nil -> null_encode_nil [0]
   encode_.(v0, v1) -> null_encode_. [0]
   ++(v0, v1) -> null_++ [0]

And the following fresh constants:    null_encArg, null_encode_++, null_encode_nil, null_encode_., null_++

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

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

   ++(nil, y) -> y [1]
   ++(x, nil) -> x [1]
   ++(.(x, y), z) -> .(x, ++(y, z)) [1]
   ++(c_++(x, y), z) -> ++(x, ++(y, z)) [1]
   encArg(nil) -> nil [0]
   encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0]
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) [0]
   encode_nil -> nil [0]
   encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0]
   ++(x0, x1) -> c_++(x0, x1) [0]
   encArg(v0) -> null_encArg [0]
   encode_++(v0, v1) -> null_encode_++ [0]
   encode_nil -> null_encode_nil [0]
   encode_.(v0, v1) -> null_encode_. [0]
   ++(v0, v1) -> null_++ [0]

The TRS has the following type information:
++ :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
nil :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
. :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
c_++ :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
encArg :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
cons_++ :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
encode_++ :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
encode_nil :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
encode_. :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++ -> nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
null_encArg :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
null_encode_++ :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
null_encode_nil :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
null_encode_. :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++
null_++ :: nil:.:c_++:cons_++:null_encArg:null_encode_++:null_encode_nil:null_encode_.:null_++

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

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

   nil => 0
   null_encArg => 0
   null_encode_++ => 0
   null_encode_nil => 0
   null_encode_. => 0
   null_++ => 0

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

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

   ++(z', z'') -{ 1 }-> x :|: z'' = 0, z' = x, x >= 0
   ++(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 0
   ++(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   ++(z', z'') -{ 1 }-> ++(x, ++(y, z)) :|: z'' = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0
   ++(z', z'') -{ 1 }-> 1 + x + ++(y, z) :|: z'' = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0
   ++(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z'' = x1, x0 >= 0, x1 >= 0, z' = x0
   encArg(z') -{ 0 }-> 0 :|: z' = 0
   encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encArg(z') -{ 0 }-> ++(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2
   encArg(z') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2
   encode_++(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   encode_++(z', z'') -{ 0 }-> ++(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2
   encode_.(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   encode_.(z', z'') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2
   encode_nil -{ 0 }-> 0 :|: 

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V, V1),0,[fun(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1),0,[encArg(V, Out)],[V >= 0]).
eq(start(V, V1),0,[fun1(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1),0,[fun2(Out)],[]).
eq(start(V, V1),0,[fun3(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(fun(V, V1, Out),1,[],[Out = V2,V1 = V2,V2 >= 0,V = 0]).
eq(fun(V, V1, Out),1,[],[Out = V3,V1 = 0,V = V3,V3 >= 0]).
eq(fun(V, V1, Out),1,[fun(V5, V6, Ret1)],[Out = 1 + Ret1 + V4,V1 = V6,V6 >= 0,V = 1 + V4 + V5,V4 >= 0,V5 >= 0]).
eq(fun(V, V1, Out),1,[fun(V8, V9, Ret11),fun(V7, Ret11, Ret)],[Out = Ret,V1 = V9,V9 >= 0,V = 1 + V7 + V8,V7 >= 0,V8 >= 0]).
eq(encArg(V, Out),0,[],[Out = 0,V = 0]).
eq(encArg(V, Out),0,[encArg(V11, Ret01),encArg(V10, Ret12)],[Out = 1 + Ret01 + Ret12,V11 >= 0,V10 >= 0,V = 1 + V10 + V11]).
eq(encArg(V, Out),0,[encArg(V12, Ret0),encArg(V13, Ret13),fun(Ret0, Ret13, Ret2)],[Out = Ret2,V12 >= 0,V13 >= 0,V = 1 + V12 + V13]).
eq(fun1(V, V1, Out),0,[encArg(V15, Ret02),encArg(V14, Ret14),fun(Ret02, Ret14, Ret3)],[Out = Ret3,V15 >= 0,V = V15,V14 >= 0,V1 = V14]).
eq(fun2(Out),0,[],[Out = 0]).
eq(fun3(V, V1, Out),0,[encArg(V17, Ret011),encArg(V16, Ret15)],[Out = 1 + Ret011 + Ret15,V17 >= 0,V = V17,V16 >= 0,V1 = V16]).
eq(fun(V, V1, Out),0,[],[Out = 1 + V18 + V19,V1 = V18,V19 >= 0,V18 >= 0,V = V19]).
eq(encArg(V, Out),0,[],[Out = 0,V20 >= 0,V = V20]).
eq(fun1(V, V1, Out),0,[],[Out = 0,V22 >= 0,V21 >= 0,V1 = V21,V = V22]).
eq(fun3(V, V1, Out),0,[],[Out = 0,V24 >= 0,V23 >= 0,V1 = V23,V = V24]).
eq(fun(V, V1, Out),0,[],[Out = 0,V25 >= 0,V26 >= 0,V1 = V26,V = V25]).
input_output_vars(fun(V,V1,Out),[V,V1],[Out]).
input_output_vars(encArg(V,Out),[V],[Out]).
input_output_vars(fun1(V,V1,Out),[V,V1],[Out]).
input_output_vars(fun2(Out),[],[Out]).
input_output_vars(fun3(V,V1,Out),[V,V1],[Out]).


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

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

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

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

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


### Cost equations --> "Loop" of fun/3 
* CEs [24] --> Loop 12 
* CEs [23] --> Loop 13 
* CEs [19] --> Loop 14 
* CEs [20] --> Loop 15 
* CEs [21] --> Loop 16 
* CEs [22] --> Loop 17 

### Ranking functions of CR fun(V,V1,Out) 
* RF of phase [12,13]: [V]

#### Partial ranking functions of CR fun(V,V1,Out) 
* Partial RF of phase [12,13]:
  - RF of loop [12:1,13:1,13:2]:
    V


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


### Cost equations --> "Loop" of encArg/2 
* CEs [31] --> Loop 18 
* CEs [26,30] --> Loop 19 
* CEs [28] --> Loop 20 
* CEs [27] --> Loop 21 
* CEs [29] --> Loop 22 
* CEs [25] --> Loop 23 

### Ranking functions of CR encArg(V,Out) 
* RF of phase [18,19,20,21,22]: [V]

#### Partial ranking functions of CR encArg(V,Out) 
* Partial RF of phase [18,19,20,21,22]:
  - RF of loop [18:1,18:2,19:1,19:2,20:1,20:2,21:1,21:2,22:1,22:2]:
    V


### Specialization of cost equations fun1/3 
* CE 15 is refined into CE [32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49] 
* CE 16 is refined into CE [50] 


### Cost equations --> "Loop" of fun1/3 
* CEs [48,49] --> Loop 24 
* CEs [41,43,44,46] --> Loop 25 
* CEs [39] --> Loop 26 
* CEs [36,45] --> Loop 27 
* CEs [35] --> Loop 28 
* CEs [32,33,34,37,38,40,42,47,50] --> Loop 29 

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

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


### Specialization of cost equations fun3/3 
* CE 17 is refined into CE [51,52,53,54] 
* CE 18 is refined into CE [55] 


### Cost equations --> "Loop" of fun3/3 
* CEs [54] --> Loop 30 
* CEs [53] --> Loop 31 
* CEs [52] --> Loop 32 
* CEs [51] --> Loop 33 
* CEs [55] --> Loop 34 

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

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


### Specialization of cost equations start/2 
* CE 1 is refined into CE [56,57,58,59,60] 
* CE 2 is refined into CE [61,62] 
* CE 3 is refined into CE [63,64,65,66,67,68] 
* CE 4 is refined into CE [69] 
* CE 5 is refined into CE [70,71,72,73,74] 


### Cost equations --> "Loop" of start/2 
* CEs [56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74] --> Loop 35 

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

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


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

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

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

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

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

* Chain [multiple([12,13],[[17],[16],[15],[14]])]: 2*it(12)+2*it([16])+0
  Such that:aux(9) =< 1
aux(10) =< V
it(12) =< aux(10)
it([16]) =< it(12)+aux(9)

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


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

* Chain [multiple([18,19,20,21,22],[[23]])]: 2*it(20)+2*s(9)+2*s(10)+0
  Such that:aux(13) =< V
aux(14) =< 2*V+1
it(20) =< aux(13)
it(18) =< aux(14)
it(20) =< aux(14)
s(12) =< it(18)*aux(13)
s(9) =< s(12)
s(10) =< s(9)+aux(14)

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


#### Cost of chains of fun1(V,V1,Out):
* Chain [29]: 6*s(15)+6*s(18)+6*s(19)+6*s(29)+6*s(32)+6*s(33)+1
  Such that:aux(15) =< V
aux(16) =< 2*V+1
aux(17) =< V1
aux(18) =< 2*V1+1
s(29) =< aux(15)
s(29) =< aux(16)
s(31) =< aux(16)*aux(15)
s(32) =< s(31)
s(33) =< s(32)+aux(16)
s(15) =< aux(17)
s(15) =< aux(18)
s(17) =< aux(18)*aux(17)
s(18) =< s(17)
s(19) =< s(18)+aux(18)

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

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

* Chain [27]: 4*s(57)+4*s(60)+4*s(61)+2*s(64)+2*s(67)+2*s(68)+1
  Such that:s(62) =< V
s(63) =< 2*V+1
aux(19) =< V1
aux(20) =< 2*V1+1
s(57) =< aux(19)
s(57) =< aux(20)
s(59) =< aux(20)*aux(19)
s(60) =< s(59)
s(61) =< s(60)+aux(20)
s(64) =< s(62)
s(64) =< s(63)
s(66) =< s(63)*s(62)
s(67) =< s(66)
s(68) =< s(67)+s(63)

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

* Chain [26]: 2*s(78)+2*s(81)+2*s(82)+0
  Such that:s(76) =< V1
s(77) =< 2*V1+1
s(78) =< s(76)
s(78) =< s(77)
s(80) =< s(77)*s(76)
s(81) =< s(80)
s(82) =< s(81)+s(77)

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

* Chain [25]: 8*s(85)+8*s(88)+8*s(89)+2*s(106)+2*s(107)+2*s(117)+2*s(120)+2*s(121)+1
  Such that:s(104) =< 1
s(115) =< V1
s(116) =< 2*V1+1
aux(22) =< V
aux(23) =< 2*V+1
s(106) =< aux(22)
s(107) =< s(106)+s(104)
s(85) =< aux(22)
s(85) =< aux(23)
s(87) =< aux(23)*aux(22)
s(88) =< s(87)
s(89) =< s(88)+aux(23)
s(117) =< s(115)
s(117) =< s(116)
s(119) =< s(116)*s(115)
s(120) =< s(119)
s(121) =< s(120)+s(116)

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

* Chain [24]: 4*s(124)+4*s(127)+4*s(128)+4*s(131)+4*s(134)+4*s(135)+2*s(152)+2*s(153)+0
  Such that:s(150) =< 1
aux(25) =< V
aux(26) =< 2*V+1
aux(27) =< V1
aux(28) =< 2*V1+1
s(152) =< aux(25)
s(153) =< s(152)+s(150)
s(131) =< aux(27)
s(131) =< aux(28)
s(133) =< aux(28)*aux(27)
s(134) =< s(133)
s(135) =< s(134)+aux(28)
s(124) =< aux(25)
s(124) =< aux(26)
s(126) =< aux(26)*aux(25)
s(127) =< s(126)
s(128) =< s(127)+aux(26)

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


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

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

* Chain [32]: 2*s(156)+2*s(159)+2*s(160)+0
  Such that:s(154) =< V1
s(155) =< 2*V1+1
s(156) =< s(154)
s(156) =< s(155)
s(158) =< s(155)*s(154)
s(159) =< s(158)
s(160) =< s(159)+s(155)

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

* Chain [31]: 2*s(163)+2*s(166)+2*s(167)+0
  Such that:s(161) =< V
s(162) =< 2*V+1
s(163) =< s(161)
s(163) =< s(162)
s(165) =< s(162)*s(161)
s(166) =< s(165)
s(167) =< s(166)+s(162)

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

* Chain [30]: 2*s(170)+2*s(173)+2*s(174)+2*s(177)+2*s(180)+2*s(181)+0
  Such that:s(168) =< V
s(169) =< 2*V+1
s(175) =< V1
s(176) =< 2*V1+1
s(177) =< s(175)
s(177) =< s(176)
s(179) =< s(176)*s(175)
s(180) =< s(179)
s(181) =< s(180)+s(176)
s(170) =< s(168)
s(170) =< s(169)
s(172) =< s(169)*s(168)
s(173) =< s(172)
s(174) =< s(173)+s(169)

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


#### Cost of chains of start(V,V1):
* Chain [35]: 6*s(184)+6*s(185)+26*s(188)+26*s(191)+26*s(192)+22*s(201)+22*s(203)+22*s(204)+1
  Such that:aux(29) =< 1
aux(30) =< V
aux(31) =< 2*V+1
aux(32) =< V1
aux(33) =< 2*V1+1
s(184) =< aux(30)
s(185) =< s(184)+aux(29)
s(188) =< aux(30)
s(188) =< aux(31)
s(190) =< aux(31)*aux(30)
s(191) =< s(190)
s(192) =< s(191)+aux(31)
s(201) =< aux(32)
s(201) =< aux(33)
s(202) =< aux(33)*aux(32)
s(203) =< s(202)
s(204) =< s(203)+aux(33)

  with precondition: [] 


Closed-form bounds of start(V,V1): 
-------------------------------------
* Chain [35] with precondition: [] 
    - Upper bound: nat(V)*38+7+nat(V)*52*nat(2*V+1)+nat(V1)*22+nat(V1)*44*nat(2*V1+1)+nat(2*V+1)*26+nat(2*V1+1)*22 
    - Complexity: n^2 

### Maximum cost of start(V,V1): nat(V)*38+7+nat(V)*52*nat(2*V+1)+nat(V1)*22+nat(V1)*44*nat(2*V1+1)+nat(2*V+1)*26+nat(2*V1+1)*22 
Asymptotic class: n^2 
* Total analysis performed in 498 ms.


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

(16)
BOUNDS(1, n^2)

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

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

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

   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   ++(++(x, y), z) -> ++(x, ++(y, z))

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

   encArg(nil) -> nil
   encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2))
   encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2))

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

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

(20)
Obligation:
Innermost TRS:
Rules:
++(nil, y) -> y
++(x, nil) -> x
++(.(x, y), z) -> .(x, ++(y, z))
++(++(x, y), z) -> ++(x, ++(y, z))
encArg(nil) -> nil
encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2))
encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))
encode_nil -> nil
encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2))

Types:
++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
nil :: nil:.:cons_++
. :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encArg :: nil:.:cons_++ -> nil:.:cons_++
cons_++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encode_++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encode_nil :: nil:.:cons_++
encode_. :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
hole_nil:.:cons_++1_0 :: nil:.:cons_++
gen_nil:.:cons_++2_0 :: Nat -> nil:.:cons_++

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

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

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

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

(22)
Obligation:
Innermost TRS:
Rules:
++(nil, y) -> y
++(x, nil) -> x
++(.(x, y), z) -> .(x, ++(y, z))
++(++(x, y), z) -> ++(x, ++(y, z))
encArg(nil) -> nil
encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2))
encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))
encode_nil -> nil
encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2))

Types:
++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
nil :: nil:.:cons_++
. :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encArg :: nil:.:cons_++ -> nil:.:cons_++
cons_++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encode_++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encode_nil :: nil:.:cons_++
encode_. :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
hole_nil:.:cons_++1_0 :: nil:.:cons_++
gen_nil:.:cons_++2_0 :: Nat -> nil:.:cons_++


Generator Equations:
gen_nil:.:cons_++2_0(0) <=> nil
gen_nil:.:cons_++2_0(+(x, 1)) <=> .(nil, gen_nil:.:cons_++2_0(x))


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

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

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

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
++(gen_nil:.:cons_++2_0(n4_0), gen_nil:.:cons_++2_0(b)) -> gen_nil:.:cons_++2_0(+(n4_0, b)), rt in Omega(1 + n4_0)

Induction Base:
++(gen_nil:.:cons_++2_0(0), gen_nil:.:cons_++2_0(b)) ->_R^Omega(1)
gen_nil:.:cons_++2_0(b)

Induction Step:
++(gen_nil:.:cons_++2_0(+(n4_0, 1)), gen_nil:.:cons_++2_0(b)) ->_R^Omega(1)
.(nil, ++(gen_nil:.:cons_++2_0(n4_0), gen_nil:.:cons_++2_0(b))) ->_IH
.(nil, gen_nil:.:cons_++2_0(+(b, c5_0)))

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

(24)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
++(nil, y) -> y
++(x, nil) -> x
++(.(x, y), z) -> .(x, ++(y, z))
++(++(x, y), z) -> ++(x, ++(y, z))
encArg(nil) -> nil
encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2))
encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))
encode_nil -> nil
encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2))

Types:
++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
nil :: nil:.:cons_++
. :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encArg :: nil:.:cons_++ -> nil:.:cons_++
cons_++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encode_++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encode_nil :: nil:.:cons_++
encode_. :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
hole_nil:.:cons_++1_0 :: nil:.:cons_++
gen_nil:.:cons_++2_0 :: Nat -> nil:.:cons_++


Generator Equations:
gen_nil:.:cons_++2_0(0) <=> nil
gen_nil:.:cons_++2_0(+(x, 1)) <=> .(nil, gen_nil:.:cons_++2_0(x))


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

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

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

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

(27)
BOUNDS(n^1, INF)

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

(28)
Obligation:
Innermost TRS:
Rules:
++(nil, y) -> y
++(x, nil) -> x
++(.(x, y), z) -> .(x, ++(y, z))
++(++(x, y), z) -> ++(x, ++(y, z))
encArg(nil) -> nil
encArg(.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2))
encArg(cons_++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))
encode_nil -> nil
encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2))

Types:
++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
nil :: nil:.:cons_++
. :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encArg :: nil:.:cons_++ -> nil:.:cons_++
cons_++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encode_++ :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
encode_nil :: nil:.:cons_++
encode_. :: nil:.:cons_++ -> nil:.:cons_++ -> nil:.:cons_++
hole_nil:.:cons_++1_0 :: nil:.:cons_++
gen_nil:.:cons_++2_0 :: Nat -> nil:.:cons_++


Lemmas:
++(gen_nil:.:cons_++2_0(n4_0), gen_nil:.:cons_++2_0(b)) -> gen_nil:.:cons_++2_0(+(n4_0, b)), rt in Omega(1 + n4_0)


Generator Equations:
gen_nil:.:cons_++2_0(0) <=> nil
gen_nil:.:cons_++2_0(+(x, 1)) <=> .(nil, gen_nil:.:cons_++2_0(x))


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

(29) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_nil:.:cons_++2_0(n822_0)) -> gen_nil:.:cons_++2_0(n822_0), rt in Omega(0)

Induction Base:
encArg(gen_nil:.:cons_++2_0(0)) ->_R^Omega(0)
nil

Induction Step:
encArg(gen_nil:.:cons_++2_0(+(n822_0, 1))) ->_R^Omega(0)
.(encArg(nil), encArg(gen_nil:.:cons_++2_0(n822_0))) ->_R^Omega(0)
.(nil, encArg(gen_nil:.:cons_++2_0(n822_0))) ->_IH
.(nil, gen_nil:.:cons_++2_0(c823_0))

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

(30)
BOUNDS(1, INF)