/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


WORST_CASE(Omega(n^1), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Derivational Complexity (full) 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), 191 ms]
(4) CpxRelTRS
(5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxRelTRS
    (7) RelTrsToWeightedTrsProof [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), 17 ms]
    (14) CpxTypedWeightedCompleteTrs
    (15) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (16) CpxRNTS
    (17) SimplificationProof [BOTH BOUNDS(ID, ID), 2 ms]
    (18) CpxRNTS
    (19) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
    (20) CpxRNTS
    (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (22) CpxRNTS
    (23) IntTrsBoundProof [UPPER BOUND(ID), 354 ms]
    (24) CpxRNTS
    (25) IntTrsBoundProof [UPPER BOUND(ID), 148 ms]
    (26) CpxRNTS
    (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (28) CpxRNTS
    (29) IntTrsBoundProof [UPPER BOUND(ID), 8 ms]
    (30) CpxRNTS
    (31) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (32) CpxRNTS
    (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (34) CpxRNTS
    (35) IntTrsBoundProof [UPPER BOUND(ID), 292 ms]
    (36) CpxRNTS
    (37) IntTrsBoundProof [UPPER BOUND(ID), 106 ms]
    (38) CpxRNTS
    (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (40) CpxRNTS
    (41) IntTrsBoundProof [UPPER BOUND(ID), 332 ms]
    (42) CpxRNTS
    (43) IntTrsBoundProof [UPPER BOUND(ID), 275 ms]
    (44) CpxRNTS
    (45) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (46) CpxRNTS
    (47) IntTrsBoundProof [UPPER BOUND(ID), 220 ms]
    (48) CpxRNTS
    (49) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (50) CpxRNTS
    (51) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (52) CpxRNTS
    (53) IntTrsBoundProof [UPPER BOUND(ID), 168 ms]
    (54) CpxRNTS
    (55) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (56) CpxRNTS
    (57) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (58) CpxRNTS
    (59) IntTrsBoundProof [UPPER BOUND(ID), 169 ms]
    (60) CpxRNTS
    (61) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (62) CpxRNTS
    (63) FinalProof [FINISHED, 0 ms]
    (64) BOUNDS(1, n^2)
(65) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(66) CpxRelTRS
    (67) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (68) typed CpxTrs
    (69) OrderProof [LOWER BOUND(ID), 0 ms]
    (70) typed CpxTrs
    (71) RewriteLemmaProof [LOWER BOUND(ID), 291 ms]
    (72) BEST
        (73) proven lower bound
            (74) LowerBoundPropagationProof [FINISHED, 0 ms]
            (75) BOUNDS(n^1, INF)
        (76) typed CpxTrs
            (77) RewriteLemmaProof [LOWER BOUND(ID), 29 ms]
            (78) typed CpxTrs
            (79) RewriteLemmaProof [LOWER BOUND(ID), 0 ms]
            (80) BOUNDS(1, INF)


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

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


The TRS R consists of the following rules:

   f(a, empty) -> g(a, empty)
   f(a, cons(x, k)) -> f(cons(x, a), k)
   g(empty, d) -> d
   g(cons(x, k), d) -> g(k, cons(x, d))

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

(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(empty) -> empty
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_empty -> empty
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))


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

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


The TRS R consists of the following rules:

   f(a, empty) -> g(a, empty)
   f(a, cons(x, k)) -> f(cons(x, a), k)
   g(empty, d) -> d
   g(cons(x, k), d) -> g(k, cons(x, d))

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

   encArg(empty) -> empty
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_empty -> empty
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Rewrite Strategy: FULL
----------------------------------------

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

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


The TRS R consists of the following rules:

   f(a, empty) -> g(a, empty)
   f(a, cons(x, k)) -> f(cons(x, a), k)
   g(empty, d) -> d
   g(cons(x, k), d) -> g(k, cons(x, d))

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

   encArg(empty) -> empty
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_empty -> empty
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Rewrite Strategy: FULL
----------------------------------------

(5) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

As the TRS is a non-duplicating overlay system, we have rc = irc.
----------------------------------------

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


The TRS R consists of the following rules:

   f(a, empty) -> g(a, empty)
   f(a, cons(x, k)) -> f(cons(x, a), k)
   g(empty, d) -> d
   g(cons(x, k), d) -> g(k, cons(x, d))

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

   encArg(empty) -> empty
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_empty -> empty
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

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

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

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


The TRS R consists of the following rules:

   f(a, empty) -> g(a, empty) [1]
   f(a, cons(x, k)) -> f(cons(x, a), k) [1]
   g(empty, d) -> d [1]
   g(cons(x, k), d) -> g(k, cons(x, d)) [1]
   encArg(empty) -> empty [0]
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_empty -> empty [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_cons(x_1, x_2) -> cons(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:

   f(a, empty) -> g(a, empty) [1]
   f(a, cons(x, k)) -> f(cons(x, a), k) [1]
   g(empty, d) -> d [1]
   g(cons(x, k), d) -> g(k, cons(x, d)) [1]
   encArg(empty) -> empty [0]
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_empty -> empty [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0]

The TRS has the following type information:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty: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:

   g_2
   f_2
   encArg_1
   encode_f_2
   encode_empty
   encode_g_2
   encode_cons_2

Due to the following rules being added:

   encArg(v0) -> empty [0]
   encode_f(v0, v1) -> empty [0]
   encode_empty -> empty [0]
   encode_g(v0, v1) -> empty [0]
   encode_cons(v0, v1) -> empty [0]
   g(v0, v1) -> empty [0]
   f(v0, v1) -> empty [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:

   f(a, empty) -> g(a, empty) [1]
   f(a, cons(x, k)) -> f(cons(x, a), k) [1]
   g(empty, d) -> d [1]
   g(cons(x, k), d) -> g(k, cons(x, d)) [1]
   encArg(empty) -> empty [0]
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_empty -> empty [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(v0) -> empty [0]
   encode_f(v0, v1) -> empty [0]
   encode_empty -> empty [0]
   encode_g(v0, v1) -> empty [0]
   encode_cons(v0, v1) -> empty [0]
   g(v0, v1) -> empty [0]
   f(v0, v1) -> empty [0]

The TRS has the following type information:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty: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:

   f(a, empty) -> g(a, empty) [1]
   f(a, cons(x, k)) -> f(cons(x, a), k) [1]
   g(empty, d) -> d [1]
   g(cons(x, k), d) -> g(k, cons(x, d)) [1]
   encArg(empty) -> empty [0]
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0]
   encode_empty -> empty [0]
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0]
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0]
   encArg(v0) -> empty [0]
   encode_f(v0, v1) -> empty [0]
   encode_empty -> empty [0]
   encode_g(v0, v1) -> empty [0]
   encode_cons(v0, v1) -> empty [0]
   g(v0, v1) -> empty [0]
   f(v0, v1) -> empty [0]

The TRS has the following type information:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty: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:

   empty => 0

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encArg(z) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_cons(z, z') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   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
   f(z, z') -{ 1 }-> g(a, 0) :|: z = a, a >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + a, k) :|: z = a, a >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   g(z, z') -{ 1 }-> d :|: z' = d, d >= 0, z = 0
   g(z, z') -{ 1 }-> g(k, 1 + x + d) :|: z' = d, x >= 0, d >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1


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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 1 }-> g(z, 0) :|: z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 1 }-> g(k, 1 + x + z') :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0


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

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

   { g }
   { encode_empty }
   { f }
   { encArg }
   { encode_cons }
   { encode_f }
   { encode_g }

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 1 }-> g(z, 0) :|: z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 1 }-> g(k, 1 + x + z') :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

Function symbols to be analyzed: {g}, {encode_empty}, {f}, {encArg}, {encode_cons}, {encode_f}, {encode_g}

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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 1 }-> g(z, 0) :|: z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 1 }-> g(k, 1 + x + z') :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

Function symbols to be analyzed: {g}, {encode_empty}, {f}, {encArg}, {encode_cons}, {encode_f}, {encode_g}

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

(23) 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'

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 1 }-> g(z, 0) :|: z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 1 }-> g(k, 1 + x + z') :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(25) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 1 }-> g(z, 0) :|: z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 1 }-> g(k, 1 + x + z') :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(29) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(31) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(35) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(37) 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 + 2*z'

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 1 }-> f(1 + x + z, k) :|: z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(41) 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

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(43) 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: 2*z^2

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

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

   encArg(z) -{ 0 }-> g(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2)) :|: 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) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 0 }-> f(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 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
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

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

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

   encArg(z) -{ 2 + s3 + 2*s4 + 2*x_1^2 + 2*x_2^2 }-> s5 :|: s3 >= 0, s3 <= x_1, s4 >= 0, s4 <= x_2, s5 >= 0, s5 <= s3 + s4, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s6 + 2*x_1^2 + 2*x_2^2 }-> s8 :|: s6 >= 0, s6 <= x_1, s7 >= 0, s7 <= x_2, s8 >= 0, s8 <= s6 + s7, 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) -{ 2*x_1^2 + 2*x_2^2 }-> 1 + s1 + s2 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 2*z^2 + 2*z'^2 }-> 1 + s15 + s16 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 2 + 2*s10 + s9 + 2*z^2 + 2*z'^2 }-> s11 :|: s9 >= 0, s9 <= z, s10 >= 0, s10 <= z', s11 >= 0, s11 <= s9 + s10, z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 1 + s12 + 2*z^2 + 2*z'^2 }-> s14 :|: s12 >= 0, s12 <= z, s13 >= 0, s13 <= z', s14 >= 0, s14 <= s12 + s13, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(47) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 2 + s3 + 2*s4 + 2*x_1^2 + 2*x_2^2 }-> s5 :|: s3 >= 0, s3 <= x_1, s4 >= 0, s4 <= x_2, s5 >= 0, s5 <= s3 + s4, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s6 + 2*x_1^2 + 2*x_2^2 }-> s8 :|: s6 >= 0, s6 <= x_1, s7 >= 0, s7 <= x_2, s8 >= 0, s8 <= s6 + s7, 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) -{ 2*x_1^2 + 2*x_2^2 }-> 1 + s1 + s2 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 2*z^2 + 2*z'^2 }-> 1 + s15 + s16 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 2 + 2*s10 + s9 + 2*z^2 + 2*z'^2 }-> s11 :|: s9 >= 0, s9 <= z, s10 >= 0, s10 <= z', s11 >= 0, s11 <= s9 + s10, z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 1 + s12 + 2*z^2 + 2*z'^2 }-> s14 :|: s12 >= 0, s12 <= z, s13 >= 0, s13 <= z', s14 >= 0, s14 <= s12 + s13, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(49) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 2 + s3 + 2*s4 + 2*x_1^2 + 2*x_2^2 }-> s5 :|: s3 >= 0, s3 <= x_1, s4 >= 0, s4 <= x_2, s5 >= 0, s5 <= s3 + s4, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s6 + 2*x_1^2 + 2*x_2^2 }-> s8 :|: s6 >= 0, s6 <= x_1, s7 >= 0, s7 <= x_2, s8 >= 0, s8 <= s6 + s7, 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) -{ 2*x_1^2 + 2*x_2^2 }-> 1 + s1 + s2 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 2*z^2 + 2*z'^2 }-> 1 + s15 + s16 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 2 + 2*s10 + s9 + 2*z^2 + 2*z'^2 }-> s11 :|: s9 >= 0, s9 <= z, s10 >= 0, s10 <= z', s11 >= 0, s11 <= s9 + s10, z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 1 + s12 + 2*z^2 + 2*z'^2 }-> s14 :|: s12 >= 0, s12 <= z, s13 >= 0, s13 <= z', s14 >= 0, s14 <= s12 + s13, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

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

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

   encArg(z) -{ 2 + s3 + 2*s4 + 2*x_1^2 + 2*x_2^2 }-> s5 :|: s3 >= 0, s3 <= x_1, s4 >= 0, s4 <= x_2, s5 >= 0, s5 <= s3 + s4, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s6 + 2*x_1^2 + 2*x_2^2 }-> s8 :|: s6 >= 0, s6 <= x_1, s7 >= 0, s7 <= x_2, s8 >= 0, s8 <= s6 + s7, 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) -{ 2*x_1^2 + 2*x_2^2 }-> 1 + s1 + s2 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 2*z^2 + 2*z'^2 }-> 1 + s15 + s16 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 2 + 2*s10 + s9 + 2*z^2 + 2*z'^2 }-> s11 :|: s9 >= 0, s9 <= z, s10 >= 0, s10 <= z', s11 >= 0, s11 <= s9 + s10, z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 1 + s12 + 2*z^2 + 2*z'^2 }-> s14 :|: s12 >= 0, s12 <= z, s13 >= 0, s13 <= z', s14 >= 0, s14 <= s12 + s13, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(53) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 2 + s3 + 2*s4 + 2*x_1^2 + 2*x_2^2 }-> s5 :|: s3 >= 0, s3 <= x_1, s4 >= 0, s4 <= x_2, s5 >= 0, s5 <= s3 + s4, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s6 + 2*x_1^2 + 2*x_2^2 }-> s8 :|: s6 >= 0, s6 <= x_1, s7 >= 0, s7 <= x_2, s8 >= 0, s8 <= s6 + s7, 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) -{ 2*x_1^2 + 2*x_2^2 }-> 1 + s1 + s2 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 2*z^2 + 2*z'^2 }-> 1 + s15 + s16 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 2 + 2*s10 + s9 + 2*z^2 + 2*z'^2 }-> s11 :|: s9 >= 0, s9 <= z, s10 >= 0, s10 <= z', s11 >= 0, s11 <= s9 + s10, z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 1 + s12 + 2*z^2 + 2*z'^2 }-> s14 :|: s12 >= 0, s12 <= z, s13 >= 0, s13 <= z', s14 >= 0, s14 <= s12 + s13, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(55) 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 + 2*z^2 + 2*z' + 2*z'^2

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

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

   encArg(z) -{ 2 + s3 + 2*s4 + 2*x_1^2 + 2*x_2^2 }-> s5 :|: s3 >= 0, s3 <= x_1, s4 >= 0, s4 <= x_2, s5 >= 0, s5 <= s3 + s4, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s6 + 2*x_1^2 + 2*x_2^2 }-> s8 :|: s6 >= 0, s6 <= x_1, s7 >= 0, s7 <= x_2, s8 >= 0, s8 <= s6 + s7, 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) -{ 2*x_1^2 + 2*x_2^2 }-> 1 + s1 + s2 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 2*z^2 + 2*z'^2 }-> 1 + s15 + s16 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 2 + 2*s10 + s9 + 2*z^2 + 2*z'^2 }-> s11 :|: s9 >= 0, s9 <= z, s10 >= 0, s10 <= z', s11 >= 0, s11 <= s9 + s10, z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 1 + s12 + 2*z^2 + 2*z'^2 }-> s14 :|: s12 >= 0, s12 <= z, s13 >= 0, s13 <= z', s14 >= 0, s14 <= s12 + s13, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

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

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

   encArg(z) -{ 2 + s3 + 2*s4 + 2*x_1^2 + 2*x_2^2 }-> s5 :|: s3 >= 0, s3 <= x_1, s4 >= 0, s4 <= x_2, s5 >= 0, s5 <= s3 + s4, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s6 + 2*x_1^2 + 2*x_2^2 }-> s8 :|: s6 >= 0, s6 <= x_1, s7 >= 0, s7 <= x_2, s8 >= 0, s8 <= s6 + s7, 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) -{ 2*x_1^2 + 2*x_2^2 }-> 1 + s1 + s2 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 2*z^2 + 2*z'^2 }-> 1 + s15 + s16 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 2 + 2*s10 + s9 + 2*z^2 + 2*z'^2 }-> s11 :|: s9 >= 0, s9 <= z, s10 >= 0, s10 <= z', s11 >= 0, s11 <= s9 + s10, z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 1 + s12 + 2*z^2 + 2*z'^2 }-> s14 :|: s12 >= 0, s12 <= z, s13 >= 0, s13 <= z', s14 >= 0, s14 <= s12 + s13, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(59) 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'

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

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

   encArg(z) -{ 2 + s3 + 2*s4 + 2*x_1^2 + 2*x_2^2 }-> s5 :|: s3 >= 0, s3 <= x_1, s4 >= 0, s4 <= x_2, s5 >= 0, s5 <= s3 + s4, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s6 + 2*x_1^2 + 2*x_2^2 }-> s8 :|: s6 >= 0, s6 <= x_1, s7 >= 0, s7 <= x_2, s8 >= 0, s8 <= s6 + s7, 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) -{ 2*x_1^2 + 2*x_2^2 }-> 1 + s1 + s2 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 2*z^2 + 2*z'^2 }-> 1 + s15 + s16 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 2 + 2*s10 + s9 + 2*z^2 + 2*z'^2 }-> s11 :|: s9 >= 0, s9 <= z, s10 >= 0, s10 <= z', s11 >= 0, s11 <= s9 + s10, z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 1 + s12 + 2*z^2 + 2*z'^2 }-> s14 :|: s12 >= 0, s12 <= z, s13 >= 0, s13 <= z', s14 >= 0, s14 <= s12 + s13, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

