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

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 192 ms]
(4) CpxRelTRS
(5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
(6) CpxRelTRS
    (7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxWeightedTrs
    (9) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CpxWeightedTrs
    (11) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) CpxTypedWeightedTrs
    (13) CompletionProof [UPPER BOUND(ID), 0 ms]
    (14) CpxTypedWeightedCompleteTrs
    (15) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (16) CpxRNTS
    (17) CompleteCoflocoProof [FINISHED, 1361 ms]
    (18) BOUNDS(1, n^1)
(19) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(20) CpxRelTRS
    (21) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (22) typed CpxTrs
    (23) OrderProof [LOWER BOUND(ID), 0 ms]
    (24) typed CpxTrs
    (25) RewriteLemmaProof [LOWER BOUND(ID), 215 ms]
    (26) proven lower bound
    (27) LowerBoundPropagationProof [FINISHED, 0 ms]
    (28) BOUNDS(n^1, INF)


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

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


The TRS R consists of the following rules:

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

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(2) -> 2
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_0) -> 0
   encArg(cons_1) -> 1
   encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3))
   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_2 -> 2
   encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3))


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

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


The TRS R consists of the following rules:

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

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

   encArg(2) -> 2
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_0) -> 0
   encArg(cons_1) -> 1
   encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3))
   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_2 -> 2
   encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3))

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


The TRS R consists of the following rules:

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

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

   encArg(2) -> 2
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_0) -> 0
   encArg(cons_1) -> 1
   encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3))
   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_2 -> 2
   encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3))

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

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

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


The TRS R consists of the following rules:

   f(x, y, z) -> 2
   0 -> 2
   1 -> 2
   g(x, x, y) -> y
   g(x, y, y) -> x
   f(c_0, c_1, x) -> f(x, x, x)

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

   encArg(2) -> 2
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_0) -> 0
   encArg(cons_1) -> 1
   encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3))
   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_2 -> 2
   encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3))
   0 -> c_0
   1 -> c_1

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

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

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


