/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), 186 ms]
(4) CpxRelTRS
(5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxWeightedTrs
    (7) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxWeightedTrs
    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CpxTypedWeightedTrs
    (11) CompletionProof [UPPER BOUND(ID), 0 ms]
    (12) CpxTypedWeightedCompleteTrs
    (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (14) CpxRNTS
    (15) CompleteCoflocoProof [FINISHED, 1146 ms]
    (16) BOUNDS(1, n^2)
(17) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(18) TRS for Loop Detection
    (19) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (20) BEST
        (21) proven lower bound
            (22) LowerBoundPropagationProof [FINISHED, 0 ms]
            (23) BOUNDS(n^1, INF)
        (24) 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:

   not(true) -> false
   not(false) -> true
   odd(0) -> false
   odd(s(x)) -> not(odd(x))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(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(true) -> true
   encArg(false) -> false
   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_not(x_1)) -> not(encArg(x_1))
   encArg(cons_odd(x_1)) -> odd(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encode_not(x_1) -> not(encArg(x_1))
   encode_true -> true
   encode_false -> false
   encode_odd(x_1) -> odd(encArg(x_1))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))


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

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


The TRS R consists of the following rules:

   not(true) -> false
   not(false) -> true
   odd(0) -> false
   odd(s(x)) -> not(odd(x))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(x, y))

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

   encArg(true) -> true
   encArg(false) -> false
   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_not(x_1)) -> not(encArg(x_1))
   encArg(cons_odd(x_1)) -> odd(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encode_not(x_1) -> not(encArg(x_1))
   encode_true -> true
   encode_false -> false
   encode_odd(x_1) -> odd(encArg(x_1))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))

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

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

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


The TRS R consists of the following rules:

   not(true) -> false
   not(false) -> true
   odd(0) -> false
   odd(s(x)) -> not(odd(x))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(x, y))

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

   encArg(true) -> true
   encArg(false) -> false
   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_not(x_1)) -> not(encArg(x_1))
   encArg(cons_odd(x_1)) -> odd(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encode_not(x_1) -> not(encArg(x_1))
   encode_true -> true
   encode_false -> false
   encode_odd(x_1) -> odd(encArg(x_1))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))

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

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

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


The TRS R consists of the following rules:

   not(true) -> false [1]
   not(false) -> true [1]
   odd(0) -> false [1]
   odd(s(x)) -> not(odd(x)) [1]
   +(x, 0) -> x [1]
   +(x, s(y)) -> s(+(x, y)) [1]
   +(s(x), y) -> s(+(x, y)) [1]
   encArg(true) -> true [0]
   encArg(false) -> false [0]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_not(x_1)) -> not(encArg(x_1)) [0]
   encArg(cons_odd(x_1)) -> odd(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) [0]
   encode_not(x_1) -> not(encArg(x_1)) [0]
   encode_true -> true [0]
   encode_false -> false [0]
   encode_odd(x_1) -> odd(encArg(x_1)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2)) [0]

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

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

+ => plus

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

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