(61) 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 + 2*z^2 + 2*z'^2

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

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

   encArg(z) -{ 2 + s3 + 2*s4 + 2*x_1^2 + 2*x_2^2 }-> s5 :|: s3 >= 0, s3 <= x_1, s4 >= 0, s4 <= x_2, s5 >= 0, s5 <= s3 + s4, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 1 + s6 + 2*x_1^2 + 2*x_2^2 }-> s8 :|: s6 >= 0, s6 <= x_1, s7 >= 0, s7 <= x_2, s8 >= 0, s8 <= s6 + s7, 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) -{ 2*x_1^2 + 2*x_2^2 }-> 1 + s1 + s2 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_cons(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_cons(z, z') -{ 2*z^2 + 2*z'^2 }-> 1 + s15 + s16 :|: s15 >= 0, s15 <= z, s16 >= 0, s16 <= z', z >= 0, z' >= 0
   encode_empty -{ 0 }-> 0 :|: 
   encode_f(z, z') -{ 2 + 2*s10 + s9 + 2*z^2 + 2*z'^2 }-> s11 :|: s9 >= 0, s9 <= z, s10 >= 0, s10 <= z', s11 >= 0, s11 <= s9 + s10, z >= 0, z' >= 0
   encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_g(z, z') -{ 1 + s12 + 2*z^2 + 2*z'^2 }-> s14 :|: s12 >= 0, s12 <= z, s13 >= 0, s13 <= z', s14 >= 0, s14 <= s12 + s13, z >= 0, z' >= 0
   encode_g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   f(z, z') -{ 2 + z }-> s :|: s >= 0, s <= z + 0, z >= 0, z' = 0
   f(z, z') -{ 4 + 2*k + x + z }-> s'' :|: s'' >= 0, s'' <= 1 + x + z + k, z >= 0, x >= 0, z' = 1 + x + k, k >= 0
   f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   g(z, z') -{ 2 + k }-> s' :|: s' >= 0, s' <= k + (1 + x + z'), x >= 0, z' >= 0, k >= 0, z = 1 + x + k
   g(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   g(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0

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

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

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

(64)
BOUNDS(1, n^2)

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

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

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


The TRS R consists of the following rules:

   f(a, empty) -> g(a, empty)
   f(a, cons(x, k)) -> f(cons(x, a), k)
   g(empty, d) -> d
   g(cons(x, k), d) -> g(k, cons(x, d))

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

   encArg(empty) -> empty
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
   encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
   encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
   encode_empty -> empty
   encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Rewrite Strategy: FULL
----------------------------------------

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

(68)
Obligation:
TRS:
Rules:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
encode_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g

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

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

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

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

(70)
Obligation:
TRS:
Rules:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
encode_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g


Generator Equations:
gen_empty:cons:cons_f:cons_g2_0(0) <=> empty
gen_empty:cons:cons_f:cons_g2_0(+(x, 1)) <=> cons(empty, gen_empty:cons:cons_f:cons_g2_0(x))


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

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

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

(71) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
g(gen_empty:cons:cons_f:cons_g2_0(n4_0), gen_empty:cons:cons_f:cons_g2_0(b)) -> gen_empty:cons:cons_f:cons_g2_0(+(n4_0, b)), rt in Omega(1 + n4_0)

Induction Base:
g(gen_empty:cons:cons_f:cons_g2_0(0), gen_empty:cons:cons_f:cons_g2_0(b)) ->_R^Omega(1)
gen_empty:cons:cons_f:cons_g2_0(b)

Induction Step:
g(gen_empty:cons:cons_f:cons_g2_0(+(n4_0, 1)), gen_empty:cons:cons_f:cons_g2_0(b)) ->_R^Omega(1)
g(gen_empty:cons:cons_f:cons_g2_0(n4_0), cons(empty, gen_empty:cons:cons_f:cons_g2_0(b))) ->_IH
gen_empty:cons:cons_f:cons_g2_0(+(+(b, 1), c5_0))

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

(72)
Complex Obligation (BEST)

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

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

TRS:
Rules:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
encode_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g


Generator Equations:
gen_empty:cons:cons_f:cons_g2_0(0) <=> empty
gen_empty:cons:cons_f:cons_g2_0(+(x, 1)) <=> cons(empty, gen_empty:cons:cons_f:cons_g2_0(x))


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

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

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

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

(75)
BOUNDS(n^1, INF)

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

(76)
Obligation:
TRS:
Rules:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
encode_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g


Lemmas:
g(gen_empty:cons:cons_f:cons_g2_0(n4_0), gen_empty:cons:cons_f:cons_g2_0(b)) -> gen_empty:cons:cons_f:cons_g2_0(+(n4_0, b)), rt in Omega(1 + n4_0)


Generator Equations:
gen_empty:cons:cons_f:cons_g2_0(0) <=> empty
gen_empty:cons:cons_f:cons_g2_0(+(x, 1)) <=> cons(empty, gen_empty:cons:cons_f:cons_g2_0(x))


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

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

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

(77) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
f(gen_empty:cons:cons_f:cons_g2_0(a), gen_empty:cons:cons_f:cons_g2_0(n577_0)) -> gen_empty:cons:cons_f:cons_g2_0(+(n577_0, a)), rt in Omega(1 + a + n577_0)

Induction Base:
f(gen_empty:cons:cons_f:cons_g2_0(a), gen_empty:cons:cons_f:cons_g2_0(0)) ->_R^Omega(1)
g(gen_empty:cons:cons_f:cons_g2_0(a), empty) ->_L^Omega(1 + a)
gen_empty:cons:cons_f:cons_g2_0(+(a, 0))

Induction Step:
f(gen_empty:cons:cons_f:cons_g2_0(a), gen_empty:cons:cons_f:cons_g2_0(+(n577_0, 1))) ->_R^Omega(1)
f(cons(empty, gen_empty:cons:cons_f:cons_g2_0(a)), gen_empty:cons:cons_f:cons_g2_0(n577_0)) ->_IH
gen_empty:cons:cons_f:cons_g2_0(+(+(a, 1), c578_0))

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

(78)
Obligation:
TRS:
Rules:
f(a, empty) -> g(a, empty)
f(a, cons(x, k)) -> f(cons(x, a), k)
g(empty, d) -> d
g(cons(x, k), d) -> g(k, cons(x, d))
encArg(empty) -> empty
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2))
encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2))
encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2))
encode_empty -> empty
encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))

