/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), 182 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, 958 ms]
    (14) BOUNDS(1, n^2)
(15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(16) TRS for Loop Detection
    (17) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (18) BEST
        (19) proven lower bound
            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
            (21) BOUNDS(n^1, INF)
        (22) TRS for Loop Detection


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

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


The TRS R consists of the following rules:

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

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

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))


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

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


The TRS R consists of the following rules:

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

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))

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

(3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

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


The TRS R consists of the following rules:

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

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))

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

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

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


The TRS R consists of the following rules:

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

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

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

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

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

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

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

(9) CompletionProof (UPPER BOUND(ID))
The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:

   encArg(v0) -> null_encArg [0]
   encode_g(v0, v1) -> null_encode_g [0]
   encode_f(v0, v1, v2) -> null_encode_f [0]
   encode_0 -> null_encode_0 [0]
   encode_1 -> null_encode_1 [0]
   encode_s(v0) -> null_encode_s [0]
   f(v0, v1, v2) -> null_f [0]

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

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

(10)
Obligation:
Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

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

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

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

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

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

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

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

   encArg(z') -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2
   encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z') -{ 0 }-> 1 :|: z' = 1
   encArg(z') -{ 0 }-> 0 :|: z' = 0
   encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encArg(z') -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z' = 1 + x_1
   encode_0 -{ 0 }-> 0 :|: 
   encode_1 -{ 0 }-> 1 :|: 
   encode_1 -{ 0 }-> 0 :|: 
   encode_f(z', z'', z1) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z1 = x_3, z' = x_1, x_3 >= 0, x_2 >= 0, z'' = x_2
   encode_f(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0
   encode_g(z', z'') -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2
   encode_g(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0
   encode_s(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encode_s(z') -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z' = x_1
   f(z', z'', z1) -{ 1 }-> f(1 + x, x, x) :|: x >= 0, z'' = 1, z1 = x, z' = 0
   f(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0
   f(z', z'', z1) -{ 1 }-> 1 + f(0, 1, z) :|: z >= 0, z' = x, z'' = y, x >= 0, y >= 0, z1 = 1 + z
   g(z', z'') -{ 1 }-> x :|: z' = x, z'' = y, x >= 0, y >= 0
   g(z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0

Only complete derivations are relevant for the runtime complexity.

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

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

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


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

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

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

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

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


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

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

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


### Specialization of cost equations g/3 
* CE 10 is refined into CE [30] 
* CE 9 is refined into CE [31] 


### Cost equations --> "Loop" of g/3 
* CEs [30] --> Loop 20 
* CEs [31] --> Loop 21 

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

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


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


### Cost equations --> "Loop" of encArg/2 
* CEs [38] --> Loop 22 
* CEs [37] --> Loop 23 
* CEs [36] --> Loop 24 
* CEs [35] --> Loop 25 
* CEs [34] --> Loop 26 
* CEs [32] --> Loop 27 
* CEs [33] --> Loop 28 

### Ranking functions of CR encArg(V,Out) 
* RF of phase [22,23,24,25,26]: [V]

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


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


### Cost equations --> "Loop" of fun/3 
* CEs [39,41] --> Loop 29 
* CEs [40,44] --> Loop 30 
* CEs [42,43,45,46,47] --> Loop 31 

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

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


### Specialization of cost equations fun1/4 
* CE 21 is refined into CE [48,49,50,51,52,53,54,55,56,57,58,59,60,61] 
* CE 22 is refined into CE [62] 


### Cost equations --> "Loop" of fun1/4 
* CEs [49,56] --> Loop 32 
* CEs [53,60] --> Loop 33 
* CEs [48,50,51,52,54,55,57,58,59,61,62] --> Loop 34 

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

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


### Specialization of cost equations fun3/1 
* CE 23 is refined into CE [63] 
* CE 24 is refined into CE [64] 


### Cost equations --> "Loop" of fun3/1 
* CEs [63] --> Loop 35 
* CEs [64] --> Loop 36 

### Ranking functions of CR fun3(Out) 

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


### Specialization of cost equations fun4/2 
* CE 25 is refined into CE [65,66] 
* CE 26 is refined into CE [67] 


### Cost equations --> "Loop" of fun4/2 
* CEs [65] --> Loop 37 
* CEs [66] --> Loop 38 
* CEs [67] --> Loop 39 

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

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


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


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

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

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


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

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

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

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


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

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


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

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

* Chain [multiple([22,23,24,25,26],[[28],[27]])]: 2*it(23)+1*s(15)+1*s(16)+0
  Such that:aux(11) =< V/2
aux(18) =< V
it(22) =< aux(18)
it(23) =< aux(18)
aux(12) =< aux(11)*2
s(19) =< it(22)*aux(11)
s(18) =< it(22)*aux(12)
s(15) =< s(18)
s(20) =< s(18)*(1/2)
s(16) =< s(20)+s(19)
s(16) =< s(18)+aux(18)

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


#### Cost of chains of fun(V,V1,Out):
* Chain [31]: 2*s(33)+1*s(37)+1*s(39)+2*s(42)+1*s(46)+1*s(48)+1
  Such that:s(31) =< V
s(32) =< V/2
s(40) =< V1
s(41) =< V1/2
s(33) =< s(31)
s(34) =< s(32)*2
s(35) =< s(31)*s(32)
s(36) =< s(31)*s(34)
s(37) =< s(36)
s(38) =< s(36)*(1/2)
s(39) =< s(38)+s(35)
s(39) =< s(36)+s(31)
s(42) =< s(40)
s(43) =< s(41)*2
s(44) =< s(40)*s(41)
s(45) =< s(40)*s(43)
s(46) =< s(45)
s(47) =< s(45)*(1/2)
s(48) =< s(47)+s(44)
s(48) =< s(45)+s(40)

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

* Chain [30]: 2*s(51)+1*s(55)+1*s(57)+4*s(60)+2*s(64)+2*s(66)+1
  Such that:s(49) =< V
s(50) =< V/2
aux(19) =< V1
aux(20) =< V1/2
s(60) =< aux(19)
s(61) =< aux(20)*2
s(62) =< aux(19)*aux(20)
s(63) =< aux(19)*s(61)
s(64) =< s(63)
s(65) =< s(63)*(1/2)
s(66) =< s(65)+s(62)
s(66) =< s(63)+aux(19)
s(51) =< s(49)
s(52) =< s(50)*2
s(53) =< s(49)*s(50)
s(54) =< s(49)*s(52)
s(55) =< s(54)
s(56) =< s(54)*(1/2)
s(57) =< s(56)+s(53)
s(57) =< s(54)+s(49)

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

* Chain [29]: 4*s(78)+2*s(82)+2*s(84)+2*s(87)+1*s(91)+1*s(93)+1
  Such that:s(85) =< V1
s(86) =< V1/2
aux(21) =< V
aux(22) =< V/2
s(87) =< s(85)
s(88) =< s(86)*2
s(89) =< s(85)*s(86)
s(90) =< s(85)*s(88)
s(91) =< s(90)
s(92) =< s(90)*(1/2)
s(93) =< s(92)+s(89)
s(93) =< s(90)+s(85)
s(78) =< aux(21)
s(79) =< aux(22)*2
s(80) =< aux(21)*aux(22)
s(81) =< aux(21)*s(79)
s(82) =< s(81)
s(83) =< s(81)*(1/2)
s(84) =< s(83)+s(80)
s(84) =< s(81)+aux(21)

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


#### Cost of chains of fun1(V,V1,V7,Out):
* Chain [34]: 10*s(105)+5*s(109)+5*s(111)+12*s(114)+6*s(118)+6*s(120)+8*s(123)+4*s(127)+4*s(129)+2*s(173)+0
  Such that:aux(27) =< 1
aux(28) =< V
aux(29) =< V/2
aux(30) =< V1
aux(31) =< V1/2
aux(32) =< V7
aux(33) =< V7/2
s(173) =< aux(31)
s(173) =< aux(27)
s(114) =< aux(30)
s(115) =< aux(31)*2
s(116) =< aux(30)*aux(31)
s(117) =< aux(30)*s(115)
s(118) =< s(117)
s(119) =< s(117)*(1/2)
s(120) =< s(119)+s(116)
s(120) =< s(117)+aux(30)
s(105) =< aux(28)
s(106) =< aux(29)*2
s(107) =< aux(28)*aux(29)
s(108) =< aux(28)*s(106)
s(109) =< s(108)
s(110) =< s(108)*(1/2)
s(111) =< s(110)+s(107)
s(111) =< s(108)+aux(28)
s(123) =< aux(32)
s(124) =< aux(33)*2
s(125) =< aux(32)*aux(33)
s(126) =< aux(32)*s(124)
s(127) =< s(126)
s(128) =< s(126)*(1/2)
s(129) =< s(128)+s(125)
s(129) =< s(126)+aux(32)

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

* Chain [33]: 2*s(256)+1*s(260)+1*s(262)+6*s(265)+2*s(269)+2*s(271)+2*s(279)+0
  Such that:s(254) =< V
s(255) =< V/2
aux(36) =< 1
aux(37) =< V7
aux(38) =< V7/2
s(265) =< aux(37)
s(278) =< aux(37)*(1/2)
s(279) =< s(278)
s(279) =< aux(37)+aux(36)
s(266) =< aux(38)*2
s(267) =< aux(37)*aux(38)
s(268) =< aux(37)*s(266)
s(269) =< s(268)
s(270) =< s(268)*(1/2)
s(271) =< s(270)+s(267)
s(271) =< s(268)+aux(37)
s(256) =< s(254)
s(257) =< s(255)*2
s(258) =< s(254)*s(255)
s(259) =< s(254)*s(257)
s(260) =< s(259)
s(261) =< s(259)*(1/2)
s(262) =< s(261)+s(258)
s(262) =< s(259)+s(254)

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

* Chain [32]: 2*s(299)+1*s(303)+1*s(305)+4*s(308)+2*s(312)+2*s(314)+6*s(317)+2*s(321)+2*s(323)+2*s(331)+0
  Such that:s(297) =< V
s(298) =< V/2
aux(43) =< 1
aux(44) =< V1
aux(45) =< V1/2
aux(46) =< V7
aux(47) =< V7/2
s(317) =< aux(46)
s(330) =< aux(46)*(1/2)
s(331) =< s(330)+aux(45)
s(331) =< aux(46)+aux(43)
s(318) =< aux(47)*2
s(319) =< aux(46)*aux(47)
s(320) =< aux(46)*s(318)
s(321) =< s(320)
s(322) =< s(320)*(1/2)
s(323) =< s(322)+s(319)
s(323) =< s(320)+aux(46)
s(308) =< aux(44)
s(309) =< aux(45)*2
s(310) =< aux(44)*aux(45)
s(311) =< aux(44)*s(309)
s(312) =< s(311)
s(313) =< s(311)*(1/2)
s(314) =< s(313)+s(310)
s(314) =< s(311)+aux(44)
s(299) =< s(297)
s(300) =< s(298)*2
s(301) =< s(297)*s(298)
s(302) =< s(297)*s(300)
s(303) =< s(302)
s(304) =< s(302)*(1/2)
s(305) =< s(304)+s(301)
s(305) =< s(302)+s(297)

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


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

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


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

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

* Chain [37]: 2*s(360)+1*s(364)+1*s(366)+0
  Such that:s(358) =< V
s(359) =< V/2
s(360) =< s(358)
s(361) =< s(359)*2
s(362) =< s(358)*s(359)
s(363) =< s(358)*s(361)
s(364) =< s(363)
s(365) =< s(363)*(1/2)
s(366) =< s(365)+s(362)
s(366) =< s(363)+s(358)

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


#### Cost of chains of start(V,V1,V7):
* Chain [40]: 21*s(372)+1*s(374)+26*s(377)+13*s(381)+13*s(383)+24*s(395)+12*s(399)+12*s(401)+2*s(445)+8*s(464)+8*s(466)+2*s(474)+2*s(497)+1
  Such that:s(367) =< -V+1
s(368) =< -V/2+V1/2
aux(49) =< 1
aux(50) =< V
aux(51) =< V/2
aux(52) =< V1
aux(53) =< V1/2
aux(54) =< V7
aux(55) =< V7/2
s(445) =< aux(53)
s(445) =< aux(49)
s(395) =< aux(52)
s(396) =< aux(53)*2
s(397) =< aux(52)*aux(53)
s(398) =< aux(52)*s(396)
s(399) =< s(398)
s(400) =< s(398)*(1/2)
s(401) =< s(400)+s(397)
s(401) =< s(398)+aux(52)
s(377) =< aux(50)
s(378) =< aux(51)*2
s(379) =< aux(50)*aux(51)
s(380) =< aux(50)*s(378)
s(381) =< s(380)
s(382) =< s(380)*(1/2)
s(383) =< s(382)+s(379)
s(383) =< s(380)+aux(50)
s(372) =< aux(54)
s(461) =< aux(55)*2
s(462) =< aux(54)*aux(55)
s(463) =< aux(54)*s(461)
s(464) =< s(463)
s(465) =< s(463)*(1/2)
s(466) =< s(465)+s(462)
s(466) =< s(463)+aux(54)
s(373) =< aux(54)*(1/2)
s(474) =< s(373)
s(474) =< aux(54)+aux(49)
s(497) =< s(373)+aux(53)
s(497) =< aux(54)+aux(49)
s(374) =< s(373)+s(368)
s(374) =< aux(54)+s(367)

  with precondition: [] 


Closed-form bounds of start(V,V1,V7): 
-------------------------------------
* Chain [40] with precondition: [] 
    - Upper bound: nat(V)*26+3+nat(V)*52*nat(V/2)+nat(V1)*24+nat(V1)*48*nat(V1/2)+47/2*nat(V7)+nat(V7)*32*nat(V7/2)+nat(-V/2+V1/2)+nat(V1/2)*2 
    - Complexity: n^2 

### Maximum cost of start(V,V1,V7): nat(V)*26+3+nat(V)*52*nat(V/2)+nat(V1)*24+nat(V1)*48*nat(V1/2)+47/2*nat(V7)+nat(V7)*32*nat(V7/2)+nat(-V/2+V1/2)+nat(V1/2)*2 
Asymptotic class: n^2 
* Total analysis performed in 804 ms.


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

(14)
BOUNDS(1, n^2)

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

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

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

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


The TRS R consists of the following rules:

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

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))

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

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

The rewrite sequence

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

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

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

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




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

(18)
Complex Obligation (BEST)

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

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

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


The TRS R consists of the following rules:

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

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))

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

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

(21)
BOUNDS(n^1, INF)

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

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

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


The TRS R consists of the following rules:

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

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

   encArg(0) -> 0
   encArg(1) -> 1
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_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_0 -> 0
   encode_1 -> 1
   encode_s(x_1) -> s(encArg(x_1))

Rewrite Strategy: INNERMOST