The TRS R consists of the following rules:

   not(true) -> false [1]
   not(false) -> true [1]
   odd(0) -> false [1]
   odd(s(x)) -> not(odd(x)) [1]
   plus(x, 0) -> x [1]
   plus(x, s(y)) -> s(plus(x, y)) [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   encArg(true) -> true [0]
   encArg(false) -> false [0]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_not(x_1)) -> not(encArg(x_1)) [0]
   encArg(cons_odd(x_1)) -> odd(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_not(x_1) -> not(encArg(x_1)) [0]
   encode_true -> true [0]
   encode_false -> false [0]
   encode_odd(x_1) -> odd(encArg(x_1)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]

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

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

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

   not(true) -> false [1]
   not(false) -> true [1]
   odd(0) -> false [1]
   odd(s(x)) -> not(odd(x)) [1]
   plus(x, 0) -> x [1]
   plus(x, s(y)) -> s(plus(x, y)) [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   encArg(true) -> true [0]
   encArg(false) -> false [0]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_not(x_1)) -> not(encArg(x_1)) [0]
   encArg(cons_odd(x_1)) -> odd(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_not(x_1) -> not(encArg(x_1)) [0]
   encode_true -> true [0]
   encode_false -> false [0]
   encode_odd(x_1) -> odd(encArg(x_1)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]

The TRS has the following type information:
not :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
true :: true:false:0:s:cons_not:cons_odd:cons_+
false :: true:false:0:s:cons_not:cons_odd:cons_+
odd :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
0 :: true:false:0:s:cons_not:cons_odd:cons_+
s :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
plus :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
encArg :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
cons_not :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
cons_odd :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
cons_+ :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
encode_not :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
encode_true :: true:false:0:s:cons_not:cons_odd:cons_+
encode_false :: true:false:0:s:cons_not:cons_odd:cons_+
encode_odd :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
encode_0 :: true:false:0:s:cons_not:cons_odd:cons_+
encode_s :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+
encode_+ :: true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+ -> true:false:0:s:cons_not:cons_odd:cons_+

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

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

   encArg(v0) -> null_encArg [0]
   encode_not(v0) -> null_encode_not [0]
   encode_true -> null_encode_true [0]
   encode_false -> null_encode_false [0]
   encode_odd(v0) -> null_encode_odd [0]
   encode_0 -> null_encode_0 [0]
   encode_s(v0) -> null_encode_s [0]
   encode_+(v0, v1) -> null_encode_+ [0]
   not(v0) -> null_not [0]
   odd(v0) -> null_odd [0]
   plus(v0, v1) -> null_plus [0]

And the following fresh constants:    null_encArg, null_encode_not, null_encode_true, null_encode_false, null_encode_odd, null_encode_0, null_encode_s, null_encode_+, null_not, null_odd, null_plus

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

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

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

   not(true) -> false [1]
   not(false) -> true [1]
   odd(0) -> false [1]
   odd(s(x)) -> not(odd(x)) [1]
   plus(x, 0) -> x [1]
   plus(x, s(y)) -> s(plus(x, y)) [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   encArg(true) -> true [0]
   encArg(false) -> false [0]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_not(x_1)) -> not(encArg(x_1)) [0]
   encArg(cons_odd(x_1)) -> odd(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_not(x_1) -> not(encArg(x_1)) [0]
   encode_true -> true [0]
   encode_false -> false [0]
   encode_odd(x_1) -> odd(encArg(x_1)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encArg(v0) -> null_encArg [0]
   encode_not(v0) -> null_encode_not [0]
   encode_true -> null_encode_true [0]
   encode_false -> null_encode_false [0]
   encode_odd(v0) -> null_encode_odd [0]
   encode_0 -> null_encode_0 [0]
   encode_s(v0) -> null_encode_s [0]
   encode_+(v0, v1) -> null_encode_+ [0]
   not(v0) -> null_not [0]
   odd(v0) -> null_odd [0]
   plus(v0, v1) -> null_plus [0]

The TRS has the following type information:
not :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
true :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
false :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
odd :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
0 :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
s :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
plus :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
encArg :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
cons_not :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
cons_odd :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
cons_+ :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
encode_not :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
encode_true :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
encode_false :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
encode_odd :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
encode_0 :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
encode_s :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
encode_+ :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus -> true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_encArg :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_encode_not :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_encode_true :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_encode_false :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_encode_odd :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_encode_0 :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_encode_s :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_encode_+ :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_not :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_odd :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus
null_plus :: true:false:0:s:cons_not:cons_odd:cons_+:null_encArg:null_encode_not:null_encode_true:null_encode_false:null_encode_odd:null_encode_0:null_encode_s:null_encode_+:null_not:null_odd:null_plus

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

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

   true => 2
   false => 1
   0 => 0
   null_encArg => 0
   null_encode_not => 0
   null_encode_true => 0
   null_encode_false => 0
   null_encode_odd => 0
   null_encode_0 => 0
   null_encode_s => 0
   null_encode_+ => 0
   null_not => 0
   null_odd => 0
   null_plus => 0

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

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

   encArg(z) -{ 0 }-> plus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> odd(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0
   encArg(z) -{ 0 }-> not(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0
   encArg(z) -{ 0 }-> 2 :|: z = 2
   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_+(z, z') -{ 0 }-> plus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_+(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_0 -{ 0 }-> 0 :|: 
   encode_false -{ 0 }-> 1 :|: 
   encode_false -{ 0 }-> 0 :|: 
   encode_not(z) -{ 0 }-> not(encArg(x_1)) :|: x_1 >= 0, z = x_1
   encode_not(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_odd(z) -{ 0 }-> odd(encArg(x_1)) :|: x_1 >= 0, z = x_1
   encode_odd(z) -{ 0 }-> 0 :|: v0 >= 0, 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
   encode_true -{ 0 }-> 2 :|: 
   encode_true -{ 0 }-> 0 :|: 
   not(z) -{ 1 }-> 2 :|: z = 1
   not(z) -{ 1 }-> 1 :|: z = 2
   not(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   odd(z) -{ 1 }-> not(odd(x)) :|: x >= 0, z = 1 + x
   odd(z) -{ 1 }-> 1 :|: z = 0
   odd(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   plus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = x
   plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V, V2),0,[not(V, Out)],[V >= 0]).
eq(start(V, V2),0,[odd(V, Out)],[V >= 0]).
eq(start(V, V2),0,[plus(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(start(V, V2),0,[encArg(V, Out)],[V >= 0]).
eq(start(V, V2),0,[fun(V, Out)],[V >= 0]).
eq(start(V, V2),0,[fun1(Out)],[]).
eq(start(V, V2),0,[fun2(Out)],[]).
eq(start(V, V2),0,[fun3(V, Out)],[V >= 0]).
eq(start(V, V2),0,[fun4(Out)],[]).
eq(start(V, V2),0,[fun5(V, Out)],[V >= 0]).
eq(start(V, V2),0,[fun6(V, V2, Out)],[V >= 0,V2 >= 0]).
eq(not(V, Out),1,[],[Out = 1,V = 2]).
eq(not(V, Out),1,[],[Out = 2,V = 1]).
eq(odd(V, Out),1,[],[Out = 1,V = 0]).
eq(odd(V, Out),1,[odd(V1, Ret0),not(Ret0, Ret)],[Out = Ret,V1 >= 0,V = 1 + V1]).
eq(plus(V, V2, Out),1,[],[Out = V3,V3 >= 0,V = V3,V2 = 0]).
eq(plus(V, V2, Out),1,[plus(V4, V5, Ret1)],[Out = 1 + Ret1,V2 = 1 + V5,V4 >= 0,V5 >= 0,V = V4]).
eq(plus(V, V2, Out),1,[plus(V6, V7, Ret11)],[Out = 1 + Ret11,V6 >= 0,V7 >= 0,V = 1 + V6,V2 = V7]).
eq(encArg(V, Out),0,[],[Out = 2,V = 2]).
eq(encArg(V, Out),0,[],[Out = 1,V = 1]).
eq(encArg(V, Out),0,[],[Out = 0,V = 0]).
eq(encArg(V, Out),0,[encArg(V8, Ret12)],[Out = 1 + Ret12,V = 1 + V8,V8 >= 0]).
eq(encArg(V, Out),0,[encArg(V9, Ret01),not(Ret01, Ret2)],[Out = Ret2,V = 1 + V9,V9 >= 0]).
eq(encArg(V, Out),0,[encArg(V10, Ret02),odd(Ret02, Ret3)],[Out = Ret3,V = 1 + V10,V10 >= 0]).
eq(encArg(V, Out),0,[encArg(V12, Ret03),encArg(V11, Ret13),plus(Ret03, Ret13, Ret4)],[Out = Ret4,V12 >= 0,V = 1 + V11 + V12,V11 >= 0]).
eq(fun(V, Out),0,[encArg(V13, Ret04),not(Ret04, Ret5)],[Out = Ret5,V13 >= 0,V = V13]).
eq(fun1(Out),0,[],[Out = 2]).
eq(fun2(Out),0,[],[Out = 1]).
eq(fun3(V, Out),0,[encArg(V14, Ret05),odd(Ret05, Ret6)],[Out = Ret6,V14 >= 0,V = V14]).
eq(fun4(Out),0,[],[Out = 0]).
eq(fun5(V, Out),0,[encArg(V15, Ret14)],[Out = 1 + Ret14,V15 >= 0,V = V15]).
eq(fun6(V, V2, Out),0,[encArg(V17, Ret06),encArg(V16, Ret15),plus(Ret06, Ret15, Ret7)],[Out = Ret7,V17 >= 0,V16 >= 0,V = V17,V2 = V16]).
eq(encArg(V, Out),0,[],[Out = 0,V18 >= 0,V = V18]).
eq(fun(V, Out),0,[],[Out = 0,V19 >= 0,V = V19]).
eq(fun1(Out),0,[],[Out = 0]).
eq(fun2(Out),0,[],[Out = 0]).
eq(fun3(V, Out),0,[],[Out = 0,V20 >= 0,V = V20]).
eq(fun5(V, Out),0,[],[Out = 0,V21 >= 0,V = V21]).
eq(fun6(V, V2, Out),0,[],[Out = 0,V22 >= 0,V23 >= 0,V = V22,V2 = V23]).
eq(not(V, Out),0,[],[Out = 0,V24 >= 0,V = V24]).
eq(odd(V, Out),0,[],[Out = 0,V25 >= 0,V = V25]).
eq(plus(V, V2, Out),0,[],[Out = 0,V26 >= 0,V27 >= 0,V = V26,V2 = V27]).
input_output_vars(not(V,Out),[V],[Out]).
input_output_vars(odd(V,Out),[V],[Out]).
input_output_vars(plus(V,V2,Out),[V,V2],[Out]).
input_output_vars(encArg(V,Out),[V],[Out]).
input_output_vars(fun(V,Out),[V],[Out]).
input_output_vars(fun1(Out),[],[Out]).
input_output_vars(fun2(Out),[],[Out]).
input_output_vars(fun3(V,Out),[V],[Out]).
input_output_vars(fun4(Out),[],[Out]).
input_output_vars(fun5(V,Out),[V],[Out]).
input_output_vars(fun6(V,V2,Out),[V,V2],[Out]).


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

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

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

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

### Specialization of cost equations not/2 
* CE 14 is refined into CE [41] 
* CE 12 is refined into CE [42] 
* CE 13 is refined into CE [43] 


### Cost equations --> "Loop" of not/2 
* CEs [41] --> Loop 25 
* CEs [42] --> Loop 26 
* CEs [43] --> Loop 27 

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

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


### Specialization of cost equations odd/2 
* CE 17 is refined into CE [44] 
* CE 15 is refined into CE [45] 
* CE 16 is refined into CE [46,47,48] 


### Cost equations --> "Loop" of odd/2 
* CEs [46] --> Loop 28 
* CEs [47] --> Loop 29 
* CEs [48] --> Loop 30 
* CEs [44] --> Loop 31 
* CEs [45] --> Loop 32 

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

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


### Specialization of cost equations plus/3 
* CE 21 is refined into CE [49] 
* CE 18 is refined into CE [50] 
* CE 19 is refined into CE [51] 
* CE 20 is refined into CE [52] 


### Cost equations --> "Loop" of plus/3 
* CEs [51] --> Loop 33 
* CEs [52] --> Loop 34 
* CEs [49] --> Loop 35 
* CEs [50] --> Loop 36 

### Ranking functions of CR plus(V,V2,Out) 
* RF of phase [33,34]: [V+V2]

#### Partial ranking functions of CR plus(V,V2,Out) 
* Partial RF of phase [33,34]:
  - RF of loop [33:1]:
    V2
  - RF of loop [34:1]:
    V


### Specialization of cost equations encArg/2 
* CE 24 is refined into CE [53] 
* CE 22 is refined into CE [54] 
* CE 23 is refined into CE [55] 
* CE 28 is refined into CE [56,57,58] 
* CE 25 is refined into CE [59] 
* CE 26 is refined into CE [60,61,62] 
* CE 27 is refined into CE [63,64,65] 


### Cost equations --> "Loop" of encArg/2 
* CEs [60] --> Loop 37 
* CEs [61,65] --> Loop 38 
* CEs [59,63] --> Loop 39 
* CEs [62,64] --> Loop 40 
* CEs [58] --> Loop 41 
* CEs [56] --> Loop 42 
* CEs [57] --> Loop 43 
* CEs [53] --> Loop 44 
* CEs [54] --> Loop 45 
* CEs [55] --> Loop 46 

### Ranking functions of CR encArg(V,Out) 
* RF of phase [37,38,39,40,41,42,43]: [V]

#### Partial ranking functions of CR encArg(V,Out) 
* Partial RF of phase [37,38,39,40,41,42,43]:
  - RF of loop [37:1,38:1,39:1,40:1,41:1,41:2,42:1,42:2,43:1,43:2]:
    V


### Specialization of cost equations fun/2 
* CE 29 is refined into CE [66,67,68,69,70,71] 
* CE 30 is refined into CE [72] 


### Cost equations --> "Loop" of fun/2 
* CEs [66] --> Loop 47 
* CEs [67,69] --> Loop 48 
* CEs [68,70,71,72] --> Loop 49 

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

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


### Specialization of cost equations fun1/1 
* CE 31 is refined into CE [73] 
* CE 32 is refined into CE [74] 


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

### Ranking functions of CR fun1(Out) 

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


### Specialization of cost equations fun2/1 
* CE 33 is refined into CE [75] 
* CE 34 is refined into CE [76] 


### Cost equations --> "Loop" of fun2/1 
* CEs [75] --> Loop 52 
* CEs [76] --> Loop 53 

### Ranking functions of CR fun2(Out) 

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


### Specialization of cost equations fun3/2 
* CE 35 is refined into CE [77,78,79,80,81,82,83] 
* CE 36 is refined into CE [84] 


### Cost equations --> "Loop" of fun3/2 
* CEs [77,82] --> Loop 54 
* CEs [79,81] --> Loop 55 
* CEs [78,80,83,84] --> Loop 56 

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

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


### Specialization of cost equations fun5/2 
* CE 37 is refined into CE [85,86,87] 
* CE 38 is refined into CE [88] 


### Cost equations --> "Loop" of fun5/2 
* CEs [87] --> Loop 57 
* CEs [88] --> Loop 58 
* CEs [85,86] --> Loop 59 

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

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


### Specialization of cost equations fun6/3 
* CE 39 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] 
* CE 40 is refined into CE [112] 


### Cost equations --> "Loop" of fun6/3 
* CEs [93] --> Loop 60 
* CEs [107,109] --> Loop 61 
* CEs [92,108] --> Loop 62 
* CEs [89,94,96,97,102,104] --> Loop 63 
* CEs [91,99,101] --> Loop 64 
* CEs [90,95,98,100,103,105,106,110,111,112] --> Loop 65 

### Ranking functions of CR fun6(V,V2,Out) 

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


### Specialization of cost equations start/2 
* CE 1 is refined into CE [113,114,115] 
* CE 2 is refined into CE [116,117,118] 
* CE 3 is refined into CE [119,120,121] 
* CE 4 is refined into CE [122,123,124] 
* CE 5 is refined into CE [125,126,127] 
* CE 6 is refined into CE [128,129] 
* CE 7 is refined into CE [130,131] 
* CE 8 is refined into CE [132,133,134] 
* CE 9 is refined into CE [135] 
* CE 10 is refined into CE [136,137,138] 
* CE 11 is refined into CE [139,140,141,142] 


### Cost equations --> "Loop" of start/2 
* CEs [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] --> Loop 66 

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

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


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

#### Cost of chains of not(V,Out):
* Chain [27]: 1
  with precondition: [V=1,Out=2] 

* Chain [26]: 1
  with precondition: [V=2,Out=1] 

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


#### Cost of chains of odd(V,Out):
* Chain [[30],[28,29],32]: 5*it(28)+1
  Such that:aux(4) =< V
it(28) =< aux(4)

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

* Chain [[30],32]: 1*it(30)+1
  Such that:it(30) =< V

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

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

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

* Chain [[28,29],32]: 4*it(28)+1
  Such that:aux(3) =< V
it(28) =< aux(3)

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

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

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


#### Cost of chains of plus(V,V2,Out):
* Chain [[33,34],36]: 1*it(33)+1*it(34)+1
  Such that:it(34) =< -V2+Out
it(33) =< V2
aux(8) =< Out
it(33) =< aux(8)
it(34) =< aux(8)

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

* Chain [[33,34],35]: 2*it(33)+0
  Such that:aux(6) =< V+V2
aux(9) =< Out
it(33) =< aux(9)
it(33) =< aux(6)

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

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

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


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

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

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

* Chain [multiple([37,38,39,40,41,42,43],[[46],[45],[44]])]: 5*it(37)+1*it(41)+4*s(28)+7*s(30)+2*s(32)+2*s(34)+0
  Such that:aux(25) =< V
aux(26) =< 2/3*V
it(37) =< aux(25)
it(41) =< aux(25)
it(41) =< aux(26)
aux(15) =< aux(25)
aux(13) =< aux(25)+1
s(29) =< it(37)*aux(25)
s(31) =< it(37)*aux(13)
s(32) =< it(41)*aux(15)
s(35) =< it(41)*aux(15)
s(34) =< s(35)
s(32) =< s(35)
s(30) =< s(31)
s(28) =< s(29)

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


#### Cost of chains of fun(V,Out):
* Chain [49]: 5*s(51)+1*s(52)+2*s(57)+2*s(59)+7*s(60)+4*s(61)+0
  Such that:s(49) =< V
s(50) =< 2/3*V
s(51) =< s(49)
s(52) =< s(49)
s(52) =< s(50)
s(53) =< s(49)
s(54) =< s(49)+1
s(55) =< s(51)*s(49)
s(56) =< s(51)*s(54)
s(57) =< s(52)*s(53)
s(58) =< s(52)*s(53)
s(59) =< s(58)
s(57) =< s(58)
s(60) =< s(56)
s(61) =< s(55)

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

* Chain [48]: 5*s(64)+1*s(65)+2*s(70)+2*s(72)+7*s(73)+4*s(74)+1
  Such that:s(62) =< V
s(63) =< 2/3*V
s(64) =< s(62)
s(65) =< s(62)
s(65) =< s(63)
s(66) =< s(62)
s(67) =< s(62)+1
s(68) =< s(64)*s(62)
s(69) =< s(64)*s(67)
s(70) =< s(65)*s(66)
s(71) =< s(65)*s(66)
s(72) =< s(71)
s(70) =< s(71)
s(73) =< s(69)
s(74) =< s(68)

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

* Chain [47]: 5*s(77)+1*s(78)+2*s(83)+2*s(85)+7*s(86)+4*s(87)+1
  Such that:s(75) =< V
s(76) =< 2/3*V
s(77) =< s(75)
s(78) =< s(75)
s(78) =< s(76)
s(79) =< s(75)
s(80) =< s(75)+1
s(81) =< s(77)*s(75)
s(82) =< s(77)*s(80)
s(83) =< s(78)*s(79)
s(84) =< s(78)*s(79)
s(85) =< s(84)
s(83) =< s(84)
s(86) =< s(82)
s(87) =< s(81)

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


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

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


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

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


#### Cost of chains of fun3(V,Out):
* Chain [56]: 12*s(90)+1*s(91)+2*s(96)+2*s(98)+7*s(99)+4*s(100)+7*s(104)+1
  Such that:s(103) =< 2
aux(27) =< V
s(89) =< 2/3*V
s(104) =< s(103)
s(90) =< aux(27)
s(91) =< aux(27)
s(91) =< s(89)
s(92) =< aux(27)
s(93) =< aux(27)+1
s(94) =< s(90)*aux(27)
s(95) =< s(90)*s(93)
s(96) =< s(91)*s(92)
s(97) =< s(91)*s(92)
s(98) =< s(97)
s(96) =< s(97)
s(99) =< s(95)
s(100) =< s(94)

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

* Chain [55]: 9*s(109)+1*s(110)+2*s(115)+2*s(117)+7*s(118)+4*s(119)+4*s(123)+1
  Such that:s(122) =< 2
aux(28) =< V
s(108) =< 2/3*V
s(123) =< s(122)
s(109) =< aux(28)
s(110) =< aux(28)
s(110) =< s(108)
s(111) =< aux(28)
s(112) =< aux(28)+1
s(113) =< s(109)*aux(28)
s(114) =< s(109)*s(112)
s(115) =< s(110)*s(111)
s(116) =< s(110)*s(111)
s(117) =< s(116)
s(115) =< s(116)
s(118) =< s(114)
s(119) =< s(113)

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

* Chain [54]: 5*s(126)+1*s(127)+2*s(132)+2*s(134)+7*s(135)+4*s(136)+1
  Such that:s(124) =< V
s(125) =< 2/3*V
s(126) =< s(124)
s(127) =< s(124)
s(127) =< s(125)
s(128) =< s(124)
s(129) =< s(124)+1
s(130) =< s(126)*s(124)
s(131) =< s(126)*s(129)
s(132) =< s(127)*s(128)
s(133) =< s(127)*s(128)
s(134) =< s(133)
s(132) =< s(133)
s(135) =< s(131)
s(136) =< s(130)

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


#### Cost of chains of fun5(V,Out):
* Chain [59]: 5*s(139)+1*s(140)+2*s(145)+2*s(147)+7*s(148)+4*s(149)+0
  Such that:s(137) =< V
s(138) =< 2/3*V
s(139) =< s(137)
s(140) =< s(137)
s(140) =< s(138)
s(141) =< s(137)
s(142) =< s(137)+1
s(143) =< s(139)*s(137)
s(144) =< s(139)*s(142)
s(145) =< s(140)*s(141)
s(146) =< s(140)*s(141)
s(147) =< s(146)
s(145) =< s(146)
s(148) =< s(144)
s(149) =< s(143)

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

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

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


#### Cost of chains of fun6(V,V2,Out):
* Chain [65]: 10*s(152)+2*s(153)+4*s(158)+4*s(160)+14*s(161)+8*s(162)+20*s(165)+4*s(166)+8*s(171)+8*s(173)+28*s(174)+16*s(175)+1
  Such that:aux(29) =< V
aux(30) =< 2/3*V
aux(31) =< V2
aux(32) =< 2/3*V2
s(165) =< aux(31)
s(166) =< aux(31)
s(166) =< aux(32)
s(167) =< aux(31)
s(168) =< aux(31)+1
s(169) =< s(165)*aux(31)
s(170) =< s(165)*s(168)
s(171) =< s(166)*s(167)
s(172) =< s(166)*s(167)
s(173) =< s(172)
s(171) =< s(172)
s(174) =< s(170)
s(175) =< s(169)
s(152) =< aux(29)
s(153) =< aux(29)
s(153) =< aux(30)
s(154) =< aux(29)
s(155) =< aux(29)+1
s(156) =< s(152)*aux(29)
s(157) =< s(152)*s(155)
s(158) =< s(153)*s(154)
s(159) =< s(153)*s(154)
s(160) =< s(159)
s(158) =< s(159)
s(161) =< s(157)
s(162) =< s(156)

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

* Chain [64]: 5*s(230)+1*s(231)+2*s(236)+2*s(238)+7*s(239)+4*s(240)+10*s(243)+2*s(244)+4*s(249)+4*s(251)+14*s(252)+8*s(253)+1*s(255)+1*s(256)+2*s(258)+1*s(273)+1*s(274)+2*s(276)+2*s(278)+2*s(281)+1
  Such that:aux(39) =< 4
aux(33) =< V
aux(34) =< V+V2
s(229) =< 2/3*V
aux(37) =< V2+2
aux(40) =< 2
aux(41) =< V2
aux(42) =< 2/3*V2
s(273) =< aux(40)
s(278) =< aux(40)
s(281) =< aux(39)
s(278) =< aux(39)
s(274) =< aux(41)
s(276) =< aux(37)
s(274) =< aux(37)
s(273) =< aux(37)
s(243) =< aux(41)
s(244) =< aux(41)
s(244) =< aux(42)
s(245) =< aux(41)
s(246) =< aux(41)+1
s(247) =< s(243)*aux(41)
s(248) =< s(243)*s(246)
s(249) =< s(244)*s(245)
s(250) =< s(244)*s(245)
s(251) =< s(250)
s(249) =< s(250)
s(252) =< s(248)
s(253) =< s(247)
s(255) =< aux(33)
s(256) =< aux(41)
s(258) =< aux(34)
s(256) =< aux(34)
s(255) =< aux(34)
s(230) =< aux(33)
s(231) =< aux(33)
s(231) =< s(229)
s(232) =< aux(33)
s(233) =< aux(33)+1
s(234) =< s(230)*aux(33)
s(235) =< s(230)*s(233)
s(236) =< s(231)*s(232)
s(237) =< s(231)*s(232)
s(238) =< s(237)
s(236) =< s(237)
s(239) =< s(235)
s(240) =< s(234)

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

* Chain [63]: 18*s(284)+3*s(285)+6*s(290)+6*s(292)+21*s(293)+12*s(294)+10*s(297)+2*s(298)+4*s(303)+4*s(305)+14*s(306)+8*s(307)+3*s(353)+1
  Such that:aux(44) =< 2
aux(45) =< V
aux(46) =< 2/3*V
aux(47) =< V2
aux(48) =< 2/3*V2
s(353) =< aux(44)
s(297) =< aux(47)
s(298) =< aux(47)
s(298) =< aux(48)
s(299) =< aux(47)
s(300) =< aux(47)+1
s(301) =< s(297)*aux(47)
s(302) =< s(297)*s(300)
s(303) =< s(298)*s(299)
s(304) =< s(298)*s(299)
s(305) =< s(304)
s(303) =< s(304)
s(306) =< s(302)
s(307) =< s(301)
s(284) =< aux(45)
s(285) =< aux(45)
s(285) =< aux(46)
s(286) =< aux(45)
s(287) =< aux(45)+1
s(288) =< s(284)*aux(45)
s(289) =< s(284)*s(287)
s(290) =< s(285)*s(286)
s(291) =< s(285)*s(286)
s(292) =< s(291)
s(290) =< s(291)
s(293) =< s(289)
s(294) =< s(288)

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

* Chain [62]: 5*s(359)+1*s(360)+2*s(365)+2*s(367)+7*s(368)+4*s(369)+0
  Such that:s(357) =< V
s(358) =< 2/3*V
s(359) =< s(357)
s(360) =< s(357)
s(360) =< s(358)
s(361) =< s(357)
s(362) =< s(357)+1
s(363) =< s(359)*s(357)
s(364) =< s(359)*s(362)
s(365) =< s(360)*s(361)
s(366) =< s(360)*s(361)
s(367) =< s(366)
s(365) =< s(366)
s(368) =< s(364)
s(369) =< s(363)

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

* Chain [61]: 8*s(372)+1*s(373)+2*s(378)+2*s(380)+7*s(381)+4*s(382)+3*s(390)+1
  Such that:aux(50) =< 2
aux(49) =< V2
s(371) =< 2/3*V2
s(390) =< aux(50)
s(372) =< aux(49)
s(373) =< aux(49)
s(373) =< s(371)
s(374) =< aux(49)
s(375) =< aux(49)+1
s(376) =< s(372)*aux(49)
s(377) =< s(372)*s(375)
s(378) =< s(373)*s(374)
s(379) =< s(373)*s(374)
s(380) =< s(379)
s(378) =< s(379)
s(381) =< s(377)
s(382) =< s(376)

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

* Chain [60]: 5*s(395)+1*s(396)+2*s(401)+2*s(403)+7*s(404)+4*s(405)+1*s(407)+1*s(408)+2*s(410)+1
  Such that:s(408) =< 2
s(394) =< 2/3*V
aux(51) =< V
aux(52) =< V+2
s(407) =< aux(51)
s(410) =< aux(52)
s(408) =< aux(52)
s(407) =< aux(52)
s(395) =< aux(51)
s(396) =< aux(51)
s(396) =< s(394)
s(397) =< aux(51)
s(398) =< aux(51)+1
s(399) =< s(395)*aux(51)
s(400) =< s(395)*s(398)
s(401) =< s(396)*s(397)
s(402) =< s(396)*s(397)
s(403) =< s(402)
s(401) =< s(402)
s(404) =< s(400)
s(405) =< s(399)

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


#### Cost of chains of start(V,V2):
* Chain [66]: 105*s(506)+2*s(510)+2*s(511)+4*s(513)+16*s(517)+32*s(522)+32*s(524)+112*s(525)+64*s(526)+17*s(569)+48*s(637)+9*s(638)+18*s(643)+18*s(645)+63*s(646)+36*s(647)+1*s(657)+1*s(658)+2*s(659)+1*s(671)+2*s(672)+2*s(673)+1*s(674)+2*s(675)+1
  Such that:s(648) =< 4
s(649) =< V+2
s(652) =< V2+2
aux(59) =< 2
aux(60) =< V
aux(61) =< V+V2
aux(62) =< 2/3*V
aux(63) =< V2
aux(64) =< 2/3*V2
s(510) =< aux(60)
s(511) =< aux(63)
s(569) =< aux(59)
s(506) =< aux(60)
s(517) =< aux(60)
s(517) =< aux(62)
s(518) =< aux(60)
s(519) =< aux(60)+1
s(520) =< s(506)*aux(60)
s(521) =< s(506)*s(519)
s(522) =< s(517)*s(518)
s(523) =< s(517)*s(518)
s(524) =< s(523)
s(522) =< s(523)
s(525) =< s(521)
s(526) =< s(520)
s(657) =< aux(59)
s(658) =< aux(60)
s(659) =< s(649)
s(657) =< s(649)
s(658) =< s(649)
s(671) =< aux(59)
s(672) =< aux(59)
s(673) =< s(648)
s(672) =< s(648)
s(674) =< aux(63)
s(675) =< s(652)
s(674) =< s(652)
s(671) =< s(652)
s(637) =< aux(63)
s(638) =< aux(63)
s(638) =< aux(64)
s(639) =< aux(63)
s(640) =< aux(63)+1
s(641) =< s(637)*aux(63)
s(642) =< s(637)*s(640)
s(643) =< s(638)*s(639)
s(644) =< s(638)*s(639)
s(645) =< s(644)
s(643) =< s(644)
s(646) =< s(642)
s(647) =< s(641)
s(513) =< aux(61)
s(511) =< aux(61)
s(510) =< aux(61)

  with precondition: [] 


Closed-form bounds of start(V,V2): 
-------------------------------------
* Chain [66] with precondition: [] 
    - Upper bound: nat(V)*236+51+nat(V)*240*nat(V)+nat(V2)*123+nat(V2)*135*nat(V2)+nat(V+V2)*4+nat(V+2)*2+nat(V2+2)*2 
    - Complexity: n^2 

### Maximum cost of start(V,V2): nat(V)*236+51+nat(V)*240*nat(V)+nat(V2)*123+nat(V2)*135*nat(V2)+nat(V+V2)*4+nat(V+2)*2+nat(V2+2)*2 
Asymptotic class: n^2 
* Total analysis performed in 979 ms.


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

(16)
BOUNDS(1, n^2)

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

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

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

   not(true) -> false
   not(false) -> true
   odd(0) -> false
   odd(s(x)) -> not(odd(x))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(x, y))

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

   encArg(true) -> true
   encArg(false) -> false
   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_not(x_1)) -> not(encArg(x_1))
   encArg(cons_odd(x_1)) -> odd(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encode_not(x_1) -> not(encArg(x_1))
   encode_true -> true
   encode_false -> false
   encode_odd(x_1) -> odd(encArg(x_1))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))

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

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

The rewrite sequence

+(x, s(y)) ->^+ s(+(x, y))

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

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

The result substitution is [ ].




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

(20)
Complex Obligation (BEST)

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

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

   not(true) -> false
   not(false) -> true
   odd(0) -> false
   odd(s(x)) -> not(odd(x))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(x, y))

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

   encArg(true) -> true
   encArg(false) -> false
   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_not(x_1)) -> not(encArg(x_1))
   encArg(cons_odd(x_1)) -> odd(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encode_not(x_1) -> not(encArg(x_1))
   encode_true -> true
   encode_false -> false
   encode_odd(x_1) -> odd(encArg(x_1))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))

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

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

(23)
BOUNDS(n^1, INF)

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

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

   not(true) -> false
   not(false) -> true
   odd(0) -> false
   odd(s(x)) -> not(odd(x))
   +(x, 0) -> x
   +(x, s(y)) -> s(+(x, y))
   +(s(x), y) -> s(+(x, y))

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

   encArg(true) -> true
   encArg(false) -> false
   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_not(x_1)) -> not(encArg(x_1))
   encArg(cons_odd(x_1)) -> odd(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encode_not(x_1) -> not(encArg(x_1))
   encode_true -> true
   encode_false -> false
   encode_odd(x_1) -> odd(encArg(x_1))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))

Rewrite Strategy: INNERMOST