Types:
f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
empty :: empty:cons:cons_f:cons_g
g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encArg :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
cons_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_f :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_empty :: empty:cons:cons_f:cons_g
encode_g :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
encode_cons :: empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g -> empty:cons:cons_f:cons_g
hole_empty:cons:cons_f:cons_g1_0 :: empty:cons:cons_f:cons_g
gen_empty:cons:cons_f:cons_g2_0 :: Nat -> empty:cons:cons_f:cons_g


Lemmas:
g(gen_empty:cons:cons_f:cons_g2_0(n4_0), gen_empty:cons:cons_f:cons_g2_0(b)) -> gen_empty:cons:cons_f:cons_g2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
f(gen_empty:cons:cons_f:cons_g2_0(a), gen_empty:cons:cons_f:cons_g2_0(n577_0)) -> gen_empty:cons:cons_f:cons_g2_0(+(n577_0, a)), rt in Omega(1 + a + n577_0)


Generator Equations:
gen_empty:cons:cons_f:cons_g2_0(0) <=> empty
gen_empty:cons:cons_f:cons_g2_0(+(x, 1)) <=> cons(empty, gen_empty:cons:cons_f:cons_g2_0(x))


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

(79) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_empty:cons:cons_f:cons_g2_0(n1175_0)) -> gen_empty:cons:cons_f:cons_g2_0(n1175_0), rt in Omega(0)

Induction Base:
encArg(gen_empty:cons:cons_f:cons_g2_0(0)) ->_R^Omega(0)
empty

Induction Step:
encArg(gen_empty:cons:cons_f:cons_g2_0(+(n1175_0, 1))) ->_R^Omega(0)
cons(encArg(empty), encArg(gen_empty:cons:cons_f:cons_g2_0(n1175_0))) ->_R^Omega(0)
cons(empty, encArg(gen_empty:cons:cons_f:cons_g2_0(n1175_0))) ->_IH
cons(empty, gen_empty:cons:cons_f:cons_g2_0(c1176_0))

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

(80)
BOUNDS(1, INF)