/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), 146 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, 1106 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), 305 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), 84 ms]
            (28) typed CpxTrs
            (29) RewriteLemmaProof [LOWER BOUND(ID), 0 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:

   f(a, empty) -> g(a, empty)
   f(a, cons(x, k)) -> f(cons(x, a), k)
   g(empty, d) -> d
   g(cons(x, k), d) -> g(k, cons(x, d))

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(empty) -> empty
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(cons_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_empty -> empty
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_cons(x_1, x_2) -> cons(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:

   f(a, empty) -> g(a, empty)
   f(a, cons(x, k)) -> f(cons(x, a), k)
   g(empty, d) -> d
   g(cons(x, k), d) -> g(k, cons(x, d))

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

   encArg(empty) -> empty
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(cons_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_empty -> empty
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_cons(x_1, x_2) -> cons(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:

   f(a, empty) -> g(a, empty)
   f(a, cons(x, k)) -> f(cons(x, a), k)
   g(empty, d) -> d
   g(cons(x, k), d) -> g(k, cons(x, d))

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

   encArg(empty) -> empty
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(cons_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_empty -> empty
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_cons(x_1, x_2) -> cons(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:

   f(a, empty) -> g(a, empty) [1]
   f(a, cons(x, k)) -> f(cons(x, a), k) [1]
   g(empty, d) -> d [1]
   g(cons(x, k), d) -> g(k, cons(x, d)) [1]
   encArg(empty) -> empty [0]
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_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_empty -> empty [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_cons(x_1, x_2) -> cons(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:

   f(a, empty) -> g(a, empty) [1]
   f(a, cons(x, k)) -> f(cons(x, a), k) [1]
   g(empty, d) -> d [1]
   g(cons(x, k), d) -> g(k, cons(x, d)) [1]
   encArg(empty) -> empty [0]
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_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_empty -> empty [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0]

The TRS has the following type information:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f: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_f(v0, v1) -> null_encode_f [0]
   encode_empty -> null_encode_empty [0]
   encode_g(v0, v1) -> null_encode_g [0]
   encode_cons(v0, v1) -> null_encode_cons [0]
   f(v0, v1) -> null_f [0]
   g(v0, v1) -> null_g [0]

And the following fresh constants:    null_encArg, null_encode_f, null_encode_empty, null_encode_g, null_encode_cons, null_f, 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:

   f(a, empty) -> g(a, empty) [1]
   f(a, cons(x, k)) -> f(cons(x, a), k) [1]
   g(empty, d) -> d [1]
   g(cons(x, k), d) -> g(k, cons(x, d)) [1]
   encArg(empty) -> empty [0]
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_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_empty -> empty [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(v0) -> null_encArg [0]
   encode_f(v0, v1) -> null_encode_f [0]
   encode_empty -> null_encode_empty [0]
   encode_g(v0, v1) -> null_encode_g [0]
   encode_cons(v0, v1) -> null_encode_cons [0]
   f(v0, v1) -> null_f [0]
   g(v0, v1) -> null_g [0]

The TRS has the following type information:
f :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
empty :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
g :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
cons :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
encArg :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
cons_f :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
cons_g :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
encode_f :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
encode_empty :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
encode_g :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
encode_cons :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g -> empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
null_encArg :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
null_encode_f :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
null_encode_empty :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
null_encode_g :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
null_encode_cons :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
null_f :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f:null_g
null_g :: empty:cons:cons_f:cons_g:null_encArg:null_encode_f:null_encode_empty:null_encode_g:null_encode_cons:null_f: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:

   empty => 0
   null_encArg => 0
   null_encode_f => 0
   null_encode_empty => 0
   null_encode_g => 0
   null_encode_cons => 0
   null_f => 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, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encArg(z) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_cons(z, z') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_g(z, z') -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_g(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   f(z, z') -{ 1 }-> g(a, 0) :|: z = a, a >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + a, k) :|: z = a, a >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   g(z, z') -{ 1 }-> d :|: z' = d, d >= 0, z = 0
   g(z, z') -{ 1 }-> g(k, 1 + x + d) :|: z' = d, x >= 0, d >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1

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(V1, V),0,[f(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V),0,[g(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V),0,[encArg(V1, Out)],[V1 >= 0]).
eq(start(V1, V),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V),0,[fun1(Out)],[]).
eq(start(V1, V),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V),0,[fun3(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(f(V1, V, Out),1,[g(V2, 0, Ret)],[Out = Ret,V1 = V2,V2 >= 0,V = 0]).
eq(f(V1, V, Out),1,[f(1 + V4 + V3, V5, Ret1)],[Out = Ret1,V1 = V3,V3 >= 0,V4 >= 0,V = 1 + V4 + V5,V5 >= 0]).
eq(g(V1, V, Out),1,[],[Out = V6,V = V6,V6 >= 0,V1 = 0]).
eq(g(V1, V, Out),1,[g(V9, 1 + V7 + V8, Ret2)],[Out = Ret2,V = V8,V7 >= 0,V8 >= 0,V9 >= 0,V1 = 1 + V7 + V9]).
eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]).
eq(encArg(V1, Out),0,[encArg(V11, Ret01),encArg(V10, Ret11)],[Out = 1 + Ret01 + Ret11,V11 >= 0,V1 = 1 + V10 + V11,V10 >= 0]).
eq(encArg(V1, Out),0,[encArg(V12, Ret0),encArg(V13, Ret12),f(Ret0, Ret12, Ret3)],[Out = Ret3,V12 >= 0,V1 = 1 + V12 + V13,V13 >= 0]).
eq(encArg(V1, Out),0,[encArg(V15, Ret02),encArg(V14, Ret13),g(Ret02, Ret13, Ret4)],[Out = Ret4,V15 >= 0,V1 = 1 + V14 + V15,V14 >= 0]).
eq(fun(V1, V, Out),0,[encArg(V17, Ret03),encArg(V16, Ret14),f(Ret03, Ret14, Ret5)],[Out = Ret5,V17 >= 0,V16 >= 0,V1 = V17,V = V16]).
eq(fun1(Out),0,[],[Out = 0]).
eq(fun2(V1, V, Out),0,[encArg(V19, Ret04),encArg(V18, Ret15),g(Ret04, Ret15, Ret6)],[Out = Ret6,V19 >= 0,V18 >= 0,V1 = V19,V = V18]).
eq(fun3(V1, V, Out),0,[encArg(V20, Ret011),encArg(V21, Ret16)],[Out = 1 + Ret011 + Ret16,V20 >= 0,V21 >= 0,V1 = V20,V = V21]).
eq(encArg(V1, Out),0,[],[Out = 0,V22 >= 0,V1 = V22]).
eq(fun(V1, V, Out),0,[],[Out = 0,V24 >= 0,V23 >= 0,V1 = V24,V = V23]).
eq(fun2(V1, V, Out),0,[],[Out = 0,V26 >= 0,V25 >= 0,V1 = V26,V = V25]).
eq(fun3(V1, V, Out),0,[],[Out = 0,V27 >= 0,V28 >= 0,V1 = V27,V = V28]).
eq(f(V1, V, Out),0,[],[Out = 0,V29 >= 0,V30 >= 0,V1 = V29,V = V30]).
eq(g(V1, V, Out),0,[],[Out = 0,V32 >= 0,V31 >= 0,V1 = V32,V = V31]).
input_output_vars(f(V1,V,Out),[V1,V],[Out]).
input_output_vars(g(V1,V,Out),[V1,V],[Out]).
input_output_vars(encArg(V1,Out),[V1],[Out]).
input_output_vars(fun(V1,V,Out),[V1,V],[Out]).
input_output_vars(fun1(Out),[],[Out]).
input_output_vars(fun2(V1,V,Out),[V1,V],[Out]).
input_output_vars(fun3(V1,V,Out),[V1,V],[Out]).


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

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

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

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

### Specialization of cost equations g/3 
* CE 13 is refined into CE [24] 
* CE 11 is refined into CE [25] 
* CE 12 is refined into CE [26] 


### Cost equations --> "Loop" of g/3 
* CEs [26] --> Loop 13 
* CEs [24] --> Loop 14 
* CEs [25] --> Loop 15 

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

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


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


### Cost equations --> "Loop" of f/3 
* CEs [31] --> Loop 16 
* CEs [30] --> Loop 17 
* CEs [27,28,29] --> Loop 18 

### Ranking functions of CR f(V1,V,Out) 
* RF of phase [16]: [V]

#### Partial ranking functions of CR f(V1,V,Out) 
* Partial RF of phase [16]:
  - RF of loop [16:1]:
    V


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


### Cost equations --> "Loop" of encArg/2 
* CEs [33] --> Loop 19 
* CEs [36] --> Loop 20 
* CEs [34,39] --> Loop 21 
* CEs [37] --> Loop 22 
* CEs [35,38] --> Loop 23 
* CEs [32] --> Loop 24 

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

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


### Specialization of cost equations fun/3 
* CE 18 is refined into CE [40,41,42,43,44,45,46,47] 
* CE 19 is refined into CE [48] 


### Cost equations --> "Loop" of fun/3 
* CEs [43] --> Loop 25 
* CEs [45,47] --> Loop 26 
* CEs [42] --> Loop 27 
* CEs [40,41,44,46,48] --> Loop 28 

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

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


### Specialization of cost equations fun2/3 
* CE 20 is refined into CE [49,50,51,52,53,54,55,56,57,58] 
* CE 21 is refined into CE [59] 


### Cost equations --> "Loop" of fun2/3 
* CEs [55] --> Loop 29 
* CEs [58] --> Loop 30 
* CEs [51,56] --> Loop 31 
* CEs [49,50,52,53,54,57,59] --> Loop 32 

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

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


### Specialization of cost equations fun3/3 
* CE 22 is refined into CE [60,61,62,63] 
* CE 23 is refined into CE [64] 


### Cost equations --> "Loop" of fun3/3 
* CEs [63] --> Loop 33 
* CEs [62] --> Loop 34 
* CEs [61] --> Loop 35 
* CEs [60] --> Loop 36 
* CEs [64] --> Loop 37 

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

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


### Specialization of cost equations start/2 
* CE 1 is refined into CE [65,66,67] 
* CE 2 is refined into CE [68,69,70] 
* CE 3 is refined into CE [71,72] 
* CE 4 is refined into CE [73,74,75,76] 
* CE 5 is refined into CE [77] 
* CE 6 is refined into CE [78,79,80,81] 
* CE 7 is refined into CE [82,83,84,85,86] 


### Cost equations --> "Loop" of start/2 
* CEs [65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86] --> Loop 38 

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

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


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

#### Cost of chains of g(V1,V,Out):
* Chain [[13],15]: 1*it(13)+1
  Such that:it(13) =< -V+Out

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

* Chain [[13],14]: 1*it(13)+0
  Such that:it(13) =< V1

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

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

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


#### Cost of chains of f(V1,V,Out):
* Chain [[16],18]: 1*it(16)+1*s(2)+2
  Such that:s(2) =< V1+V
it(16) =< V

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

* Chain [[16],17]: 1*it(16)+1*s(3)+2
  Such that:it(16) =< -V1+Out
s(3) =< Out

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

* Chain [18]: 1*s(2)+2
  Such that:s(2) =< V1

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

* Chain [17]: 1*s(3)+2
  Such that:s(3) =< V1

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


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

* Chain [multiple([19,20,21,22,23],[[24]])]: 4*it(20)+3*it(22)+1*s(23)+1*s(24)+2*s(25)+2*s(27)+2*s(28)+0
  Such that:it([24]) =< V1+1
aux(11) =< V1
aux(12) =< 2/3*V1
it(20) =< aux(11)
it(22) =< aux(11)
it(20) =< aux(12)
aux(5) =< aux(11)-1
aux(8) =< aux(11)
it(20) =< it([24])*(1/3)+aux(12)
it(22) =< it([24])*(1/3)+aux(12)
s(30) =< it(22)*aux(5)
s(28) =< it(22)*aux(8)
s(26) =< it(20)*aux(5)
s(23) =< it(20)*aux(5)
s(24) =< it(20)*aux(11)
s(27) =< s(30)
s(25) =< s(26)

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


#### Cost of chains of fun(V1,V,Out):
* Chain [28]: 8*s(37)+6*s(38)+4*s(42)+2*s(44)+2*s(45)+4*s(46)+4*s(47)+3*s(49)+8*s(54)+6*s(55)+4*s(59)+2*s(61)+2*s(62)+4*s(63)+4*s(64)+3*s(65)+1*s(97)+2
  Such that:s(97) =< V1+V
aux(18) =< V1
aux(19) =< V1+1
aux(20) =< 2/3*V1
aux(21) =< V
aux(22) =< V+1
aux(23) =< 2/3*V
s(65) =< aux(18)
s(54) =< aux(18)
s(55) =< aux(18)
s(54) =< aux(20)
s(56) =< aux(18)-1
s(57) =< aux(18)
s(54) =< aux(19)*(1/3)+aux(20)
s(55) =< aux(19)*(1/3)+aux(20)
s(58) =< s(55)*s(56)
s(59) =< s(55)*s(57)
s(60) =< s(54)*s(56)
s(61) =< s(54)*s(56)
s(62) =< s(54)*aux(18)
s(63) =< s(58)
s(64) =< s(60)
s(49) =< aux(21)
s(37) =< aux(21)
s(38) =< aux(21)
s(37) =< aux(23)
s(39) =< aux(21)-1
s(40) =< aux(21)
s(37) =< aux(22)*(1/3)+aux(23)
s(38) =< aux(22)*(1/3)+aux(23)
s(41) =< s(38)*s(39)
s(42) =< s(38)*s(40)
s(43) =< s(37)*s(39)
s(44) =< s(37)*s(39)
s(45) =< s(37)*aux(21)
s(46) =< s(41)
s(47) =< s(43)

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

* Chain [27]: 4*s(102)+3*s(103)+2*s(107)+1*s(109)+1*s(110)+2*s(111)+2*s(112)+2*s(113)+2
  Such that:s(99) =< V+1
s(101) =< 2/3*V
aux(24) =< V
s(113) =< aux(24)
s(102) =< aux(24)
s(103) =< aux(24)
s(102) =< s(101)
s(104) =< aux(24)-1
s(105) =< aux(24)
s(102) =< s(99)*(1/3)+s(101)
s(103) =< s(99)*(1/3)+s(101)
s(106) =< s(103)*s(104)
s(107) =< s(103)*s(105)
s(108) =< s(102)*s(104)
s(109) =< s(102)*s(104)
s(110) =< s(102)*aux(24)
s(111) =< s(106)
s(112) =< s(108)

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

* Chain [26]: 8*s(118)+6*s(119)+4*s(123)+2*s(125)+2*s(126)+4*s(127)+4*s(128)+8*s(132)+6*s(133)+4*s(137)+2*s(139)+2*s(140)+4*s(141)+4*s(142)+1*s(143)+1*s(172)+1*s(173)+2
  Such that:s(173) =< V1+V
aux(27) =< V1
aux(28) =< V1+1
aux(29) =< 2/3*V1
aux(30) =< V
aux(31) =< V+1
aux(32) =< 2/3*V
s(172) =< aux(30)
s(132) =< aux(30)
s(133) =< aux(30)
s(132) =< aux(32)
s(134) =< aux(30)-1
s(135) =< aux(30)
s(132) =< aux(31)*(1/3)+aux(32)
s(133) =< aux(31)*(1/3)+aux(32)
s(136) =< s(133)*s(134)
s(137) =< s(133)*s(135)
s(138) =< s(132)*s(134)
s(139) =< s(132)*s(134)
s(140) =< s(132)*aux(30)
s(141) =< s(136)
s(142) =< s(138)
s(118) =< aux(27)
s(119) =< aux(27)
s(118) =< aux(29)
s(120) =< aux(27)-1
s(121) =< aux(27)
s(118) =< aux(28)*(1/3)+aux(29)
s(119) =< aux(28)*(1/3)+aux(29)
s(122) =< s(119)*s(120)
s(123) =< s(119)*s(121)
s(124) =< s(118)*s(120)
s(125) =< s(118)*s(120)
s(126) =< s(118)*aux(27)
s(127) =< s(122)
s(128) =< s(124)
s(143) =< aux(27)

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

* Chain [25]: 4*s(177)+3*s(178)+2*s(182)+1*s(184)+1*s(185)+2*s(186)+2*s(187)+1*s(188)+2
  Such that:s(174) =< V1+1
s(176) =< 2/3*V1
aux(33) =< V1
s(188) =< aux(33)
s(177) =< aux(33)
s(178) =< aux(33)
s(177) =< s(176)
s(179) =< aux(33)-1
s(180) =< aux(33)
s(177) =< s(174)*(1/3)+s(176)
s(178) =< s(174)*(1/3)+s(176)
s(181) =< s(178)*s(179)
s(182) =< s(178)*s(180)
s(183) =< s(177)*s(179)
s(184) =< s(177)*s(179)
s(185) =< s(177)*aux(33)
s(186) =< s(181)
s(187) =< s(183)

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


#### Cost of chains of fun2(V1,V,Out):
* Chain [32]: 8*s(193)+6*s(194)+4*s(198)+2*s(200)+2*s(201)+4*s(202)+4*s(203)+12*s(208)+9*s(209)+6*s(213)+3*s(215)+3*s(216)+6*s(217)+6*s(218)+2*s(233)+1
  Such that:aux(36) =< V1
aux(37) =< V1+1
aux(38) =< 2/3*V1
aux(39) =< V
aux(40) =< V+1
aux(41) =< 2/3*V
s(208) =< aux(36)
s(209) =< aux(36)
s(208) =< aux(38)
s(210) =< aux(36)-1
s(211) =< aux(36)
s(208) =< aux(37)*(1/3)+aux(38)
s(209) =< aux(37)*(1/3)+aux(38)
s(212) =< s(209)*s(210)
s(213) =< s(209)*s(211)
s(214) =< s(208)*s(210)
s(215) =< s(208)*s(210)
s(216) =< s(208)*aux(36)
s(217) =< s(212)
s(218) =< s(214)
s(233) =< aux(36)
s(193) =< aux(39)
s(194) =< aux(39)
s(193) =< aux(41)
s(195) =< aux(39)-1
s(196) =< aux(39)
s(193) =< aux(40)*(1/3)+aux(41)
s(194) =< aux(40)*(1/3)+aux(41)
s(197) =< s(194)*s(195)
s(198) =< s(194)*s(196)
s(199) =< s(193)*s(195)
s(200) =< s(193)*s(195)
s(201) =< s(193)*aux(39)
s(202) =< s(197)
s(203) =< s(199)

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

* Chain [31]: 8*s(266)+6*s(267)+4*s(271)+2*s(273)+2*s(274)+4*s(275)+4*s(276)+4*s(280)+3*s(281)+2*s(285)+1*s(287)+1*s(288)+2*s(289)+2*s(290)+1
  Such that:s(278) =< V1
s(277) =< V1+1
s(279) =< 2/3*V1
aux(42) =< V
aux(43) =< V+1
aux(44) =< 2/3*V
s(266) =< aux(42)
s(267) =< aux(42)
s(266) =< aux(44)
s(268) =< aux(42)-1
s(269) =< aux(42)
s(266) =< aux(43)*(1/3)+aux(44)
s(267) =< aux(43)*(1/3)+aux(44)
s(270) =< s(267)*s(268)
s(271) =< s(267)*s(269)
s(272) =< s(266)*s(268)
s(273) =< s(266)*s(268)
s(274) =< s(266)*aux(42)
s(275) =< s(270)
s(276) =< s(272)
s(280) =< s(278)
s(281) =< s(278)
s(280) =< s(279)
s(282) =< s(278)-1
s(283) =< s(278)
s(280) =< s(277)*(1/3)+s(279)
s(281) =< s(277)*(1/3)+s(279)
s(284) =< s(281)*s(282)
s(285) =< s(281)*s(283)
s(286) =< s(280)*s(282)
s(287) =< s(280)*s(282)
s(288) =< s(280)*s(278)
s(289) =< s(284)
s(290) =< s(286)

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

* Chain [30]: 4*s(308)+3*s(309)+2*s(313)+1*s(315)+1*s(316)+2*s(317)+2*s(318)+4*s(322)+3*s(323)+2*s(327)+1*s(329)+1*s(330)+2*s(331)+2*s(332)+1*s(333)+1
  Such that:s(305) =< V1+1
s(307) =< 2/3*V1
s(320) =< V
s(319) =< V+1
s(321) =< 2/3*V
aux(45) =< V1
s(333) =< aux(45)
s(322) =< s(320)
s(323) =< s(320)
s(322) =< s(321)
s(324) =< s(320)-1
s(325) =< s(320)
s(322) =< s(319)*(1/3)+s(321)
s(323) =< s(319)*(1/3)+s(321)
s(326) =< s(323)*s(324)
s(327) =< s(323)*s(325)
s(328) =< s(322)*s(324)
s(329) =< s(322)*s(324)
s(330) =< s(322)*s(320)
s(331) =< s(326)
s(332) =< s(328)
s(308) =< aux(45)
s(309) =< aux(45)
s(308) =< s(307)
s(310) =< aux(45)-1
s(311) =< aux(45)
s(308) =< s(305)*(1/3)+s(307)
s(309) =< s(305)*(1/3)+s(307)
s(312) =< s(309)*s(310)
s(313) =< s(309)*s(311)
s(314) =< s(308)*s(310)
s(315) =< s(308)*s(310)
s(316) =< s(308)*aux(45)
s(317) =< s(312)
s(318) =< s(314)

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

* Chain [29]: 4*s(337)+3*s(338)+2*s(342)+1*s(344)+1*s(345)+2*s(346)+2*s(347)+1*s(348)+1
  Such that:s(334) =< V1+1
s(336) =< 2/3*V1
aux(46) =< V1
s(348) =< aux(46)
s(337) =< aux(46)
s(338) =< aux(46)
s(337) =< s(336)
s(339) =< aux(46)-1
s(340) =< aux(46)
s(337) =< s(334)*(1/3)+s(336)
s(338) =< s(334)*(1/3)+s(336)
s(341) =< s(338)*s(339)
s(342) =< s(338)*s(340)
s(343) =< s(337)*s(339)
s(344) =< s(337)*s(339)
s(345) =< s(337)*aux(46)
s(346) =< s(341)
s(347) =< s(343)

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


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

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

* Chain [35]: 4*s(352)+3*s(353)+2*s(357)+1*s(359)+1*s(360)+2*s(361)+2*s(362)+0
  Such that:s(350) =< V
s(349) =< V+1
s(351) =< 2/3*V
s(352) =< s(350)
s(353) =< s(350)
s(352) =< s(351)
s(354) =< s(350)-1
s(355) =< s(350)
s(352) =< s(349)*(1/3)+s(351)
s(353) =< s(349)*(1/3)+s(351)
s(356) =< s(353)*s(354)
s(357) =< s(353)*s(355)
s(358) =< s(352)*s(354)
s(359) =< s(352)*s(354)
s(360) =< s(352)*s(350)
s(361) =< s(356)
s(362) =< s(358)

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

* Chain [34]: 4*s(366)+3*s(367)+2*s(371)+1*s(373)+1*s(374)+2*s(375)+2*s(376)+0
  Such that:s(364) =< V1
s(363) =< V1+1
s(365) =< 2/3*V1
s(366) =< s(364)
s(367) =< s(364)
s(366) =< s(365)
s(368) =< s(364)-1
s(369) =< s(364)
s(366) =< s(363)*(1/3)+s(365)
s(367) =< s(363)*(1/3)+s(365)
s(370) =< s(367)*s(368)
s(371) =< s(367)*s(369)
s(372) =< s(366)*s(368)
s(373) =< s(366)*s(368)
s(374) =< s(366)*s(364)
s(375) =< s(370)
s(376) =< s(372)

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

* Chain [33]: 4*s(380)+3*s(381)+2*s(385)+1*s(387)+1*s(388)+2*s(389)+2*s(390)+4*s(394)+3*s(395)+2*s(399)+1*s(401)+1*s(402)+2*s(403)+2*s(404)+0
  Such that:s(378) =< V1
s(377) =< V1+1
s(379) =< 2/3*V1
s(392) =< V
s(391) =< V+1
s(393) =< 2/3*V
s(394) =< s(392)
s(395) =< s(392)
s(394) =< s(393)
s(396) =< s(392)-1
s(397) =< s(392)
s(394) =< s(391)*(1/3)+s(393)
s(395) =< s(391)*(1/3)+s(393)
s(398) =< s(395)*s(396)
s(399) =< s(395)*s(397)
s(400) =< s(394)*s(396)
s(401) =< s(394)*s(396)
s(402) =< s(394)*s(392)
s(403) =< s(398)
s(404) =< s(400)
s(380) =< s(378)
s(381) =< s(378)
s(380) =< s(379)
s(382) =< s(378)-1
s(383) =< s(378)
s(380) =< s(377)*(1/3)+s(379)
s(381) =< s(377)*(1/3)+s(379)
s(384) =< s(381)*s(382)
s(385) =< s(381)*s(383)
s(386) =< s(380)*s(382)
s(387) =< s(380)*s(382)
s(388) =< s(380)*s(378)
s(389) =< s(384)
s(390) =< s(386)

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


#### Cost of chains of start(V1,V):
* Chain [38]: 13*s(405)+4*s(407)+8*s(408)+56*s(416)+42*s(417)+28*s(421)+14*s(423)+14*s(424)+28*s(425)+28*s(426)+48*s(447)+36*s(448)+24*s(452)+12*s(454)+12*s(455)+24*s(456)+24*s(457)+2
  Such that:aux(47) =< V1
aux(48) =< V1+1
aux(49) =< V1+V
aux(50) =< 2/3*V1
aux(51) =< V
aux(52) =< V+1
aux(53) =< 2/3*V
s(405) =< aux(47)
s(407) =< aux(49)
s(408) =< aux(51)
s(416) =< aux(47)
s(417) =< aux(47)
s(416) =< aux(50)
s(418) =< aux(47)-1
s(419) =< aux(47)
s(416) =< aux(48)*(1/3)+aux(50)
s(417) =< aux(48)*(1/3)+aux(50)
s(420) =< s(417)*s(418)
s(421) =< s(417)*s(419)
s(422) =< s(416)*s(418)
s(423) =< s(416)*s(418)
s(424) =< s(416)*aux(47)
s(425) =< s(420)
s(426) =< s(422)
s(447) =< aux(51)
s(448) =< aux(51)
s(447) =< aux(53)
s(449) =< aux(51)-1
s(450) =< aux(51)
s(447) =< aux(52)*(1/3)+aux(53)
s(448) =< aux(52)*(1/3)+aux(53)
s(451) =< s(448)*s(449)
s(452) =< s(448)*s(450)
s(453) =< s(447)*s(449)
s(454) =< s(447)*s(449)
s(455) =< s(447)*aux(51)
s(456) =< s(451)
s(457) =< s(453)

  with precondition: [] 


Closed-form bounds of start(V1,V): 
-------------------------------------
* Chain [38] with precondition: [] 
    - Upper bound: nat(V1)*111+2+nat(V1)*42*nat(V1)+nat(V1)*70*nat(nat(V1)+ -1)+nat(V)*92+nat(V)*36*nat(V)+nat(V)*60*nat(nat(V)+ -1)+nat(V1+V)*4 
    - Complexity: n^2 

### Maximum cost of start(V1,V): nat(V1)*111+2+nat(V1)*42*nat(V1)+nat(V1)*70*nat(nat(V1)+ -1)+nat(V)*92+nat(V)*36*nat(V)+nat(V)*60*nat(nat(V)+ -1)+nat(V1+V)*4 
Asymptotic class: n^2 
* Total analysis performed in 932 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:

   f(a, empty) -> g(a, empty)
   f(a, cons(x, k)) -> f(cons(x, a), k)
   g(empty, d) -> d
   g(cons(x, k), d) -> g(k, cons(x, d))

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

   encArg(empty) -> empty
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(cons_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_empty -> empty
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

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

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

(18)
Obligation:
Innermost TRS:
Rules:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_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_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g

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

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

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

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

(20)
Obligation:
Innermost TRS:
Rules:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_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_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g


Generator Equations:
gen_empty:cons:cons_f:cons_g2_0(0) <=> empty
gen_empty:cons:cons_f:cons_g2_0(+(x, 1)) <=> cons(empty, gen_empty:cons:cons_f:cons_g2_0(x))


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

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

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

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
g(gen_empty:cons:cons_f:cons_g2_0(n4_0), gen_empty:cons:cons_f:cons_g2_0(b)) -> gen_empty:cons:cons_f:cons_g2_0(+(n4_0, b)), rt in Omega(1 + n4_0)

Induction Base:
g(gen_empty:cons:cons_f:cons_g2_0(0), gen_empty:cons:cons_f:cons_g2_0(b)) ->_R^Omega(1)
gen_empty:cons:cons_f:cons_g2_0(b)

Induction Step:
g(gen_empty:cons:cons_f:cons_g2_0(+(n4_0, 1)), gen_empty:cons:cons_f:cons_g2_0(b)) ->_R^Omega(1)
g(gen_empty:cons:cons_f:cons_g2_0(n4_0), cons(empty, gen_empty:cons:cons_f:cons_g2_0(b))) ->_IH
gen_empty:cons:cons_f:cons_g2_0(+(+(b, 1), c5_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:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_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_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g


Generator Equations:
gen_empty:cons:cons_f:cons_g2_0(0) <=> empty
gen_empty:cons:cons_f:cons_g2_0(+(x, 1)) <=> cons(empty, gen_empty:cons:cons_f:cons_g2_0(x))


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

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

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

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

(25)
BOUNDS(n^1, INF)

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

(26)
Obligation:
Innermost TRS:
Rules:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_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_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g


Lemmas:
g(gen_empty:cons:cons_f:cons_g2_0(n4_0), gen_empty:cons:cons_f:cons_g2_0(b)) -> gen_empty:cons:cons_f:cons_g2_0(+(n4_0, b)), rt in Omega(1 + n4_0)


Generator Equations:
gen_empty:cons:cons_f:cons_g2_0(0) <=> empty
gen_empty:cons:cons_f:cons_g2_0(+(x, 1)) <=> cons(empty, gen_empty:cons:cons_f:cons_g2_0(x))


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

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

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

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
f(gen_empty:cons:cons_f:cons_g2_0(a), gen_empty:cons:cons_f:cons_g2_0(n673_0)) -> gen_empty:cons:cons_f:cons_g2_0(+(n673_0, a)), rt in Omega(1 + a + n673_0)

Induction Base:
f(gen_empty:cons:cons_f:cons_g2_0(a), gen_empty:cons:cons_f:cons_g2_0(0)) ->_R^Omega(1)
g(gen_empty:cons:cons_f:cons_g2_0(a), empty) ->_L^Omega(1 + a)
gen_empty:cons:cons_f:cons_g2_0(+(a, 0))

Induction Step:
f(gen_empty:cons:cons_f:cons_g2_0(a), gen_empty:cons:cons_f:cons_g2_0(+(n673_0, 1))) ->_R^Omega(1)
f(cons(empty, gen_empty:cons:cons_f:cons_g2_0(a)), gen_empty:cons:cons_f:cons_g2_0(n673_0)) ->_IH
gen_empty:cons:cons_f:cons_g2_0(+(+(a, 1), c674_0))

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

(28)
Obligation:
Innermost TRS:
Rules:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_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_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g


Lemmas:
g(gen_empty:cons:cons_f:cons_g2_0(n4_0), gen_empty:cons:cons_f:cons_g2_0(b)) -> gen_empty:cons:cons_f:cons_g2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
f(gen_empty:cons:cons_f:cons_g2_0(a), gen_empty:cons:cons_f:cons_g2_0(n673_0)) -> gen_empty:cons:cons_f:cons_g2_0(+(n673_0, a)), rt in Omega(1 + a + n673_0)


Generator Equations:
gen_empty:cons:cons_f:cons_g2_0(0) <=> empty
gen_empty:cons:cons_f:cons_g2_0(+(x, 1)) <=> cons(empty, gen_empty:cons:cons_f:cons_g2_0(x))


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

(29) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_empty:cons:cons_f:cons_g2_0(n1379_0)) -> gen_empty:cons:cons_f:cons_g2_0(n1379_0), rt in Omega(0)

Induction Base:
encArg(gen_empty:cons:cons_f:cons_g2_0(0)) ->_R^Omega(0)
empty

Induction Step:
encArg(gen_empty:cons:cons_f:cons_g2_0(+(n1379_0, 1))) ->_R^Omega(0)
cons(encArg(empty), encArg(gen_empty:cons:cons_f:cons_g2_0(n1379_0))) ->_R^Omega(0)
cons(empty, encArg(gen_empty:cons:cons_f:cons_g2_0(n1379_0))) ->_IH
cons(empty, gen_empty:cons:cons_f:cons_g2_0(c1380_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)