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

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 177 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) NarrowingProof [BOTH BOUNDS(ID, ID), 272 ms]
    (14) CpxTypedWeightedCompleteTrs
    (15) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (16) CpxRNTS
    (17) InliningProof [UPPER BOUND(ID), 0 ms]
    (18) CpxRNTS
    (19) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
    (20) CpxRNTS
    (21) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
    (22) CpxRNTS
    (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (24) CpxRNTS
    (25) IntTrsBoundProof [UPPER BOUND(ID), 34 ms]
    (26) CpxRNTS
    (27) IntTrsBoundProof [UPPER BOUND(ID), 3 ms]
    (28) CpxRNTS
    (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (30) CpxRNTS
    (31) IntTrsBoundProof [UPPER BOUND(ID), 48 ms]
    (32) CpxRNTS
    (33) IntTrsBoundProof [UPPER BOUND(ID), 4 ms]
    (34) CpxRNTS
    (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (36) CpxRNTS
    (37) IntTrsBoundProof [UPPER BOUND(ID), 300 ms]
    (38) CpxRNTS
    (39) IntTrsBoundProof [UPPER BOUND(ID), 63 ms]
    (40) CpxRNTS
    (41) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (42) CpxRNTS
    (43) IntTrsBoundProof [UPPER BOUND(ID), 261 ms]
    (44) CpxRNTS
    (45) IntTrsBoundProof [UPPER BOUND(ID), 75 ms]
    (46) CpxRNTS
    (47) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (48) CpxRNTS
    (49) IntTrsBoundProof [UPPER BOUND(ID), 392 ms]
    (50) CpxRNTS
    (51) IntTrsBoundProof [UPPER BOUND(ID), 347 ms]
    (52) CpxRNTS
    (53) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (54) CpxRNTS
    (55) IntTrsBoundProof [UPPER BOUND(ID), 97 ms]
    (56) CpxRNTS
    (57) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (58) CpxRNTS
    (59) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (60) CpxRNTS
    (61) IntTrsBoundProof [UPPER BOUND(ID), 178 ms]
    (62) CpxRNTS
    (63) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (64) CpxRNTS
    (65) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (66) CpxRNTS
    (67) IntTrsBoundProof [UPPER BOUND(ID), 187 ms]
    (68) CpxRNTS
    (69) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (70) CpxRNTS
    (71) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (72) CpxRNTS
    (73) IntTrsBoundProof [UPPER BOUND(ID), 178 ms]
    (74) CpxRNTS
    (75) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (76) CpxRNTS
    (77) FinalProof [FINISHED, 0 ms]
    (78) BOUNDS(1, n^2)
(79) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(80) CpxRelTRS
    (81) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (82) typed CpxTrs
    (83) OrderProof [LOWER BOUND(ID), 0 ms]
    (84) typed CpxTrs
    (85) RewriteLemmaProof [LOWER BOUND(ID), 278 ms]
    (86) BEST
        (87) proven lower bound
            (88) LowerBoundPropagationProof [FINISHED, 0 ms]
            (89) BOUNDS(n^1, INF)
        (90) typed CpxTrs
            (91) RewriteLemmaProof [LOWER BOUND(ID), 74 ms]
            (92) BOUNDS(1, INF)


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

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


The TRS R consists of the following rules:

   +(X, 0) -> X
   +(X, s(Y)) -> s(+(X, Y))
   f(0, s(0), X) -> f(X, +(X, X), X)
   g(X, Y) -> X
   g(X, Y) -> 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(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))


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

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

   +(X, 0) -> X
   +(X, s(Y)) -> s(+(X, Y))
   f(0, s(0), X) -> f(X, +(X, X), X)
   g(X, Y) -> X
   g(X, Y) -> Y

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

   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))

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:

   +(X, 0) -> X
   +(X, s(Y)) -> s(+(X, Y))
   f(0, s(0), X) -> f(X, +(X, X), X)
   g(X, Y) -> X
   g(X, Y) -> Y

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

   encArg(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_s(x_1) -> s(encArg(x_1))
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))

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:

   +(X, 0) -> X [1]
   +(X, s(Y)) -> s(+(X, Y)) [1]
   f(0, s(0), X) -> f(X, +(X, X), X) [1]
   g(X, Y) -> X [1]
   g(X, Y) -> Y [1]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> +(encArg(x_1), encArg(x_2)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]

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:

   plus(X, 0) -> X [1]
   plus(X, s(Y)) -> s(plus(X, Y)) [1]
   f(0, s(0), X) -> f(X, plus(X, X), X) [1]
   g(X, Y) -> X [1]
   g(X, Y) -> Y [1]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]

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:

   plus(X, 0) -> X [1]
   plus(X, s(Y)) -> s(plus(X, Y)) [1]
   f(0, s(0), X) -> f(X, plus(X, X), X) [1]
   g(X, Y) -> X [1]
   g(X, Y) -> Y [1]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]