The TRS R consists of the following rules:

   f(x, y, z) -> 2 [1]
   0 -> 2 [1]
   1 -> 2 [1]
   g(x, x, y) -> y [1]
   g(x, y, y) -> x [1]
   f(c_0, c_1, x) -> f(x, x, x) [1]
   encArg(2) -> 2 [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_0) -> 0 [0]
   encArg(cons_1) -> 1 [0]
   encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) [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_2 -> 2 [0]
   encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   0 -> c_0 [0]
   1 -> c_1 [0]

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

(9) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
Renamed defined symbols to avoid conflicts with arithmetic symbols:

0 => 0'
1 => 1'

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

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


The TRS R consists of the following rules:

   f(x, y, z) -> 2 [1]
   0' -> 2 [1]
   1' -> 2 [1]
   g(x, x, y) -> y [1]
   g(x, y, y) -> x [1]
   f(c_0, c_1, x) -> f(x, x, x) [1]
   encArg(2) -> 2 [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_0) -> 0' [0]
   encArg(cons_1) -> 1' [0]
   encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) [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_2 -> 2 [0]
   encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   0' -> c_0 [0]
   1' -> c_1 [0]

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

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

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

   f(x, y, z) -> 2 [1]
   0' -> 2 [1]
   1' -> 2 [1]
   g(x, x, y) -> y [1]
   g(x, y, y) -> x [1]
   f(c_0, c_1, x) -> f(x, x, x) [1]
   encArg(2) -> 2 [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_0) -> 0' [0]
   encArg(cons_1) -> 1' [0]
   encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) [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_2 -> 2 [0]
   encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   0' -> c_0 [0]
   1' -> c_1 [0]

The TRS has the following type information:
f :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
2 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
0' :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
1' :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
g :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
c_0 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
c_1 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
encArg :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
cons_f :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
cons_0 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
cons_1 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
cons_g :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
encode_f :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
encode_0 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
encode_1 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
encode_2 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g
encode_g :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g

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

(13) 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_0 -> null_encode_0 [0]
   encode_1 -> null_encode_1 [0]
   encode_2 -> null_encode_2 [0]
   encode_g(v0, v1, v2) -> null_encode_g [0]
   0' -> null_0' [0]
   1' -> null_1' [0]
   g(v0, v1, v2) -> null_g [0]

And the following fresh constants:    null_encArg, null_encode_f, null_encode_0, null_encode_1, null_encode_2, null_encode_g, null_0', null_1', null_g

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

(14)
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(x, y, z) -> 2 [1]
   0' -> 2 [1]
   1' -> 2 [1]
   g(x, x, y) -> y [1]
   g(x, y, y) -> x [1]
   f(c_0, c_1, x) -> f(x, x, x) [1]
   encArg(2) -> 2 [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_0) -> 0' [0]
   encArg(cons_1) -> 1' [0]
   encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) [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_2 -> 2 [0]
   encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   0' -> c_0 [0]
   1' -> c_1 [0]
   encArg(v0) -> null_encArg [0]
   encode_f(v0, v1, v2) -> null_encode_f [0]
   encode_0 -> null_encode_0 [0]
   encode_1 -> null_encode_1 [0]
   encode_2 -> null_encode_2 [0]
   encode_g(v0, v1, v2) -> null_encode_g [0]
   0' -> null_0' [0]
   1' -> null_1' [0]
   g(v0, v1, v2) -> null_g [0]

The TRS has the following type information:
f :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
2 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
0' :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
1' :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
g :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
c_0 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
c_1 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
encArg :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
cons_f :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
cons_0 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
cons_1 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
cons_g :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
encode_f :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
encode_0 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
encode_1 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
encode_2 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
encode_g :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g -> 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
null_encArg :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
null_encode_f :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
null_encode_0 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
null_encode_1 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
null_encode_2 :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
null_encode_g :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
null_0' :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
null_1' :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g
null_g :: 2:c_0:c_1:cons_f:cons_0:cons_1:cons_g:null_encArg:null_encode_f:null_encode_0:null_encode_1:null_encode_2:null_encode_g:null_0':null_1':null_g

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

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

   2 => 0
   c_0 => 1
   c_1 => 2
   cons_0 => 3
   cons_1 => 4
   null_encArg => 0
   null_encode_f => 0
   null_encode_0 => 0
   null_encode_1 => 0
   null_encode_2 => 0
   null_encode_g => 0
   null_0' => 0
   null_1' => 0
   null_g => 0

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

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

   0' -{ 0 }-> 1 :|: 
   0' -{ 1 }-> 0 :|: 
   0' -{ 0 }-> 0 :|: 
   1' -{ 0 }-> 2 :|: 
   1' -{ 1 }-> 0 :|: 
   1' -{ 0 }-> 0 :|: 
   encArg(z') -{ 0 }-> g(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 }-> 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' = 4
   encArg(z') -{ 0 }-> 0' :|: z' = 3
   encArg(z') -{ 0 }-> 0 :|: z' = 0
   encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0
   encode_0 -{ 0 }-> 0' :|: 
   encode_0 -{ 0 }-> 0 :|: 
   encode_1 -{ 0 }-> 1' :|: 
   encode_1 -{ 0 }-> 0 :|: 
   encode_2 -{ 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'', z1) -{ 0 }-> g(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_g(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0
   f(z', z'', z1) -{ 1 }-> f(x, x, x) :|: x >= 0, z' = 1, z'' = 2, z1 = x
   f(z', z'', z1) -{ 1 }-> 0 :|: z1 = z, z >= 0, z' = x, z'' = y, x >= 0, y >= 0
   g(z', z'', z1) -{ 1 }-> x :|: z1 = y, z' = x, z'' = y, x >= 0, y >= 0
   g(z', z'', z1) -{ 1 }-> y :|: z1 = y, z' = x, x >= 0, y >= 0, z'' = x
   g(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0

Only complete derivations are relevant for the runtime complexity.

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

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

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


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

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

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

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

### Specialization of cost equations f/4 
* CE 12 is refined into CE [35] 
* CE 11 is refined into CE [36] 


### Cost equations --> "Loop" of f/4 
* CEs [36] --> Loop 19 
* CEs [35] --> Loop 20 

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

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


### Specialization of cost equations fun/1 
* CE 14 is refined into CE [37] 
* CE 13 is refined into CE [38] 
* CE 15 is refined into CE [39] 


### Cost equations --> "Loop" of fun/1 
* CEs [37] --> Loop 21 
* CEs [38,39] --> Loop 22 

### Ranking functions of CR fun(Out) 

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


### Specialization of cost equations fun1/1 
* CE 17 is refined into CE [40] 
* CE 16 is refined into CE [41] 
* CE 18 is refined into CE [42] 


### Cost equations --> "Loop" of fun1/1 
* CEs [40] --> Loop 23 
* CEs [41,42] --> Loop 24 

### Ranking functions of CR fun1(Out) 

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


### Specialization of cost equations g/4 
* CE 20 is refined into CE [43] 
* CE 19 is refined into CE [44] 
* CE 21 is refined into CE [45] 


### Cost equations --> "Loop" of g/4 
* CEs [43] --> Loop 25 
* CEs [44] --> Loop 26 
* CEs [45] --> Loop 27 

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

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


### Specialization of cost equations encArg/2 
* CE 22 is refined into CE [46] 
* CE 25 is refined into CE [47,48] 
* CE 24 is refined into CE [49,50] 
* CE 23 is refined into CE [51] 
* CE 26 is refined into CE [52,53,54] 


### Cost equations --> "Loop" of encArg/2 
* CEs [53] --> Loop 28 
* CEs [54] --> Loop 29 
* CEs [51,52] --> Loop 30 
* CEs [48] --> Loop 31 
* CEs [47] --> Loop 32 
* CEs [50] --> Loop 33 
* CEs [46,49] --> Loop 34 

### Ranking functions of CR encArg(V,Out) 
* RF of phase [28,29,30]: [V]

#### Partial ranking functions of CR encArg(V,Out) 
* Partial RF of phase [28,29,30]:
  - RF of loop [28:1,28:2,28:3,29:1,29:2,29:3,30:1,30:2,30:3]:
    V


### Specialization of cost equations fun2/4 
* CE 27 is refined into CE [55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81] 
* CE 28 is refined into CE [82] 


### Cost equations --> "Loop" of fun2/4 
* CEs [61,62,63,70,71,72] --> Loop 35 
* CEs [57,60,66,69,75,78] --> Loop 36 
* CEs [55,56,58,59,64,65,67,68,73,74,76,77,79,80,81,82] --> Loop 37 

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

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


### Specialization of cost equations fun3/1 
* CE 29 is refined into CE [83,84] 
* CE 30 is refined into CE [85] 


### Cost equations --> "Loop" of fun3/1 
* CEs [84] --> Loop 38 
* CEs [83,85] --> Loop 39 

### Ranking functions of CR fun3(Out) 

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


### Specialization of cost equations fun4/1 
* CE 31 is refined into CE [86,87] 
* CE 32 is refined into CE [88] 


### Cost equations --> "Loop" of fun4/1 
* CEs [87] --> Loop 40 
* CEs [86,88] --> Loop 41 

### Ranking functions of CR fun4(Out) 

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


### Specialization of cost equations fun6/4 
* CE 33 is refined into CE [89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157] 
* CE 34 is refined into CE [158] 


### Cost equations --> "Loop" of fun6/4 
* CEs [97] --> Loop 42 
* CEs [108] --> Loop 43 
* CEs [107] --> Loop 44 
* CEs [91,94,100,103,112,113] --> Loop 45 
* CEs [106,109,110,111,131,132,133,134,135] --> Loop 46 
* CEs [137] --> Loop 47 
* CEs [96,105,121,130,143,144] --> Loop 48 
* CEs [95,104,120,122,129,142,149] --> Loop 49 
* CEs [90,99,115,124,151,152] --> Loop 50 
* CEs [138,141,146,148,156,157] --> Loop 51 
* CEs [89,92,93,98,101,102,114,116,117,118,119,123,125,126,127,128,136,139,140,145,147,150,153,154,155,158] --> Loop 52 

### Ranking functions of CR fun6(V,V1,V5,Out) 

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


### Specialization of cost equations start/3 
* CE 1 is refined into CE [159] 
* CE 2 is refined into CE [160,161] 
* CE 3 is refined into CE [162,163] 
* CE 4 is refined into CE [164,165,166] 
* CE 5 is refined into CE [167,168,169] 
* CE 6 is refined into CE [170,171] 
* CE 7 is refined into CE [172,173] 
* CE 8 is refined into CE [174,175] 
* CE 9 is refined into CE [176] 
* CE 10 is refined into CE [177,178,179,180,181,182,183,184] 


### Cost equations --> "Loop" of start/3 
* CEs [159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184] --> Loop 53 

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

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


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

#### Cost of chains of f(V,V1,V5,Out):
* Chain [20,19]: 2
  with precondition: [V=1,V1=2,Out=0,V5>=0] 

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


#### Cost of chains of fun(Out):
* Chain [22]: 1
  with precondition: [Out=0] 

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


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

* Chain [23]: 0
  with precondition: [Out=2] 


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

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

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


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

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

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

* Chain [31]: 0
  with precondition: [V=4,Out=2] 

* Chain [multiple([28,29,30],[[34],[33],[32],[31]])]: 4*it(28)+1*it([32])+1*it([34])+0
  Such that:it([34]) =< 2*V+1
aux(1) =< V
aux(2) =< 2/9*V+1/9
it(28) =< aux(1)
it([32]) =< aux(1)
it([32]) =< aux(2)

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


#### Cost of chains of fun2(V,V1,V5,Out):
* Chain [37]: 4*s(7)+16*s(9)+4*s(10)+6*s(12)+24*s(14)+6*s(15)+7*s(17)+28*s(19)+7*s(20)+5
  Such that:aux(3) =< V
aux(4) =< 2*V+1
aux(5) =< 2/9*V+1/9
aux(6) =< V1
aux(7) =< 2*V1+1
aux(8) =< 2/9*V1+1/9
aux(9) =< V5
aux(10) =< 2*V5+1
aux(11) =< 2/9*V5+1/9
s(7) =< aux(4)
s(12) =< aux(7)
s(17) =< aux(10)
s(19) =< aux(9)
s(20) =< aux(9)
s(20) =< aux(11)
s(14) =< aux(6)
s(15) =< aux(6)
s(15) =< aux(8)
s(9) =< aux(3)
s(10) =< aux(3)
s(10) =< aux(5)

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

* Chain [36]: 2*s(92)+8*s(94)+2*s(95)+3*s(97)+12*s(99)+3*s(100)+4
  Such that:aux(12) =< V
aux(13) =< 2*V+1
aux(14) =< 2/9*V+1/9
aux(15) =< V1
aux(16) =< 2*V1+1
aux(17) =< 2/9*V1+1/9
s(92) =< aux(13)
s(97) =< aux(16)
s(99) =< aux(15)
s(100) =< aux(15)
s(100) =< aux(17)
s(94) =< aux(12)
s(95) =< aux(12)
s(95) =< aux(14)

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

* Chain [35]: 3*s(117)+12*s(119)+3*s(120)+2*s(122)+8*s(124)+2*s(125)+4
  Such that:aux(18) =< V
aux(19) =< 2*V+1
aux(20) =< 2/9*V+1/9
aux(21) =< V5
aux(22) =< 2*V5+1
aux(23) =< 2/9*V5+1/9
s(117) =< aux(19)
s(122) =< aux(22)
s(124) =< aux(21)
s(125) =< aux(21)
s(125) =< aux(23)
s(119) =< aux(18)
s(120) =< aux(18)
s(120) =< aux(20)

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


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

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


#### Cost of chains of fun4(Out):
* Chain [41]: 1
  with precondition: [Out=0] 

* Chain [40]: 0
  with precondition: [Out=2] 


#### Cost of chains of fun6(V,V1,V5,Out):
* Chain [52]: 6*s(172)+24*s(174)+6*s(175)+11*s(177)+44*s(179)+11*s(180)+9*s(182)+36*s(184)+9*s(185)+4
  Such that:aux(30) =< V
aux(31) =< 2*V+1
aux(32) =< 2/9*V+1/9
aux(33) =< V1
aux(34) =< 2*V1+1
aux(35) =< 2/9*V1+1/9
aux(36) =< V5
aux(37) =< 2*V5+1
aux(38) =< 2/9*V5+1/9
s(172) =< aux(31)
s(177) =< aux(34)
s(182) =< aux(37)
s(184) =< aux(36)
s(185) =< aux(36)
s(185) =< aux(38)
s(179) =< aux(33)
s(180) =< aux(33)
s(180) =< aux(35)
s(174) =< aux(30)
s(175) =< aux(30)
s(175) =< aux(32)

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

* Chain [51]: 2*s(302)+8*s(304)+2*s(305)+2*s(307)+8*s(309)+2*s(310)+3
  Such that:aux(39) =< V1
aux(40) =< 2*V1+1
aux(41) =< 2/9*V1+1/9
aux(42) =< V5
aux(43) =< 2*V5+1
aux(44) =< 2/9*V5+1/9
s(302) =< aux(40)
s(307) =< aux(43)
s(309) =< aux(42)
s(310) =< aux(42)
s(310) =< aux(44)
s(304) =< aux(39)
s(305) =< aux(39)
s(305) =< aux(41)

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

* Chain [50]: 2*s(322)+8*s(324)+2*s(325)+2*s(327)+8*s(329)+2*s(330)+6*s(332)+24*s(334)+6*s(335)+3
  Such that:aux(45) =< V
aux(46) =< 2*V+1
aux(47) =< 2/9*V+1/9
aux(48) =< V1
aux(49) =< 2*V1+1
aux(50) =< 2/9*V1+1/9
aux(51) =< V5
aux(52) =< 2*V5+1
aux(53) =< 2/9*V5+1/9
s(322) =< aux(46)
s(327) =< aux(49)
s(332) =< aux(52)
s(334) =< aux(51)
s(335) =< aux(51)
s(335) =< aux(53)
s(329) =< aux(48)
s(330) =< aux(48)
s(330) =< aux(50)
s(324) =< aux(45)
s(325) =< aux(45)
s(325) =< aux(47)

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

* Chain [49]: 2*s(372)+8*s(374)+2*s(375)+4*s(377)+16*s(379)+4*s(380)+2
  Such that:aux(54) =< V
aux(55) =< 2*V+1
aux(56) =< 2/9*V+1/9
aux(57) =< V1
aux(58) =< 2*V1+1
aux(59) =< 2/9*V1+1/9
s(372) =< aux(55)
s(377) =< aux(58)
s(379) =< aux(57)
s(380) =< aux(57)
s(380) =< aux(59)
s(374) =< aux(54)
s(375) =< aux(54)
s(375) =< aux(56)

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

* Chain [48]: 2*s(402)+8*s(404)+2*s(405)+4*s(407)+16*s(409)+4*s(410)+3
  Such that:aux(60) =< V
aux(61) =< 2*V+1
aux(62) =< 2/9*V+1/9
aux(63) =< V1
aux(64) =< 2*V1+1
aux(65) =< 2/9*V1+1/9
s(402) =< aux(61)
s(407) =< aux(64)
s(409) =< aux(63)
s(410) =< aux(63)
s(410) =< aux(65)
s(404) =< aux(60)
s(405) =< aux(60)
s(405) =< aux(62)

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

* Chain [47]: 1*s(432)+4*s(434)+1*s(435)+1*s(437)+4*s(439)+1*s(440)+1
  Such that:s(431) =< V1
s(432) =< 2*V1+1
s(433) =< 2/9*V1+1/9
s(436) =< V5
s(437) =< 2*V5+1
s(438) =< 2/9*V5+1/9
s(439) =< s(436)
s(440) =< s(436)
s(440) =< s(438)
s(434) =< s(431)
s(435) =< s(431)
s(435) =< s(433)

  with precondition: [V=4,2>=Out,V1>=5,Out>=0,V5>=2*Out+1] 

* Chain [46]: 4*s(442)+16*s(444)+4*s(445)+3*s(447)+12*s(449)+3*s(450)+2
  Such that:aux(66) =< V
aux(67) =< 2*V+1
aux(68) =< 2/9*V+1/9
aux(69) =< V5
aux(70) =< 2*V5+1
aux(71) =< 2/9*V5+1/9
s(442) =< aux(67)
s(447) =< aux(70)
s(449) =< aux(69)
s(450) =< aux(69)
s(450) =< aux(71)
s(444) =< aux(66)
s(445) =< aux(66)
s(445) =< aux(68)

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

* Chain [45]: 6*s(477)+24*s(479)+6*s(480)+2*s(482)+8*s(484)+2*s(485)+2*s(487)+8*s(489)+2*s(490)+3
  Such that:aux(72) =< V
aux(73) =< 2*V+1
aux(74) =< 2/9*V+1/9
aux(75) =< V1
aux(76) =< 2*V1+1
aux(77) =< 2/9*V1+1/9
aux(78) =< V5
aux(79) =< 2*V5+1
aux(80) =< 2/9*V5+1/9
s(477) =< aux(73)
s(482) =< aux(76)
s(487) =< aux(79)
s(489) =< aux(78)
s(490) =< aux(78)
s(490) =< aux(80)
s(484) =< aux(75)
s(485) =< aux(75)
s(485) =< aux(77)
s(479) =< aux(72)
s(480) =< aux(72)
s(480) =< aux(74)

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

* Chain [44]: 1*s(527)+4*s(529)+1*s(530)+1*s(532)+4*s(534)+1*s(535)+1
  Such that:s(526) =< V
s(527) =< 2*V+1
s(528) =< 2/9*V+1/9
s(531) =< V5
s(532) =< 2*V5+1
s(533) =< 2/9*V5+1/9
s(534) =< s(531)
s(535) =< s(531)
s(535) =< s(533)
s(529) =< s(526)
s(530) =< s(526)
s(530) =< s(528)

  with precondition: [V1=4,2>=Out,V>=5,Out>=0,V5>=2*Out+1] 

* Chain [43]: 1*s(537)+4*s(539)+1*s(540)+1*s(542)+4*s(544)+1*s(545)+1
  Such that:s(536) =< V
s(537) =< 2*V+1
s(538) =< 2/9*V+1/9
s(541) =< V5
s(542) =< 2*V5+1
s(543) =< 2/9*V5+1/9
s(544) =< s(541)
s(545) =< s(541)
s(545) =< s(543)
s(539) =< s(536)
s(540) =< s(536)
s(540) =< s(538)

  with precondition: [V1=4,2>=Out,V5>=5,Out>=0,V>=2*Out+1] 

* Chain [42]: 1*s(547)+4*s(549)+1*s(550)+1*s(552)+4*s(554)+1*s(555)+1
  Such that:s(546) =< V
s(547) =< 2*V+1
s(548) =< 2/9*V+1/9
s(551) =< V1
s(552) =< 2*V1+1
s(553) =< 2/9*V1+1/9
s(554) =< s(551)
s(555) =< s(551)
s(555) =< s(553)
s(549) =< s(546)
s(550) =< s(546)
s(550) =< s(548)

  with precondition: [V5=4,2>=Out,V1>=5,Out>=0,V>=2*Out+1] 


#### Cost of chains of start(V,V1,V5):
* Chain [53]: 35*s(643)+140*s(645)+35*s(646)+34*s(657)+136*s(658)+34*s(659)+36*s(662)+144*s(663)+36*s(664)+5
  Such that:aux(99) =< V
aux(100) =< 2*V+1
aux(101) =< 2/9*V+1/9
aux(102) =< V1
aux(103) =< 2*V1+1
aux(104) =< 2/9*V1+1/9
aux(105) =< V5
aux(106) =< 2*V5+1
aux(107) =< 2/9*V5+1/9
s(643) =< aux(100)
s(662) =< aux(103)
s(657) =< aux(106)
s(645) =< aux(99)
s(646) =< aux(99)
s(646) =< aux(101)
s(658) =< aux(105)
s(659) =< aux(105)
s(659) =< aux(107)
s(663) =< aux(102)
s(664) =< aux(102)
s(664) =< aux(104)

  with precondition: [] 


Closed-form bounds of start(V,V1,V5): 
-------------------------------------
* Chain [53] with precondition: [] 
    - Upper bound: nat(V)*175+5+nat(V1)*180+nat(V5)*170+nat(2*V+1)*35+nat(2*V1+1)*36+nat(2*V5+1)*34 
    - Complexity: n 

### Maximum cost of start(V,V1,V5): nat(V)*175+5+nat(V1)*180+nat(V5)*170+nat(2*V+1)*35+nat(2*V1+1)*36+nat(2*V5+1)*34 
Asymptotic class: n 
* Total analysis performed in 1197 ms.


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

(18)
BOUNDS(1, n^1)

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

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

(20)
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(0', 1', x) -> f(x, x, x)
   f(x, y, z) -> 2'
   0' -> 2'
   1' -> 2'
   g(x, x, y) -> y
   g(x, y, y) -> x

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

   encArg(2') -> 2'
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_0) -> 0'
   encArg(cons_1) -> 1'
   encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3))
   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_2 -> 2'
   encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3))

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

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

(22)
Obligation:
Innermost TRS:
Rules:
f(0', 1', x) -> f(x, x, x)
f(x, y, z) -> 2'
0' -> 2'
1' -> 2'
g(x, x, y) -> y
g(x, y, y) -> x
encArg(2') -> 2'
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_0) -> 0'
encArg(cons_1) -> 1'
encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3))
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_2 -> 2'
encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3))

Types:
f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
0' :: 2':cons_f:cons_0:cons_1:cons_g
1' :: 2':cons_f:cons_0:cons_1:cons_g
2' :: 2':cons_f:cons_0:cons_1:cons_g
g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
encArg :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
cons_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
cons_0 :: 2':cons_f:cons_0:cons_1:cons_g
cons_1 :: 2':cons_f:cons_0:cons_1:cons_g
cons_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
encode_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
encode_0 :: 2':cons_f:cons_0:cons_1:cons_g
encode_1 :: 2':cons_f:cons_0:cons_1:cons_g
encode_2 :: 2':cons_f:cons_0:cons_1:cons_g
encode_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
hole_2':cons_f:cons_0:cons_1:cons_g1_4 :: 2':cons_f:cons_0:cons_1:cons_g
gen_2':cons_f:cons_0:cons_1:cons_g2_4 :: Nat -> 2':cons_f:cons_0:cons_1:cons_g

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

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

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

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

(24)
Obligation:
Innermost TRS:
Rules:
f(0', 1', x) -> f(x, x, x)
f(x, y, z) -> 2'
0' -> 2'
1' -> 2'
g(x, x, y) -> y
g(x, y, y) -> x
encArg(2') -> 2'
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_0) -> 0'
encArg(cons_1) -> 1'
encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3))
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_2 -> 2'
encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3))

