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


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


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 (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), 96 ms]
(4) CpxRelTRS
(5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxRelTRS
    (7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxWeightedTrs
    (9) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CpxWeightedTrs
    (11) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) CpxTypedWeightedTrs
    (13) CompletionProof [UPPER BOUND(ID), 0 ms]
    (14) CpxTypedWeightedCompleteTrs
    (15) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (16) CpxTypedWeightedCompleteTrs
    (17) CpxTypedWeightedTrsToRntsProof [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), 374 ms]
    (26) CpxRNTS
    (27) IntTrsBoundProof [UPPER BOUND(ID), 120 ms]
    (28) CpxRNTS
    (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (30) CpxRNTS
    (31) IntTrsBoundProof [UPPER BOUND(ID), 4 ms]
    (32) CpxRNTS
    (33) IntTrsBoundProof [UPPER BOUND(ID), 12 ms]
    (34) CpxRNTS
    (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (36) CpxRNTS
    (37) IntTrsBoundProof [UPPER BOUND(ID), 331 ms]
    (38) CpxRNTS
    (39) IntTrsBoundProof [UPPER BOUND(ID), 96 ms]
    (40) CpxRNTS
    (41) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (42) CpxRNTS
    (43) IntTrsBoundProof [UPPER BOUND(ID), 363 ms]
    (44) CpxRNTS
    (45) IntTrsBoundProof [UPPER BOUND(ID), 166 ms]
    (46) CpxRNTS
    (47) ResultPropagationProof [UPPER BOUND(ID), 1 ms]
    (48) CpxRNTS
    (49) IntTrsBoundProof [UPPER BOUND(ID), 209 ms]
    (50) CpxRNTS
    (51) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (52) CpxRNTS
    (53) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (54) CpxRNTS
    (55) IntTrsBoundProof [UPPER BOUND(ID), 168 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) FinalProof [FINISHED, 0 ms]
    (66) BOUNDS(1, n^2)
(67) RenamingProof [BOTH BOUNDS(ID, ID), 1 ms]
(68) CpxRelTRS
    (69) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (70) typed CpxTrs
    (71) OrderProof [LOWER BOUND(ID), 0 ms]
    (72) typed CpxTrs
    (73) RewriteLemmaProof [LOWER BOUND(ID), 296 ms]
    (74) BEST
        (75) proven lower bound
            (76) LowerBoundPropagationProof [FINISHED, 0 ms]
            (77) BOUNDS(n^1, INF)
        (78) typed CpxTrs
            (79) RewriteLemmaProof [LOWER BOUND(ID), 32 ms]
            (80) typed CpxTrs
            (81) RewriteLemmaProof [LOWER BOUND(ID), 48 ms]
            (82) 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:

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

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(0) -> 0
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(cons_+(x_1, x_2)) -> +(encArg(x_1), encArg(x_2))
   encArg(cons_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(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:

   +(0, y) -> y
   +(s(x), y) -> s(+(x, y))
   -(0, y) -> 0
   -(x, 0) -> x
   -(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(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:

   +(0, y) -> y
   +(s(x), y) -> s(+(x, y))
   -(0, y) -> 0
   -(x, 0) -> x
   -(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(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:

   +(0, y) -> y
   +(s(x), y) -> s(+(x, y))
   -(0, y) -> 0
   -(x, 0) -> x
   -(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(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:

   +(0, y) -> y [1]
   +(s(x), y) -> s(+(x, y)) [1]
   -(0, y) -> 0 [1]
   -(x, 0) -> x [1]
   -(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) [0]

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

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

+ => plus
- => minus

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

(10)
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(0, y) -> y [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   minus(0, y) -> 0 [1]
   minus(x, 0) -> x [1]
   minus(s(x), s(y)) -> minus(x, 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_-(x_1, x_2)) -> minus(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_-(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0]

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

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

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

   plus(0, y) -> y [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   minus(0, y) -> 0 [1]
   minus(x, 0) -> x [1]
   minus(s(x), s(y)) -> minus(x, 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_-(x_1, x_2)) -> minus(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_-(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0]

The TRS has the following type information:
plus :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
0 :: 0:s:cons_+:cons_-
s :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
minus :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encArg :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
cons_+ :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
cons_- :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encode_+ :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encode_0 :: 0:s:cons_+:cons_-
encode_s :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encode_- :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-

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

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

   minus_2
   plus_2
   encArg_1
   encode_+_2
   encode_0
   encode_s_1
   encode_-_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_-(v0, v1) -> 0 [0]
   minus(v0, v1) -> 0 [0]
   plus(v0, v1) -> 0 [0]

And the following fresh constants: none

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

(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(0, y) -> y [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   minus(0, y) -> 0 [1]
   minus(x, 0) -> x [1]
   minus(s(x), s(y)) -> minus(x, 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_-(x_1, x_2)) -> minus(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_-(x_1, x_2) -> minus(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_-(v0, v1) -> 0 [0]
   minus(v0, v1) -> 0 [0]
   plus(v0, v1) -> 0 [0]

The TRS has the following type information:
plus :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
0 :: 0:s:cons_+:cons_-
s :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
minus :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encArg :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
cons_+ :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
cons_- :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encode_+ :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encode_0 :: 0:s:cons_+:cons_-
encode_s :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encode_- :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-

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

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

(16)
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(0, y) -> y [1]
   plus(s(x), y) -> s(plus(x, y)) [1]
   minus(0, y) -> 0 [1]
   minus(x, 0) -> x [1]
   minus(s(x), s(y)) -> minus(x, 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_-(x_1, x_2)) -> minus(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_-(x_1, x_2) -> minus(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_-(v0, v1) -> 0 [0]
   minus(v0, v1) -> 0 [0]
   plus(v0, v1) -> 0 [0]

The TRS has the following type information:
plus :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
0 :: 0:s:cons_+:cons_-
s :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
minus :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encArg :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
cons_+ :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
cons_- :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encode_+ :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encode_0 :: 0:s:cons_+:cons_-
encode_s :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-
encode_- :: 0:s:cons_+:cons_- -> 0:s:cons_+:cons_- -> 0:s:cons_+:cons_-

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

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

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

(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 }-> minus(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) :|: 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_-(z, z') -{ 0 }-> minus(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_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1
   minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0
   minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   minus(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y
   minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   plus(z, z') -{ 1 }-> y :|: y >= 0, z = 0, z' = y
   plus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y


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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0


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

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

   { minus }
   { encode_0 }
   { plus }
   { encArg }
   { encode_- }
   { 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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {minus}, {encode_0}, {plus}, {encArg}, {encode_-}, {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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {minus}, {encode_0}, {plus}, {encArg}, {encode_-}, {encode_+}, {encode_s}

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

(25) IntTrsBoundProof (UPPER BOUND(ID))

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

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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {minus}, {encode_0}, {plus}, {encArg}, {encode_-}, {encode_+}, {encode_s}
Previous analysis results are:
  minus: runtime: ?, size: O(n^1) [z]

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

(27) IntTrsBoundProof (UPPER BOUND(ID))

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

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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

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

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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

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

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

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

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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

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

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

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

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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

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

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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

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

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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {plus}, {encArg}, {encode_-}, {encode_+}, {encode_s}
Previous analysis results are:
  minus: runtime: O(n^1) [2 + z'], size: O(n^1) [z]
  encode_0: runtime: O(1) [0], size: O(1) [0]
  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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {encArg}, {encode_-}, {encode_+}, {encode_s}
Previous analysis results are:
  minus: runtime: O(n^1) [2 + z'], size: O(n^1) [z]
  encode_0: runtime: O(1) [0], size: O(1) [0]
  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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

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

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

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

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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

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

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

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

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

(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 }-> minus(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(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_-(z, z') -{ 0 }-> minus(encArg(z), encArg(z')) :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

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

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

(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) -{ 1 + s1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s3 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, s3 >= 0, s3 <= s1 + s2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 2 + 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, 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 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s7 + z + z^2 + z' + z'^2 }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 2 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11, z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s10 :|: s10 >= 0, s10 <= z, z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

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

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

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

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

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

   encArg(z) -{ 1 + s1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s3 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, s3 >= 0, s3 <= s1 + s2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 2 + 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, 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 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s7 + z + z^2 + z' + z'^2 }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 2 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11, z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s10 :|: s10 >= 0, s10 <= z, z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

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

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

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

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

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

   encArg(z) -{ 1 + s1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s3 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, s3 >= 0, s3 <= s1 + s2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 2 + 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, 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 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s7 + z + z^2 + z' + z'^2 }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 2 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11, z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s10 :|: s10 >= 0, s10 <= z, z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {encode_+}, {encode_s}
Previous analysis results are:
  minus: runtime: O(n^1) [2 + z'], size: O(n^1) [z]
  encode_0: runtime: O(1) [0], size: O(1) [0]
  plus: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_-: runtime: O(n^2) [2 + z + z^2 + 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) -{ 1 + s1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s3 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, s3 >= 0, s3 <= s1 + s2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 2 + 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, 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 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s7 + z + z^2 + z' + z'^2 }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 2 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11, z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s10 :|: s10 >= 0, s10 <= z, z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

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

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

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

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

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

   encArg(z) -{ 1 + s1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s3 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, s3 >= 0, s3 <= s1 + s2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 2 + 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, 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 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s7 + z + z^2 + z' + z'^2 }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 2 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11, z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s10 :|: s10 >= 0, s10 <= z, z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

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

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

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

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

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

   encArg(z) -{ 1 + s1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s3 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, s3 >= 0, s3 <= s1 + s2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 2 + 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, 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 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s7 + z + z^2 + z' + z'^2 }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 2 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11, z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s10 :|: s10 >= 0, s10 <= z, z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {encode_s}
Previous analysis results are:
  minus: runtime: O(n^1) [2 + z'], size: O(n^1) [z]
  encode_0: runtime: O(1) [0], size: O(1) [0]
  plus: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_-: runtime: O(n^2) [2 + z + z^2 + 2*z' + z'^2], size: O(n^1) [z]
  encode_+: runtime: O(n^2) [1 + 2*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) -{ 1 + s1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s3 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, s3 >= 0, s3 <= s1 + s2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 2 + 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, 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 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s7 + z + z^2 + z' + z'^2 }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 2 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11, z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s10 :|: s10 >= 0, s10 <= z, z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

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

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

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

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

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

   encArg(z) -{ 1 + s1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s3 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, s3 >= 0, s3 <= s1 + s2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 2 + 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, 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 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s7 + z + z^2 + z' + z'^2 }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 2 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11, z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s10 :|: s10 >= 0, s10 <= z, z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

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

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

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

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

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

   encArg(z) -{ 1 + s1 + x_1 + x_1^2 + x_2 + x_2^2 }-> s3 :|: s1 >= 0, s1 <= x_1, s2 >= 0, s2 <= x_2, s3 >= 0, s3 <= s1 + s2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 2 + 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, 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 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0
   encode_+(z, z') -{ 1 + s7 + z + z^2 + z' + z'^2 }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8, z >= 0, z' >= 0
   encode_+(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_-(z, z') -{ 2 + s12 + z + z^2 + z' + z'^2 }-> s13 :|: s11 >= 0, s11 <= z, s12 >= 0, s12 <= z', s13 >= 0, s13 <= s11, z >= 0, z' >= 0
   encode_-(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ z + z^2 }-> 1 + s10 :|: s10 >= 0, s10 <= z, z >= 0
   minus(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
   minus(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
   minus(z, z') -{ 0 }-> 0 :|: 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 - 1 + z', z - 1 >= 0, z' >= 0

Function symbols to be analyzed: 
Previous analysis results are:
  minus: runtime: O(n^1) [2 + z'], size: O(n^1) [z]
  encode_0: runtime: O(1) [0], size: O(1) [0]
  plus: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [z + z^2], size: O(n^1) [z]
  encode_-: runtime: O(n^2) [2 + z + z^2 + 2*z' + z'^2], size: O(n^1) [z]
  encode_+: runtime: O(n^2) [1 + 2*z + z^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]

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

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

(66)
BOUNDS(1, n^2)

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

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

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

   +'(0', y) -> y
   +'(s(x), y) -> s(+'(x, y))
   -(0', y) -> 0'
   -(x, 0') -> x
   -(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2))

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

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

(70)
Obligation:
TRS:
Rules:
+'(0', y) -> y
+'(s(x), y) -> s(+'(x, y))
-(0', y) -> 0'
-(x, 0') -> x
-(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2))

Types:
+' :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
0' :: 0':s:cons_+:cons_-
s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encArg :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_0 :: 0':s:cons_+:cons_-
encode_s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
hole_0':s:cons_+:cons_-1_3 :: 0':s:cons_+:cons_-
gen_0':s:cons_+:cons_-2_3 :: Nat -> 0':s:cons_+:cons_-

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

(71) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
+', -, encArg

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

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

(72)
Obligation:
TRS:
Rules:
+'(0', y) -> y
+'(s(x), y) -> s(+'(x, y))
-(0', y) -> 0'
-(x, 0') -> x
-(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2))

Types:
+' :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
0' :: 0':s:cons_+:cons_-
s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encArg :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_0 :: 0':s:cons_+:cons_-
encode_s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
hole_0':s:cons_+:cons_-1_3 :: 0':s:cons_+:cons_-
gen_0':s:cons_+:cons_-2_3 :: Nat -> 0':s:cons_+:cons_-


Generator Equations:
gen_0':s:cons_+:cons_-2_3(0) <=> 0'
gen_0':s:cons_+:cons_-2_3(+(x, 1)) <=> s(gen_0':s:cons_+:cons_-2_3(x))


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

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

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

(73) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
+'(gen_0':s:cons_+:cons_-2_3(n4_3), gen_0':s:cons_+:cons_-2_3(b)) -> gen_0':s:cons_+:cons_-2_3(+(n4_3, b)), rt in Omega(1 + n4_3)

Induction Base:
+'(gen_0':s:cons_+:cons_-2_3(0), gen_0':s:cons_+:cons_-2_3(b)) ->_R^Omega(1)
gen_0':s:cons_+:cons_-2_3(b)

Induction Step:
+'(gen_0':s:cons_+:cons_-2_3(+(n4_3, 1)), gen_0':s:cons_+:cons_-2_3(b)) ->_R^Omega(1)
s(+'(gen_0':s:cons_+:cons_-2_3(n4_3), gen_0':s:cons_+:cons_-2_3(b))) ->_IH
s(gen_0':s:cons_+:cons_-2_3(+(b, c5_3)))

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

(74)
Complex Obligation (BEST)

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

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

TRS:
Rules:
+'(0', y) -> y
+'(s(x), y) -> s(+'(x, y))
-(0', y) -> 0'
-(x, 0') -> x
-(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2))

Types:
+' :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
0' :: 0':s:cons_+:cons_-
s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encArg :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_0 :: 0':s:cons_+:cons_-
encode_s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
hole_0':s:cons_+:cons_-1_3 :: 0':s:cons_+:cons_-
gen_0':s:cons_+:cons_-2_3 :: Nat -> 0':s:cons_+:cons_-


Generator Equations:
gen_0':s:cons_+:cons_-2_3(0) <=> 0'
gen_0':s:cons_+:cons_-2_3(+(x, 1)) <=> s(gen_0':s:cons_+:cons_-2_3(x))


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

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

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

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

(77)
BOUNDS(n^1, INF)

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

(78)
Obligation:
TRS:
Rules:
+'(0', y) -> y
+'(s(x), y) -> s(+'(x, y))
-(0', y) -> 0'
-(x, 0') -> x
-(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2))

Types:
+' :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
0' :: 0':s:cons_+:cons_-
s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encArg :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_0 :: 0':s:cons_+:cons_-
encode_s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
hole_0':s:cons_+:cons_-1_3 :: 0':s:cons_+:cons_-
gen_0':s:cons_+:cons_-2_3 :: Nat -> 0':s:cons_+:cons_-


Lemmas:
+'(gen_0':s:cons_+:cons_-2_3(n4_3), gen_0':s:cons_+:cons_-2_3(b)) -> gen_0':s:cons_+:cons_-2_3(+(n4_3, b)), rt in Omega(1 + n4_3)


Generator Equations:
gen_0':s:cons_+:cons_-2_3(0) <=> 0'
gen_0':s:cons_+:cons_-2_3(+(x, 1)) <=> s(gen_0':s:cons_+:cons_-2_3(x))


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

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

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

(79) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
-(gen_0':s:cons_+:cons_-2_3(n565_3), gen_0':s:cons_+:cons_-2_3(n565_3)) -> gen_0':s:cons_+:cons_-2_3(0), rt in Omega(1 + n565_3)

Induction Base:
-(gen_0':s:cons_+:cons_-2_3(0), gen_0':s:cons_+:cons_-2_3(0)) ->_R^Omega(1)
0'

Induction Step:
-(gen_0':s:cons_+:cons_-2_3(+(n565_3, 1)), gen_0':s:cons_+:cons_-2_3(+(n565_3, 1))) ->_R^Omega(1)
-(gen_0':s:cons_+:cons_-2_3(n565_3), gen_0':s:cons_+:cons_-2_3(n565_3)) ->_IH
gen_0':s:cons_+:cons_-2_3(0)

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

(80)
Obligation:
TRS:
Rules:
+'(0', y) -> y
+'(s(x), y) -> s(+'(x, y))
-(0', y) -> 0'
-(x, 0') -> x
-(s(x), s(y)) -> -(x, 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_-(x_1, x_2)) -> -(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_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2))

Types:
+' :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
0' :: 0':s:cons_+:cons_-
s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encArg :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
cons_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_+ :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_0 :: 0':s:cons_+:cons_-
encode_s :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
encode_- :: 0':s:cons_+:cons_- -> 0':s:cons_+:cons_- -> 0':s:cons_+:cons_-
hole_0':s:cons_+:cons_-1_3 :: 0':s:cons_+:cons_-
gen_0':s:cons_+:cons_-2_3 :: Nat -> 0':s:cons_+:cons_-


Lemmas:
+'(gen_0':s:cons_+:cons_-2_3(n4_3), gen_0':s:cons_+:cons_-2_3(b)) -> gen_0':s:cons_+:cons_-2_3(+(n4_3, b)), rt in Omega(1 + n4_3)
-(gen_0':s:cons_+:cons_-2_3(n565_3), gen_0':s:cons_+:cons_-2_3(n565_3)) -> gen_0':s:cons_+:cons_-2_3(0), rt in Omega(1 + n565_3)


Generator Equations:
gen_0':s:cons_+:cons_-2_3(0) <=> 0'
gen_0':s:cons_+:cons_-2_3(+(x, 1)) <=> s(gen_0':s:cons_+:cons_-2_3(x))


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

(81) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_0':s:cons_+:cons_-2_3(n839_3)) -> gen_0':s:cons_+:cons_-2_3(n839_3), rt in Omega(0)

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

Induction Step:
encArg(gen_0':s:cons_+:cons_-2_3(+(n839_3, 1))) ->_R^Omega(0)
s(encArg(gen_0':s:cons_+:cons_-2_3(n839_3))) ->_IH
s(gen_0':s:cons_+:cons_-2_3(c840_3))

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

(82)
BOUNDS(1, INF)