The TRS has the following type information:
plus :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
0 :: 0:s:cons_+:cons_f:cons_g
s :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
f :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
g :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encArg :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
cons_+ :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
cons_f :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
cons_g :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_+ :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_0 :: 0:s:cons_+:cons_f:cons_g
encode_s :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_f :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_g :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g

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

(11) CompletionProof (UPPER BOUND(ID))
The transformation into a RNTS is sound, since:

(a) The obligation is a constructor system where every type has a constant constructor,

(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
none

(c) The following functions are completely defined:

   plus_2
   f_3
   g_2
   encArg_1
   encode_+_2
   encode_0
   encode_s_1
   encode_f_3
   encode_g_2

Due to the following rules being added:

   encArg(v0) -> 0 [0]
   encode_+(v0, v1) -> 0 [0]
   encode_0 -> 0 [0]
   encode_s(v0) -> 0 [0]
   encode_f(v0, v1, v2) -> 0 [0]
   encode_g(v0, v1) -> 0 [0]
   plus(v0, v1) -> 0 [0]
   f(v0, v1, v2) -> 0 [0]

And the following fresh constants: none

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

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

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

   plus(X, 0) -> X [1]
   plus(X, s(Y)) -> s(plus(X, Y)) [1]
   f(0, s(0), X) -> f(X, plus(X, X), X) [1]
   g(X, Y) -> X [1]
   g(X, Y) -> Y [1]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encArg(v0) -> 0 [0]
   encode_+(v0, v1) -> 0 [0]
   encode_0 -> 0 [0]
   encode_s(v0) -> 0 [0]
   encode_f(v0, v1, v2) -> 0 [0]
   encode_g(v0, v1) -> 0 [0]
   plus(v0, v1) -> 0 [0]
   f(v0, v1, v2) -> 0 [0]

The TRS has the following type information:
plus :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
0 :: 0:s:cons_+:cons_f:cons_g
s :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
f :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
g :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encArg :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
cons_+ :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
cons_f :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
cons_g :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_+ :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_0 :: 0:s:cons_+:cons_f:cons_g
encode_s :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_f :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_g :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g

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

(13) NarrowingProof (BOTH BOUNDS(ID, ID))
Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
----------------------------------------

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

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

   plus(X, 0) -> X [1]
   plus(X, s(Y)) -> s(plus(X, Y)) [1]
   f(0, s(0), 0) -> f(0, 0, 0) [2]
   f(0, s(0), s(Y')) -> f(s(Y'), s(plus(s(Y'), Y')), s(Y')) [2]
   f(0, s(0), X) -> f(X, 0, X) [1]
   g(X, Y) -> X [1]
   g(X, Y) -> Y [1]
   encArg(0) -> 0 [0]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(cons_+(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_+(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) [0]
   encode_0 -> 0 [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encArg(v0) -> 0 [0]
   encode_+(v0, v1) -> 0 [0]
   encode_0 -> 0 [0]
   encode_s(v0) -> 0 [0]
   encode_f(v0, v1, v2) -> 0 [0]
   encode_g(v0, v1) -> 0 [0]
   plus(v0, v1) -> 0 [0]
   f(v0, v1, v2) -> 0 [0]

The TRS has the following type information:
plus :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
0 :: 0:s:cons_+:cons_f:cons_g
s :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
f :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
g :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encArg :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
cons_+ :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
cons_f :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
cons_g :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_+ :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_0 :: 0:s:cons_+:cons_f:cons_g
encode_s :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_f :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g
encode_g :: 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_g -> 0:s:cons_+:cons_f:cons_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:

   0 => 0

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

(16)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 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_f(z, z', z'') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, x_3 >= 0, x_2 >= 0, z = x_1, z' = x_2, z'' = x_3
   encode_f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_g(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1
   f(z, z', z'') -{ 1 }-> f(X, 0, X) :|: z'' = X, X >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + Y', 1 + plus(1 + Y', Y'), 1 + Y') :|: z'' = 1 + Y', Y' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   g(z, z') -{ 1 }-> X :|: z' = Y, Y >= 0, X >= 0, z = X
   g(z, z') -{ 1 }-> Y :|: z' = Y, Y >= 0, X >= 0, z = X
   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) :|: Y >= 0, z' = 1 + Y, X >= 0, z = X


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

(17) InliningProof (UPPER BOUND(ID))
Inlined the following terminating rules on right-hand sides where appropriate:

   g(z, z') -{ 1 }-> Y :|: z' = Y, Y >= 0, X >= 0, z = X
   g(z, z') -{ 1 }-> X :|: z' = Y, Y >= 0, X >= 0, z = X

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

(18)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 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_f(z, z', z'') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, x_3 >= 0, x_2 >= 0, z = x_1, z' = x_2, z'' = x_3
   encode_f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_g(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1
   f(z, z', z'') -{ 1 }-> f(X, 0, X) :|: z'' = X, X >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + Y', 1 + plus(1 + Y', Y'), 1 + Y') :|: z'' = 1 + Y', Y' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   g(z, z') -{ 1 }-> X :|: z' = Y, Y >= 0, X >= 0, z = X
   g(z, z') -{ 1 }-> Y :|: z' = Y, Y >= 0, X >= 0, z = X
   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) :|: Y >= 0, z' = 1 + Y, X >= 0, z = X


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

(19) SimplificationProof (BOTH BOUNDS(ID, ID))
Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
----------------------------------------

(20)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0


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

(21) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
Found the following analysis order by SCC decomposition:

   { encode_0 }
   { g }
   { plus }
   { f }
   { encArg }
   { encode_g }
   { encode_f }
   { encode_+ }
   { encode_s }

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

(22)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_0}, {g}, {plus}, {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}

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

(23) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(24)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_0}, {g}, {plus}, {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}

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

(25) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: encode_0
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

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

(26)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_0}, {g}, {plus}, {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: ?, size: O(1) [0]

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

(27) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: encode_0
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

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

(28)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {g}, {plus}, {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]

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

(29) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(30)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {g}, {plus}, {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]

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

(31) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: g
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z + z'

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

(32)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {g}, {plus}, {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: ?, size: O(n^1) [z + z']

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

(33) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: g
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 1

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

(34)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {plus}, {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']

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

(35) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(36)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {plus}, {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']

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

(37) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: plus
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z + z'

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

(38)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {plus}, {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: ?, size: O(n^1) [z + z']

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

(39) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: plus
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 1 + z'

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

(40)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(1 + (z'' - 1), 1 + plus(1 + (z'' - 1), z'' - 1), 1 + (z'' - 1)) :|: z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 }-> 1 + plus(z, z' - 1) :|: z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']

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

(41) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(42)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 + z'' }-> f(1 + (z'' - 1), 1 + s', 1 + (z'' - 1)) :|: s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']

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

(43) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: f
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

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

(44)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 + z'' }-> f(1 + (z'' - 1), 1 + s', 1 + (z'' - 1)) :|: s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {f}, {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: ?, size: O(1) [0]

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

(45) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: f
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 2 + z''

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

(46)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 1 }-> f(z'', 0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 }-> f(0, 0, 0) :|: z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 2 + z'' }-> f(1 + (z'' - 1), 1 + s', 1 + (z'' - 1)) :|: s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]

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

(47) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(48)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]

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

(49) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: encArg
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z

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

(50)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encArg}, {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: ?, size: O(n^1) [z]

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

(51) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: encArg
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: z + z^2

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

(52)
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 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_+(z, z') -{ 0 }-> plus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 0 }-> f(encArg(z), encArg(z'), encArg(z'')) :|: z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 0 }-> g(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]

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

(53) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]

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

(55) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: encode_g
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z + z'

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

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_g}, {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: ?, size: O(n^1) [z + z']

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

(57) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: encode_g
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 1 + z + z^2 + z' + z'^2

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

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']

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

(59) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']

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

(61) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: encode_f
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

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

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_f}, {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']
  encode_f: runtime: ?, size: O(1) [0]

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

(63) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: encode_f
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 2 + z + z^2 + z' + z'^2 + 2*z'' + z''^2

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

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']
  encode_f: runtime: O(n^2) [2 + z + z^2 + z' + z'^2 + 2*z'' + z''^2], size: O(1) [0]

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

(65) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']
  encode_f: runtime: O(n^2) [2 + z + z^2 + z' + z'^2 + 2*z'' + z''^2], size: O(1) [0]

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

(67) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: encode_+
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z + z'

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

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_+}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']
  encode_f: runtime: O(n^2) [2 + z + z^2 + z' + z'^2 + 2*z'' + z''^2], size: O(1) [0]
  encode_+: runtime: ?, size: O(n^1) [z + z']

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

(69) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: encode_+
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 1 + z + z^2 + 2*z' + z'^2

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

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']
  encode_f: runtime: O(n^2) [2 + z + z^2 + z' + z'^2 + 2*z'' + z''^2], size: O(1) [0]
  encode_+: runtime: O(n^2) [1 + z + z^2 + 2*z' + z'^2], size: O(n^1) [z + z']

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

(71) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']
  encode_f: runtime: O(n^2) [2 + z + z^2 + z' + z'^2 + 2*z'' + z''^2], size: O(1) [0]
  encode_+: runtime: O(n^2) [1 + z + z^2 + 2*z' + z'^2], size: O(n^1) [z + z']

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

(73) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: encode_s
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 1 + z

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

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']
  encode_f: runtime: O(n^2) [2 + z + z^2 + z' + z'^2 + 2*z'' + z''^2], size: O(1) [0]
  encode_+: runtime: O(n^2) [1 + z + z^2 + 2*z' + z'^2], size: O(n^1) [z + z']
  encode_s: runtime: ?, size: O(n^1) [1 + z]

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

(75) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: encode_s
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: z + z^2

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

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

   encArg(z) -{ 2 + s9 + x_1 + x_1^2 + x_2 + x_2^2 + x_3 + x_3^2 }-> s10 :|: s7 >= 0, s7 <= x_1, s8 >= 0, s8 <= x_2, s9 >= 0, s9 <= x_3, s10 >= 0, s10 <= 0, x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0
   encArg(z) -{ 1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s21 :|: s19 >= 0, s19 <= x_1, s20 >= 0, s20 <= x_2, s21 >= 0, s21 <= s20 + s19, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s5 + x_1 + x_1^2 + x_2 + x_2^2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -1*z + z^2 }-> 1 + s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11 + s12, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_f(z, z', z'') -{ 2 + s17 + z + z^2 + z' + z'^2 + z'' + z''^2 }-> s18 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', s17 >= 0, s17 <= z'', s18 >= 0, s18 <= 0, z >= 0, z'' >= 0, z' >= 0
   encode_f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   encode_g(z, z') -{ 1 + z + z^2 + z' + z'^2 }-> s24 :|: s22 >= 0, s22 <= z, s23 >= 0, s23 <= z', s24 >= 0, s24 <= s23 + s22, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s14 :|: s14 >= 0, s14 <= z, z >= 0
   f(z, z', z'') -{ 4 }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 4 + 2*z'' }-> s1 :|: s1 >= 0, s1 <= 0, s' >= 0, s' <= 1 + (z'' - 1) + (z'' - 1), z'' - 1 >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 3 + z'' }-> s2 :|: s2 >= 0, s2 <= 0, z'' >= 0, z' = 1 + 0, z = 0
   f(z, z', z'') -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0
   g(z, z') -{ 1 }-> z :|: z' >= 0, z >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z >= 0
   plus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   plus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   plus(z, z') -{ 1 + z' }-> 1 + s :|: s >= 0, s <= z + (z' - 1), z' - 1 >= 0, z >= 0

Function symbols to be analyzed: 
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  g: runtime: O(1) [1], size: O(n^1) [z + z']
  plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z + z']
  f: runtime: O(n^1) [2 + z''], size: O(1) [0]
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_g: runtime: O(n^2) [1 + z + z^2 + z' + z'^2], size: O(n^1) [z + z']
  encode_f: runtime: O(n^2) [2 + z + z^2 + z' + z'^2 + 2*z'' + z''^2], size: O(1) [0]
  encode_+: runtime: O(n^2) [1 + z + z^2 + 2*z' + z'^2], size: O(n^1) [z + z']
  encode_s: runtime: O(n^2) [z + z^2], size: O(n^1) [1 + z]

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

(77) FinalProof (FINISHED)
Computed overall runtime complexity
----------------------------------------

(78)
BOUNDS(1, n^2)

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

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

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

   +'(X, 0') -> X
   +'(X, s(Y)) -> s(+'(X, Y))
   f(0', s(0'), X) -> f(X, +'(X, X), X)
   g(X, Y) -> X
   g(X, Y) -> Y

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

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

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

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

(82)
Obligation:
Innermost TRS:
Rules:
+'(X, 0') -> X
+'(X, s(Y)) -> s(+'(X, Y))
f(0', s(0'), X) -> f(X, +'(X, X), X)
g(X, Y) -> X
g(X, Y) -> Y
encArg(0') -> 0'
encArg(s(x_1)) -> s(encArg(x_1))
encArg(cons_+(x_1, x_2)) -> +'(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_+(x_1, x_2) -> +'(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_s(x_1) -> s(encArg(x_1))
encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))

Types:
+' :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
0' :: 0':s:cons_+:cons_f:cons_g
s :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encArg :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_+ :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_+ :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_0 :: 0':s:cons_+:cons_f:cons_g
encode_s :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
hole_0':s:cons_+:cons_f:cons_g1_4 :: 0':s:cons_+:cons_f:cons_g
gen_0':s:cons_+:cons_f:cons_g2_4 :: Nat -> 0':s:cons_+:cons_f:cons_g

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

(83) 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
f < encArg

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

(84)
Obligation:
Innermost TRS:
Rules:
+'(X, 0') -> X
+'(X, s(Y)) -> s(+'(X, Y))
f(0', s(0'), X) -> f(X, +'(X, X), X)
g(X, Y) -> X
g(X, Y) -> Y
encArg(0') -> 0'
encArg(s(x_1)) -> s(encArg(x_1))
encArg(cons_+(x_1, x_2)) -> +'(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_+(x_1, x_2) -> +'(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_s(x_1) -> s(encArg(x_1))
encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))

Types:
+' :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
0' :: 0':s:cons_+:cons_f:cons_g
s :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encArg :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_+ :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_+ :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_0 :: 0':s:cons_+:cons_f:cons_g
encode_s :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
hole_0':s:cons_+:cons_f:cons_g1_4 :: 0':s:cons_+:cons_f:cons_g
gen_0':s:cons_+:cons_f:cons_g2_4 :: Nat -> 0':s:cons_+:cons_f:cons_g


Generator Equations:
gen_0':s:cons_+:cons_f:cons_g2_4(0) <=> 0'
gen_0':s:cons_+:cons_f:cons_g2_4(+(x, 1)) <=> s(gen_0':s:cons_+:cons_f:cons_g2_4(x))


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

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

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

(85) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
+'(gen_0':s:cons_+:cons_f:cons_g2_4(a), gen_0':s:cons_+:cons_f:cons_g2_4(n4_4)) -> gen_0':s:cons_+:cons_f:cons_g2_4(+(n4_4, a)), rt in Omega(1 + n4_4)

Induction Base:
+'(gen_0':s:cons_+:cons_f:cons_g2_4(a), gen_0':s:cons_+:cons_f:cons_g2_4(0)) ->_R^Omega(1)
gen_0':s:cons_+:cons_f:cons_g2_4(a)

Induction Step:
+'(gen_0':s:cons_+:cons_f:cons_g2_4(a), gen_0':s:cons_+:cons_f:cons_g2_4(+(n4_4, 1))) ->_R^Omega(1)
s(+'(gen_0':s:cons_+:cons_f:cons_g2_4(a), gen_0':s:cons_+:cons_f:cons_g2_4(n4_4))) ->_IH
s(gen_0':s:cons_+:cons_f:cons_g2_4(+(a, c5_4)))

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

(86)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
+'(X, 0') -> X
+'(X, s(Y)) -> s(+'(X, Y))
f(0', s(0'), X) -> f(X, +'(X, X), X)
g(X, Y) -> X
g(X, Y) -> Y
encArg(0') -> 0'
encArg(s(x_1)) -> s(encArg(x_1))
encArg(cons_+(x_1, x_2)) -> +'(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_+(x_1, x_2) -> +'(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_s(x_1) -> s(encArg(x_1))
encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))

Types:
+' :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
0' :: 0':s:cons_+:cons_f:cons_g
s :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encArg :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_+ :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_+ :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_0 :: 0':s:cons_+:cons_f:cons_g
encode_s :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
hole_0':s:cons_+:cons_f:cons_g1_4 :: 0':s:cons_+:cons_f:cons_g
gen_0':s:cons_+:cons_f:cons_g2_4 :: Nat -> 0':s:cons_+:cons_f:cons_g


Generator Equations:
gen_0':s:cons_+:cons_f:cons_g2_4(0) <=> 0'
gen_0':s:cons_+:cons_f:cons_g2_4(+(x, 1)) <=> s(gen_0':s:cons_+:cons_f:cons_g2_4(x))


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

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

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

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

(89)
BOUNDS(n^1, INF)

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

(90)
Obligation:
Innermost TRS:
Rules:
+'(X, 0') -> X
+'(X, s(Y)) -> s(+'(X, Y))
f(0', s(0'), X) -> f(X, +'(X, X), X)
g(X, Y) -> X
g(X, Y) -> Y
encArg(0') -> 0'
encArg(s(x_1)) -> s(encArg(x_1))
encArg(cons_+(x_1, x_2)) -> +'(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_+(x_1, x_2) -> +'(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_s(x_1) -> s(encArg(x_1))
encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3))
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))

Types:
+' :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
0' :: 0':s:cons_+:cons_f:cons_g
s :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encArg :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_+ :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
cons_g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_+ :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_0 :: 0':s:cons_+:cons_f:cons_g
encode_s :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_f :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
encode_g :: 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g -> 0':s:cons_+:cons_f:cons_g
hole_0':s:cons_+:cons_f:cons_g1_4 :: 0':s:cons_+:cons_f:cons_g
gen_0':s:cons_+:cons_f:cons_g2_4 :: Nat -> 0':s:cons_+:cons_f:cons_g


Lemmas:
+'(gen_0':s:cons_+:cons_f:cons_g2_4(a), gen_0':s:cons_+:cons_f:cons_g2_4(n4_4)) -> gen_0':s:cons_+:cons_f:cons_g2_4(+(n4_4, a)), rt in Omega(1 + n4_4)


Generator Equations:
gen_0':s:cons_+:cons_f:cons_g2_4(0) <=> 0'
gen_0':s:cons_+:cons_f:cons_g2_4(+(x, 1)) <=> s(gen_0':s:cons_+:cons_f:cons_g2_4(x))


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

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

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

(91) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_0':s:cons_+:cons_f:cons_g2_4(n805_4)) -> gen_0':s:cons_+:cons_f:cons_g2_4(n805_4), rt in Omega(0)

Induction Base:
encArg(gen_0':s:cons_+:cons_f:cons_g2_4(0)) ->_R^Omega(0)
0'

Induction Step:
encArg(gen_0':s:cons_+:cons_f:cons_g2_4(+(n805_4, 1))) ->_R^Omega(0)
s(encArg(gen_0':s:cons_+:cons_f:cons_g2_4(n805_4))) ->_IH
s(gen_0':s:cons_+:cons_f:cons_g2_4(c806_4))

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

(92)
BOUNDS(1, INF)