Types:
f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
0' :: 2':cons_f:cons_0:cons_1:cons_g
1' :: 2':cons_f:cons_0:cons_1:cons_g
2' :: 2':cons_f:cons_0:cons_1:cons_g
g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
encArg :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
cons_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
cons_0 :: 2':cons_f:cons_0:cons_1:cons_g
cons_1 :: 2':cons_f:cons_0:cons_1:cons_g
cons_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
encode_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
encode_0 :: 2':cons_f:cons_0:cons_1:cons_g
encode_1 :: 2':cons_f:cons_0:cons_1:cons_g
encode_2 :: 2':cons_f:cons_0:cons_1:cons_g
encode_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
hole_2':cons_f:cons_0:cons_1:cons_g1_4 :: 2':cons_f:cons_0:cons_1:cons_g
gen_2':cons_f:cons_0:cons_1:cons_g2_4 :: Nat -> 2':cons_f:cons_0:cons_1:cons_g


Generator Equations:
gen_2':cons_f:cons_0:cons_1:cons_g2_4(0) <=> 2'
gen_2':cons_f:cons_0:cons_1:cons_g2_4(+(x, 1)) <=> cons_f(2', 2', gen_2':cons_f:cons_0:cons_1: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

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

(25) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(n14_4)) -> gen_2':cons_f:cons_0:cons_1:cons_g2_4(0), rt in Omega(n14_4)

