/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^3))
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^3).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 158 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, 1477 ms]
    (14) BOUNDS(1, n^3)
(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), 482 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), 86 ms]
            (28) BOUNDS(1, INF)


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

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


The TRS R consists of the following rules:

   f(t, x, y) -> f(g(x, y), x, s(y))
   g(s(x), 0) -> t
   g(s(x), s(y)) -> g(x, y)

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(t) -> t
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_t -> t
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0


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

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


The TRS R consists of the following rules:

   f(t, x, y) -> f(g(x, y), x, s(y))
   g(s(x), 0) -> t
   g(s(x), s(y)) -> g(x, y)

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

   encArg(t) -> t
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_t -> t
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

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


The TRS R consists of the following rules:

   f(t, x, y) -> f(g(x, y), x, s(y))
   g(s(x), 0) -> t
   g(s(x), s(y)) -> g(x, y)

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

   encArg(t) -> t
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_t -> t
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

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


The TRS R consists of the following rules:

   f(t, x, y) -> f(g(x, y), x, s(y)) [1]
   g(s(x), 0) -> t [1]
   g(s(x), s(y)) -> g(x, y) [1]
   encArg(t) -> t [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_t -> t [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [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(t, x, y) -> f(g(x, y), x, s(y)) [1]
   g(s(x), 0) -> t [1]
   g(s(x), s(y)) -> g(x, y) [1]
   encArg(t) -> t [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_t -> t [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [0]

The TRS has the following type information:
f :: t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g
t :: t:s:0:cons_f:cons_g
g :: t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g
s :: t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g
0 :: t:s:0:cons_f:cons_g
encArg :: t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g
cons_f :: t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g
cons_g :: t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g
encode_f :: t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g
encode_t :: t:s:0:cons_f:cons_g
encode_g :: t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g
encode_s :: t:s:0:cons_f:cons_g -> t:s:0:cons_f:cons_g
encode_0 :: t:s:0: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, v2) -> null_encode_f [0]
   encode_t -> null_encode_t [0]
   encode_g(v0, v1) -> null_encode_g [0]
   encode_s(v0) -> null_encode_s [0]
   encode_0 -> null_encode_0 [0]
   f(v0, v1, v2) -> null_f [0]
   g(v0, v1) -> null_g [0]

And the following fresh constants:    null_encArg, null_encode_f, null_encode_t, null_encode_g, null_encode_s, null_encode_0, 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(t, x, y) -> f(g(x, y), x, s(y)) [1]
   g(s(x), 0) -> t [1]
   g(s(x), s(y)) -> g(x, y) [1]
   encArg(t) -> t [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_t -> t [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [0]
   encArg(v0) -> null_encArg [0]
   encode_f(v0, v1, v2) -> null_encode_f [0]
   encode_t -> null_encode_t [0]
   encode_g(v0, v1) -> null_encode_g [0]
   encode_s(v0) -> null_encode_s [0]
   encode_0 -> null_encode_0 [0]
   f(v0, v1, v2) -> null_f [0]
   g(v0, v1) -> null_g [0]

The TRS has the following type information:
f :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
t :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
g :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
s :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
0 :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
encArg :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
cons_f :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
cons_g :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
encode_f :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
encode_t :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
encode_g :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
encode_s :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g -> t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
encode_0 :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
null_encArg :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
null_encode_f :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
null_encode_t :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
null_encode_g :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
null_encode_s :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
null_encode_0 :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
null_f :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0:null_f:null_g
null_g :: t:s:0:cons_f:cons_g:null_encArg:null_encode_f:null_encode_t:null_encode_g:null_encode_s:null_encode_0: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:

   t => 1
   0 => 0
   null_encArg => 0
   null_encode_f => 0
   null_encode_t => 0
   null_encode_g => 0
   null_encode_s => 0
   null_encode_0 => 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), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, x_3 >= 0, x_2 >= 0, z = x_1, z' = x_2, z'' = x_3
   encode_f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   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
   encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1
   encode_t -{ 0 }-> 1 :|: 
   encode_t -{ 0 }-> 0 :|: 
   f(z, z', z'') -{ 1 }-> f(g(x, y), x, 1 + y) :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0
   f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   g(z, z') -{ 1 }-> g(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   g(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0
   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, V2),0,[f(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]).
eq(start(V1, V, V2),0,[g(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V2),0,[encArg(V1, Out)],[V1 >= 0]).
eq(start(V1, V, V2),0,[fun(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]).
eq(start(V1, V, V2),0,[fun1(Out)],[]).
eq(start(V1, V, V2),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V2),0,[fun3(V1, Out)],[V1 >= 0]).
eq(start(V1, V, V2),0,[fun4(Out)],[]).
eq(f(V1, V, V2, Out),1,[g(V4, V3, Ret0),f(Ret0, V4, 1 + V3, Ret)],[Out = Ret,V = V4,V2 = V3,V1 = 1,V4 >= 0,V3 >= 0]).
eq(g(V1, V, Out),1,[],[Out = 1,V5 >= 0,V1 = 1 + V5,V = 0]).
eq(g(V1, V, Out),1,[g(V6, V7, Ret1)],[Out = Ret1,V = 1 + V7,V6 >= 0,V7 >= 0,V1 = 1 + V6]).
eq(encArg(V1, Out),0,[],[Out = 1,V1 = 1]).
eq(encArg(V1, Out),0,[encArg(V8, Ret11)],[Out = 1 + Ret11,V1 = 1 + V8,V8 >= 0]).
eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]).
eq(encArg(V1, Out),0,[encArg(V10, Ret01),encArg(V11, Ret12),encArg(V9, Ret2),f(Ret01, Ret12, Ret2, Ret3)],[Out = Ret3,V10 >= 0,V1 = 1 + V10 + V11 + V9,V9 >= 0,V11 >= 0]).
eq(encArg(V1, Out),0,[encArg(V12, Ret02),encArg(V13, Ret13),g(Ret02, Ret13, Ret4)],[Out = Ret4,V12 >= 0,V1 = 1 + V12 + V13,V13 >= 0]).
eq(fun(V1, V, V2, Out),0,[encArg(V16, Ret03),encArg(V14, Ret14),encArg(V15, Ret21),f(Ret03, Ret14, Ret21, Ret5)],[Out = Ret5,V16 >= 0,V15 >= 0,V14 >= 0,V1 = V16,V = V14,V2 = V15]).
eq(fun1(Out),0,[],[Out = 1]).
eq(fun2(V1, V, Out),0,[encArg(V18, Ret04),encArg(V17, Ret15),g(Ret04, Ret15, Ret6)],[Out = Ret6,V18 >= 0,V17 >= 0,V1 = V18,V = V17]).
eq(fun3(V1, Out),0,[encArg(V19, Ret16)],[Out = 1 + Ret16,V19 >= 0,V1 = V19]).
eq(fun4(Out),0,[],[Out = 0]).
eq(encArg(V1, Out),0,[],[Out = 0,V20 >= 0,V1 = V20]).
eq(fun(V1, V, V2, Out),0,[],[Out = 0,V22 >= 0,V2 = V23,V21 >= 0,V1 = V22,V = V21,V23 >= 0]).
eq(fun1(Out),0,[],[Out = 0]).
eq(fun2(V1, V, Out),0,[],[Out = 0,V25 >= 0,V24 >= 0,V1 = V25,V = V24]).
eq(fun3(V1, Out),0,[],[Out = 0,V26 >= 0,V1 = V26]).
eq(f(V1, V, V2, Out),0,[],[Out = 0,V27 >= 0,V2 = V28,V29 >= 0,V1 = V27,V = V29,V28 >= 0]).
eq(g(V1, V, Out),0,[],[Out = 0,V30 >= 0,V31 >= 0,V1 = V30,V = V31]).
input_output_vars(f(V1,V,V2,Out),[V1,V,V2],[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,V2,Out),[V1,V,V2],[Out]).
input_output_vars(fun1(Out),[],[Out]).
input_output_vars(fun2(V1,V,Out),[V1,V],[Out]).
input_output_vars(fun3(V1,Out),[V1],[Out]).
input_output_vars(fun4(Out),[],[Out]).


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

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

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

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

### Specialization of cost equations g/3 
* CE 13 is refined into CE [27] 
* CE 11 is refined into CE [28] 
* CE 12 is refined into CE [29] 


### Cost equations --> "Loop" of g/3 
* CEs [29] --> Loop 17 
* CEs [27] --> Loop 18 
* CEs [28] --> Loop 19 

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

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


### Specialization of cost equations f/4 
* CE 10 is refined into CE [30] 
* CE 9 is refined into CE [31,32,33] 


### Cost equations --> "Loop" of f/4 
* CEs [33] --> Loop 20 
* CEs [32] --> Loop 21 
* CEs [31] --> Loop 22 
* CEs [30] --> Loop 23 

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

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


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


### Cost equations --> "Loop" of encArg/2 
* CEs [40] --> Loop 24 
* CEs [39] --> Loop 25 
* CEs [38] --> Loop 26 
* CEs [36] --> Loop 27 
* CEs [37] --> Loop 28 
* CEs [34] --> Loop 29 
* CEs [35] --> Loop 30 

### Ranking functions of CR encArg(V1,Out) 
* RF of phase [24,25,26,27,28]: [V1]

#### Partial ranking functions of CR encArg(V1,Out) 
* Partial RF of phase [24,25,26,27,28]:
  - RF of loop [24:1,25:1,25:2,25:3,26:1,26:2,27:1,27:2,28:1,28:2]:
    V1


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


### Cost equations --> "Loop" of fun/4 
* CEs [41,42,43,44,45,46,47,48,49] --> Loop 31 

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

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


### Specialization of cost equations fun1/1 
* CE 21 is refined into CE [50] 
* CE 22 is refined into CE [51] 


### Cost equations --> "Loop" of fun1/1 
* CEs [50] --> Loop 32 
* CEs [51] --> Loop 33 

### Ranking functions of CR fun1(Out) 

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


### Specialization of cost equations fun2/3 
* CE 23 is refined into CE [52,53,54,55,56,57,58] 
* CE 24 is refined into CE [59] 


### Cost equations --> "Loop" of fun2/3 
* CEs [52,54,55] --> Loop 34 
* CEs [53,56,57,58,59] --> Loop 35 

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

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


### Specialization of cost equations fun3/2 
* CE 25 is refined into CE [60,61] 
* CE 26 is refined into CE [62] 


### Cost equations --> "Loop" of fun3/2 
* CEs [60] --> Loop 36 
* CEs [61] --> Loop 37 
* CEs [62] --> Loop 38 

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

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


### Specialization of cost equations start/3 
* CE 1 is refined into CE [63] 
* CE 2 is refined into CE [64,65,66] 
* CE 3 is refined into CE [67,68] 
* CE 4 is refined into CE [69] 
* CE 5 is refined into CE [70,71] 
* CE 6 is refined into CE [72,73] 
* CE 7 is refined into CE [74,75,76] 
* CE 8 is refined into CE [77] 


### Cost equations --> "Loop" of start/3 
* CEs [63,64,65,66,67,68,69,70,71,72,73,74,75,76,77] --> Loop 39 

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

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


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

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

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

* Chain [[17],18]: 1*it(17)+0
  Such that:it(17) =< V

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

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

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


#### Cost of chains of f(V1,V,V2,Out):
* Chain [[20],23]: 2*it(20)+1*s(4)+0
  Such that:aux(1) =< V
it(20) =< V-V2
s(4) =< it(20)*aux(1)

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

* Chain [[20],21,23]: 2*it(20)+1*s(4)+1*s(5)+1
  Such that:aux(1) =< V
s(5) =< V+1
it(20) =< V-V2
s(4) =< it(20)*aux(1)

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

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

* Chain [22,[20],23]: 2*it(20)+1*s(4)+2
  Such that:aux(2) =< V
it(20) =< aux(2)
s(4) =< it(20)*aux(2)

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

* Chain [22,[20],21,23]: 2*it(20)+1*s(4)+1*s(5)+3
  Such that:s(5) =< V+1
aux(3) =< V
it(20) =< aux(3)
s(4) =< it(20)*aux(3)

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

* Chain [22,23]: 2
  with precondition: [V1=1,V2=0,Out=0,V>=1] 

* Chain [22,21,23]: 1*s(5)+3
  Such that:s(5) =< 2

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

* Chain [21,23]: 1*s(5)+1
  Such that:s(5) =< V2+1

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


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

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

* Chain [multiple([24,25,26,27,28],[[30],[29]])]: 3*it(25)+1*it(26)+1*it(27)+1*s(43)+1*s(44)+2*s(45)+8*s(46)+4*s(47)+1*s(50)+1*s(51)+0
  Such that:aux(21) =< V1
aux(22) =< 2/3*V1
aux(23) =< 2/5*V1
it(24) =< aux(21)
it(25) =< aux(21)
it(26) =< aux(21)
it(27) =< aux(21)
it(27) =< aux(22)
it(26) =< aux(23)
aux(9) =< aux(21)
aux(13) =< aux(21)-2
aux(10) =< aux(21)+1
s(43) =< aux(21)*2
s(44) =< it(25)*aux(10)
s(49) =< it(25)*aux(10)
s(48) =< it(25)*aux(9)
s(51) =< it(24)*aux(9)
s(50) =< it(26)*aux(13)
s(45) =< s(49)
s(46) =< s(48)
s(47) =< s(46)*aux(21)

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


#### Cost of chains of fun(V1,V,V2,Out):
* Chain [31]: 12*s(74)+4*s(75)+4*s(76)+4*s(80)+4*s(81)+4*s(84)+4*s(85)+8*s(86)+32*s(87)+16*s(88)+44*s(92)+4*s(93)+4*s(94)+4*s(98)+4*s(99)+4*s(102)+4*s(103)+8*s(104)+32*s(105)+16*s(106)+12*s(110)+4*s(111)+4*s(112)+4*s(116)+4*s(117)+4*s(120)+4*s(121)+8*s(122)+32*s(123)+16*s(124)+8*s(125)+4*s(126)+8*s(130)+16*s(133)+12*s(172)+3
  Such that:aux(34) =< 1
aux(35) =< 2
aux(36) =< V1
aux(37) =< 2/3*V1
aux(38) =< 2/5*V1
aux(39) =< V
aux(40) =< V+1
aux(41) =< 2/3*V
aux(42) =< 2/5*V
aux(43) =< V2
aux(44) =< V2+1
aux(45) =< 2/3*V2
aux(46) =< 2/5*V2
s(172) =< aux(34)
s(125) =< aux(35)
s(126) =< aux(44)
s(130) =< aux(40)
s(92) =< aux(39)
s(133) =< s(92)*aux(39)
s(93) =< aux(39)
s(94) =< aux(39)
s(94) =< aux(41)
s(93) =< aux(42)
s(95) =< aux(39)
s(96) =< aux(39)-2
s(97) =< aux(39)+1
s(98) =< aux(39)*2
s(99) =< s(92)*s(97)
s(100) =< s(92)*s(97)
s(101) =< s(92)*s(95)
s(102) =< aux(39)*s(95)
s(103) =< s(93)*s(96)
s(104) =< s(100)
s(105) =< s(101)
s(106) =< s(105)*aux(39)
s(74) =< aux(36)
s(75) =< aux(36)
s(76) =< aux(36)
s(76) =< aux(37)
s(75) =< aux(38)
s(77) =< aux(36)
s(78) =< aux(36)-2
s(79) =< aux(36)+1
s(80) =< aux(36)*2
s(81) =< s(74)*s(79)
s(82) =< s(74)*s(79)
s(83) =< s(74)*s(77)
s(84) =< aux(36)*s(77)
s(85) =< s(75)*s(78)
s(86) =< s(82)
s(87) =< s(83)
s(88) =< s(87)*aux(36)
s(110) =< aux(43)
s(111) =< aux(43)
s(112) =< aux(43)
s(112) =< aux(45)
s(111) =< aux(46)
s(113) =< aux(43)
s(114) =< aux(43)-2
s(115) =< aux(43)+1
s(116) =< aux(43)*2
s(117) =< s(110)*s(115)
s(118) =< s(110)*s(115)
s(119) =< s(110)*s(113)
s(120) =< aux(43)*s(113)
s(121) =< s(111)*s(114)
s(122) =< s(118)
s(123) =< s(119)
s(124) =< s(123)*aux(43)

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


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

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


#### Cost of chains of fun2(V1,V,Out):
* Chain [35]: 6*s(370)+2*s(371)+2*s(372)+2*s(376)+2*s(377)+2*s(380)+2*s(381)+4*s(382)+16*s(383)+8*s(384)+8*s(388)+2*s(389)+2*s(390)+2*s(394)+2*s(395)+2*s(398)+2*s(399)+4*s(400)+16*s(401)+8*s(402)+0
  Such that:aux(49) =< V1
aux(50) =< 2/3*V1
aux(51) =< 2/5*V1
aux(52) =< V
aux(53) =< 2/3*V
aux(54) =< 2/5*V
s(388) =< aux(52)
s(389) =< aux(52)
s(390) =< aux(52)
s(390) =< aux(53)
s(389) =< aux(54)
s(391) =< aux(52)
s(392) =< aux(52)-2
s(393) =< aux(52)+1
s(394) =< aux(52)*2
s(395) =< s(388)*s(393)
s(396) =< s(388)*s(393)
s(397) =< s(388)*s(391)
s(398) =< aux(52)*s(391)
s(399) =< s(389)*s(392)
s(400) =< s(396)
s(401) =< s(397)
s(402) =< s(401)*aux(52)
s(370) =< aux(49)
s(371) =< aux(49)
s(372) =< aux(49)
s(372) =< aux(50)
s(371) =< aux(51)
s(373) =< aux(49)
s(374) =< aux(49)-2
s(375) =< aux(49)+1
s(376) =< aux(49)*2
s(377) =< s(370)*s(375)
s(378) =< s(370)*s(375)
s(379) =< s(370)*s(373)
s(380) =< aux(49)*s(373)
s(381) =< s(371)*s(374)
s(382) =< s(378)
s(383) =< s(379)
s(384) =< s(383)*aux(49)

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

* Chain [34]: 9*s(446)+3*s(447)+3*s(448)+3*s(452)+3*s(453)+3*s(456)+3*s(457)+6*s(458)+24*s(459)+12*s(460)+7*s(464)+2*s(465)+2*s(466)+2*s(470)+2*s(471)+2*s(474)+2*s(475)+4*s(476)+16*s(477)+8*s(478)+1
  Such that:aux(56) =< V1
aux(57) =< 2/3*V1
aux(58) =< 2/5*V1
aux(59) =< V
aux(60) =< 2/3*V
aux(61) =< 2/5*V
s(464) =< aux(59)
s(465) =< aux(59)
s(466) =< aux(59)
s(466) =< aux(60)
s(465) =< aux(61)
s(467) =< aux(59)
s(468) =< aux(59)-2
s(469) =< aux(59)+1
s(470) =< aux(59)*2
s(471) =< s(464)*s(469)
s(472) =< s(464)*s(469)
s(473) =< s(464)*s(467)
s(474) =< aux(59)*s(467)
s(475) =< s(465)*s(468)
s(476) =< s(472)
s(477) =< s(473)
s(478) =< s(477)*aux(59)
s(446) =< aux(56)
s(447) =< aux(56)
s(448) =< aux(56)
s(448) =< aux(57)
s(447) =< aux(58)
s(449) =< aux(56)
s(450) =< aux(56)-2
s(451) =< aux(56)+1
s(452) =< aux(56)*2
s(453) =< s(446)*s(451)
s(454) =< s(446)*s(451)
s(455) =< s(446)*s(449)
s(456) =< aux(56)*s(449)
s(457) =< s(447)*s(450)
s(458) =< s(454)
s(459) =< s(455)
s(460) =< s(459)*aux(56)

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


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

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

* Chain [36]: 3*s(537)+1*s(538)+1*s(539)+1*s(543)+1*s(544)+1*s(547)+1*s(548)+2*s(549)+8*s(550)+4*s(551)+0
  Such that:s(534) =< V1
s(535) =< 2/3*V1
s(536) =< 2/5*V1
s(537) =< s(534)
s(538) =< s(534)
s(539) =< s(534)
s(539) =< s(535)
s(538) =< s(536)
s(540) =< s(534)
s(541) =< s(534)-2
s(542) =< s(534)+1
s(543) =< s(534)*2
s(544) =< s(537)*s(542)
s(545) =< s(537)*s(542)
s(546) =< s(537)*s(540)
s(547) =< s(534)*s(540)
s(548) =< s(538)*s(541)
s(549) =< s(545)
s(550) =< s(546)
s(551) =< s(550)*s(534)

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


#### Cost of chains of start(V1,V,V2):
* Chain [39]: 9*s(552)+5*s(553)+10*s(557)+4*s(558)+65*s(559)+18*s(560)+2*s(561)+33*s(567)+11*s(568)+11*s(569)+11*s(573)+11*s(574)+11*s(577)+11*s(578)+22*s(579)+88*s(580)+44*s(581)+12*s(595)+8*s(601)+8*s(602)+8*s(606)+8*s(607)+8*s(610)+8*s(611)+16*s(612)+64*s(613)+32*s(614)+12*s(630)+4*s(631)+4*s(632)+4*s(636)+4*s(637)+4*s(640)+4*s(641)+8*s(642)+32*s(643)+16*s(644)+3
  Such that:s(582) =< 1
s(556) =< V-V2
s(591) =< V2
s(593) =< 2/3*V2
s(594) =< 2/5*V2
aux(62) =< 2
aux(63) =< V1
aux(64) =< 2/3*V1
aux(65) =< 2/5*V1
aux(66) =< V
aux(67) =< V+1
aux(68) =< 2/3*V
aux(69) =< 2/5*V
aux(70) =< V2+1
s(552) =< aux(62)
s(559) =< aux(66)
s(553) =< aux(70)
s(595) =< s(582)
s(557) =< aux(67)
s(560) =< s(559)*aux(66)
s(601) =< aux(66)
s(602) =< aux(66)
s(602) =< aux(68)
s(601) =< aux(69)
s(603) =< aux(66)
s(604) =< aux(66)-2
s(605) =< aux(66)+1
s(606) =< aux(66)*2
s(607) =< s(559)*s(605)
s(608) =< s(559)*s(605)
s(609) =< s(559)*s(603)
s(610) =< aux(66)*s(603)
s(611) =< s(601)*s(604)
s(612) =< s(608)
s(613) =< s(609)
s(614) =< s(613)*aux(66)
s(567) =< aux(63)
s(568) =< aux(63)
s(569) =< aux(63)
s(569) =< aux(64)
s(568) =< aux(65)
s(570) =< aux(63)
s(571) =< aux(63)-2
s(572) =< aux(63)+1
s(573) =< aux(63)*2
s(574) =< s(567)*s(572)
s(575) =< s(567)*s(572)
s(576) =< s(567)*s(570)
s(577) =< aux(63)*s(570)
s(578) =< s(568)*s(571)
s(579) =< s(575)
s(580) =< s(576)
s(581) =< s(580)*aux(63)
s(630) =< s(591)
s(631) =< s(591)
s(632) =< s(591)
s(632) =< s(593)
s(631) =< s(594)
s(633) =< s(591)
s(634) =< s(591)-2
s(635) =< s(591)+1
s(636) =< s(591)*2
s(637) =< s(630)*s(635)
s(638) =< s(630)*s(635)
s(639) =< s(630)*s(633)
s(640) =< s(591)*s(633)
s(641) =< s(631)*s(634)
s(642) =< s(638)
s(643) =< s(639)
s(644) =< s(643)*s(591)
s(558) =< s(556)
s(561) =< s(558)*aux(66)

  with precondition: [] 


Closed-form bounds of start(V1,V,V2): 
-------------------------------------
* Chain [39] with precondition: [] 
    - Upper bound: nat(V1)*110+33+nat(V1)*132*nat(V1)+nat(V1)*44*nat(V1)*nat(V1)+nat(V1)*11*nat(nat(V1)+ -2)+nat(V)*121+nat(V)*114*nat(V)+nat(V)*32*nat(V)*nat(V)+nat(V)*8*nat(nat(V)+ -2)+nat(V)*2*nat(V-V2)+nat(V2)*40+nat(V2)*48*nat(V2)+nat(V2)*16*nat(V2)*nat(V2)+nat(V2)*4*nat(nat(V2)+ -2)+nat(V+1)*10+nat(V2+1)*5+nat(V-V2)*4 
    - Complexity: n^3 

### Maximum cost of start(V1,V,V2): nat(V1)*110+33+nat(V1)*132*nat(V1)+nat(V1)*44*nat(V1)*nat(V1)+nat(V1)*11*nat(nat(V1)+ -2)+nat(V)*121+nat(V)*114*nat(V)+nat(V)*32*nat(V)*nat(V)+nat(V)*8*nat(nat(V)+ -2)+nat(V)*2*nat(V-V2)+nat(V2)*40+nat(V2)*48*nat(V2)+nat(V2)*16*nat(V2)*nat(V2)+nat(V2)*4*nat(nat(V2)+ -2)+nat(V+1)*10+nat(V2+1)*5+nat(V-V2)*4 
Asymptotic class: n^3 
* Total analysis performed in 1249 ms.


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

(14)
BOUNDS(1, n^3)

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

(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(t, x, y) -> f(g(x, y), x, s(y))
   g(s(x), 0') -> t
   g(s(x), s(y)) -> g(x, y)

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

   encArg(t) -> t
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0') -> 0'
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_t -> t
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0'

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

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

(18)
Obligation:
Innermost TRS:
Rules:
f(t, x, y) -> f(g(x, y), x, s(y))
g(s(x), 0') -> t
g(s(x), s(y)) -> g(x, y)
encArg(t) -> t
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encode_t -> t
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'

Types:
f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
t :: t:s:0':cons_f:cons_g
g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
s :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
0' :: t:s:0':cons_f:cons_g
encArg :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
cons_f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
cons_g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_t :: t:s:0':cons_f:cons_g
encode_g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_s :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_0 :: t:s:0':cons_f:cons_g
hole_t:s:0':cons_f:cons_g1_4 :: t:s:0':cons_f:cons_g
gen_t:s:0':cons_f:cons_g2_4 :: Nat -> t:s:0':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(t, x, y) -> f(g(x, y), x, s(y))
g(s(x), 0') -> t
g(s(x), s(y)) -> g(x, y)
encArg(t) -> t
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encode_t -> t
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'

Types:
f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
t :: t:s:0':cons_f:cons_g
g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
s :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
0' :: t:s:0':cons_f:cons_g
encArg :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
cons_f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
cons_g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_t :: t:s:0':cons_f:cons_g
encode_g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_s :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_0 :: t:s:0':cons_f:cons_g
hole_t:s:0':cons_f:cons_g1_4 :: t:s:0':cons_f:cons_g
gen_t:s:0':cons_f:cons_g2_4 :: Nat -> t:s:0':cons_f:cons_g


Generator Equations:
gen_t:s:0':cons_f:cons_g2_4(0) <=> t
gen_t:s:0':cons_f:cons_g2_4(+(x, 1)) <=> s(gen_t:s:0':cons_f:cons_g2_4(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_t:s:0':cons_f:cons_g2_4(+(1, n4_4)), gen_t:s:0':cons_f:cons_g2_4(+(1, n4_4))) -> *3_4, rt in Omega(n4_4)

Induction Base:
g(gen_t:s:0':cons_f:cons_g2_4(+(1, 0)), gen_t:s:0':cons_f:cons_g2_4(+(1, 0)))

Induction Step:
g(gen_t:s:0':cons_f:cons_g2_4(+(1, +(n4_4, 1))), gen_t:s:0':cons_f:cons_g2_4(+(1, +(n4_4, 1)))) ->_R^Omega(1)
g(gen_t:s:0':cons_f:cons_g2_4(+(1, n4_4)), gen_t:s:0':cons_f:cons_g2_4(+(1, n4_4))) ->_IH
*3_4

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(t, x, y) -> f(g(x, y), x, s(y))
g(s(x), 0') -> t
g(s(x), s(y)) -> g(x, y)
encArg(t) -> t
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encode_t -> t
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'

Types:
f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
t :: t:s:0':cons_f:cons_g
g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
s :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
0' :: t:s:0':cons_f:cons_g
encArg :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
cons_f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
cons_g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_t :: t:s:0':cons_f:cons_g
encode_g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_s :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_0 :: t:s:0':cons_f:cons_g
hole_t:s:0':cons_f:cons_g1_4 :: t:s:0':cons_f:cons_g
gen_t:s:0':cons_f:cons_g2_4 :: Nat -> t:s:0':cons_f:cons_g


Generator Equations:
gen_t:s:0':cons_f:cons_g2_4(0) <=> t
gen_t:s:0':cons_f:cons_g2_4(+(x, 1)) <=> s(gen_t:s:0':cons_f:cons_g2_4(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(t, x, y) -> f(g(x, y), x, s(y))
g(s(x), 0') -> t
g(s(x), s(y)) -> g(x, y)
encArg(t) -> t
encArg(s(x_1)) -> s(encArg(x_1))
encArg(0') -> 0'
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encode_t -> t
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_s(x_1) -> s(encArg(x_1))
encode_0 -> 0'

Types:
f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
t :: t:s:0':cons_f:cons_g
g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
s :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
0' :: t:s:0':cons_f:cons_g
encArg :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
cons_f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
cons_g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_f :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_t :: t:s:0':cons_f:cons_g
encode_g :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_s :: t:s:0':cons_f:cons_g -> t:s:0':cons_f:cons_g
encode_0 :: t:s:0':cons_f:cons_g
hole_t:s:0':cons_f:cons_g1_4 :: t:s:0':cons_f:cons_g
gen_t:s:0':cons_f:cons_g2_4 :: Nat -> t:s:0':cons_f:cons_g


Lemmas:
g(gen_t:s:0':cons_f:cons_g2_4(+(1, n4_4)), gen_t:s:0':cons_f:cons_g2_4(+(1, n4_4))) -> *3_4, rt in Omega(n4_4)


Generator Equations:
gen_t:s:0':cons_f:cons_g2_4(0) <=> t
gen_t:s:0':cons_f:cons_g2_4(+(x, 1)) <=> s(gen_t:s:0':cons_f:cons_g2_4(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:
encArg(gen_t:s:0':cons_f:cons_g2_4(n1316_4)) -> gen_t:s:0':cons_f:cons_g2_4(n1316_4), rt in Omega(0)

Induction Base:
encArg(gen_t:s:0':cons_f:cons_g2_4(0)) ->_R^Omega(0)
t

Induction Step:
encArg(gen_t:s:0':cons_f:cons_g2_4(+(n1316_4, 1))) ->_R^Omega(0)
s(encArg(gen_t:s:0':cons_f:cons_g2_4(n1316_4))) ->_IH
s(gen_t:s:0':cons_f:cons_g2_4(c1317_4))

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

(28)
BOUNDS(1, INF)