Induction Base:
encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(0)) ->_R^Omega(0)
2'

Induction Step:
encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(+(n14_4, 1))) ->_R^Omega(0)
f(encArg(2'), encArg(2'), encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(n14_4))) ->_R^Omega(0)
f(2', encArg(2'), encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(n14_4))) ->_R^Omega(0)
f(2', 2', encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(n14_4))) ->_IH
f(2', 2', gen_2':cons_f:cons_0:cons_1:cons_g2_4(0)) ->_R^Omega(1)
2'

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

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

Innermost TRS:
Rules:
f(0', 1', x) -> f(x, x, x)
f(x, y, z) -> 2'
0' -> 2'
1' -> 2'
g(x, x, y) -> y
g(x, y, y) -> x
encArg(2') -> 2'
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_0) -> 0'
encArg(cons_1) -> 1'
encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3))
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_2 -> 2'
encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3))

Types:
f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
0' :: 2':cons_f:cons_0:cons_1:cons_g
1' :: 2':cons_f:cons_0:cons_1:cons_g
2' :: 2':cons_f:cons_0:cons_1:cons_g
g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
encArg :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
cons_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
cons_0 :: 2':cons_f:cons_0:cons_1:cons_g
cons_1 :: 2':cons_f:cons_0:cons_1:cons_g
cons_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
encode_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
encode_0 :: 2':cons_f:cons_0:cons_1:cons_g
encode_1 :: 2':cons_f:cons_0:cons_1:cons_g
encode_2 :: 2':cons_f:cons_0:cons_1:cons_g
encode_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g
hole_2':cons_f:cons_0:cons_1:cons_g1_4 :: 2':cons_f:cons_0:cons_1:cons_g
gen_2':cons_f:cons_0:cons_1:cons_g2_4 :: Nat -> 2':cons_f:cons_0:cons_1:cons_g


Generator Equations:
gen_2':cons_f:cons_0:cons_1:cons_g2_4(0) <=> 2'
gen_2':cons_f:cons_0:cons_1:cons_g2_4(+(x, 1)) <=> cons_f(2', 2', gen_2':cons_f:cons_0:cons_1:cons_g2_4(x))


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

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

(28)
BOUNDS(n^1, INF)