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), 167 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), 0 ms]
    (14) CpxTypedWeightedCompleteTrs
    (15) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (16) CpxRNTS
    (17) SimplificationProof [BOTH BOUNDS(ID, ID), 0 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), 24 ms]
    (24) CpxRNTS
    (25) IntTrsBoundProof [UPPER BOUND(ID), 5 ms]
    (26) CpxRNTS
    (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (28) CpxRNTS
    (29) IntTrsBoundProof [UPPER BOUND(ID), 206 ms]
    (30) CpxRNTS
    (31) IntTrsBoundProof [UPPER BOUND(ID), 16 ms]
    (32) CpxRNTS
    (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (34) CpxRNTS
    (35) IntTrsBoundProof [UPPER BOUND(ID), 136 ms]
    (36) CpxRNTS
    (37) IntTrsBoundProof [UPPER BOUND(ID), 2 ms]
    (38) CpxRNTS
    (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (40) CpxRNTS
    (41) IntTrsBoundProof [UPPER BOUND(ID), 721 ms]
    (42) CpxRNTS
    (43) IntTrsBoundProof [UPPER BOUND(ID), 320 ms]
    (44) CpxRNTS
    (45) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (46) CpxRNTS
    (47) IntTrsBoundProof [UPPER BOUND(ID), 197 ms]
    (48) CpxRNTS
    (49) IntTrsBoundProof [UPPER BOUND(ID), 7 ms]
    (50) CpxRNTS
    (51) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (52) CpxRNTS
    (53) IntTrsBoundProof [UPPER BOUND(ID), 171 ms]
    (54) CpxRNTS
    (55) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (56) CpxRNTS
    (57) FinalProof [FINISHED, 0 ms]
    (58) BOUNDS(1, n^2)
(59) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(60) CpxRelTRS
    (61) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (62) typed CpxTrs
    (63) OrderProof [LOWER BOUND(ID), 0 ms]
    (64) typed CpxTrs
    (65) RewriteLemmaProof [LOWER BOUND(ID), 1126 ms]
    (66) BEST
        (67) proven lower bound
            (68) LowerBoundPropagationProof [FINISHED, 0 ms]
            (69) BOUNDS(n^1, INF)
        (70) typed CpxTrs
            (71) RewriteLemmaProof [LOWER BOUND(ID), 11 ms]
            (72) 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:

   rev(a) -> a
   rev(b) -> b
   rev(++(x, y)) -> ++(rev(y), rev(x))
   rev(++(x, x)) -> rev(x)

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(a) -> a
   encArg(b) -> b
   encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encArg(cons_rev(x_1)) -> rev(encArg(x_1))
   encode_rev(x_1) -> rev(encArg(x_1))
   encode_a -> a
   encode_b -> b
   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:

   rev(a) -> a
   rev(b) -> b
   rev(++(x, y)) -> ++(rev(y), rev(x))
   rev(++(x, x)) -> rev(x)

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

   encArg(a) -> a
   encArg(b) -> b
   encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encArg(cons_rev(x_1)) -> rev(encArg(x_1))
   encode_rev(x_1) -> rev(encArg(x_1))
   encode_a -> a
   encode_b -> b
   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:

   rev(a) -> a
   rev(b) -> b
   rev(++(x, y)) -> ++(rev(y), rev(x))
   rev(++(x, x)) -> rev(x)

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

   encArg(a) -> a
   encArg(b) -> b
   encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encArg(cons_rev(x_1)) -> rev(encArg(x_1))
   encode_rev(x_1) -> rev(encArg(x_1))
   encode_a -> a
   encode_b -> b
   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:

   rev(a) -> a
   rev(b) -> b
   rev(++(x, y)) -> ++(rev(y), rev(x))
   rev(++(x, x)) -> rev(x)

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

   encArg(a) -> a
   encArg(b) -> b
   encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encArg(cons_rev(x_1)) -> rev(encArg(x_1))
   encode_rev(x_1) -> rev(encArg(x_1))
   encode_a -> a
   encode_b -> b
   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:

   rev(a) -> a [1]
   rev(b) -> b [1]
   rev(++(x, y)) -> ++(rev(y), rev(x)) [1]
   rev(++(x, x)) -> rev(x) [1]
   encArg(a) -> a [0]
   encArg(b) -> b [0]
   encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_rev(x_1)) -> rev(encArg(x_1)) [0]
   encode_rev(x_1) -> rev(encArg(x_1)) [0]
   encode_a -> a [0]
   encode_b -> b [0]
   encode_++(x_1, x_2) -> ++(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:

   rev(a) -> a [1]
   rev(b) -> b [1]
   rev(++(x, y)) -> ++(rev(y), rev(x)) [1]
   rev(++(x, x)) -> rev(x) [1]
   encArg(a) -> a [0]
   encArg(b) -> b [0]
   encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_rev(x_1)) -> rev(encArg(x_1)) [0]
   encode_rev(x_1) -> rev(encArg(x_1)) [0]
   encode_a -> a [0]
   encode_b -> b [0]
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) [0]

The TRS has the following type information:
rev :: a:b:++:cons_rev -> a:b:++:cons_rev
a :: a:b:++:cons_rev
b :: a:b:++:cons_rev
++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev
encArg :: a:b:++:cons_rev -> a:b:++:cons_rev
cons_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_a :: a:b:++:cons_rev
encode_b :: a:b:++:cons_rev
encode_++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev

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:

   rev_1
   encArg_1
   encode_rev_1
   encode_a
   encode_b
   encode_++_2

Due to the following rules being added:

   encArg(v0) -> null_encArg [0]
   encode_rev(v0) -> null_encode_rev [0]
   encode_a -> null_encode_a [0]
   encode_b -> null_encode_b [0]
   encode_++(v0, v1) -> null_encode_++ [0]
   rev(v0) -> null_rev [0]

And the following fresh constants:    null_encArg, null_encode_rev, null_encode_a, null_encode_b, null_encode_++, null_rev

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

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

   rev(a) -> a [1]
   rev(b) -> b [1]
   rev(++(x, y)) -> ++(rev(y), rev(x)) [1]
   rev(++(x, x)) -> rev(x) [1]
   encArg(a) -> a [0]
   encArg(b) -> b [0]
   encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_rev(x_1)) -> rev(encArg(x_1)) [0]
   encode_rev(x_1) -> rev(encArg(x_1)) [0]
   encode_a -> a [0]
   encode_b -> b [0]
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) [0]
   encArg(v0) -> null_encArg [0]
   encode_rev(v0) -> null_encode_rev [0]
   encode_a -> null_encode_a [0]
   encode_b -> null_encode_b [0]
   encode_++(v0, v1) -> null_encode_++ [0]
   rev(v0) -> null_rev [0]

The TRS has the following type information:
rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
a :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
b :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
++ :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encArg :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
cons_rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encode_rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encode_a :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encode_b :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encode_++ :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encArg :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encode_rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encode_a :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encode_b :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encode_++ :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev

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:

   rev(a) -> a [1]
   rev(b) -> b [1]
   rev(++(x, y)) -> ++(rev(y), rev(x)) [1]
   rev(++(x, x)) -> rev(x) [1]
   encArg(a) -> a [0]
   encArg(b) -> b [0]
   encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2)) [0]
   encArg(cons_rev(a)) -> rev(a) [0]
   encArg(cons_rev(b)) -> rev(b) [0]
   encArg(cons_rev(++(x_1', x_2'))) -> rev(++(encArg(x_1'), encArg(x_2'))) [0]
   encArg(cons_rev(cons_rev(x_1''))) -> rev(rev(encArg(x_1''))) [0]
   encArg(cons_rev(x_1)) -> rev(null_encArg) [0]
   encode_rev(a) -> rev(a) [0]
   encode_rev(b) -> rev(b) [0]
   encode_rev(++(x_11, x_2'')) -> rev(++(encArg(x_11), encArg(x_2''))) [0]
   encode_rev(cons_rev(x_12)) -> rev(rev(encArg(x_12))) [0]
   encode_rev(x_1) -> rev(null_encArg) [0]
   encode_a -> a [0]
   encode_b -> b [0]
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2)) [0]
   encArg(v0) -> null_encArg [0]
   encode_rev(v0) -> null_encode_rev [0]
   encode_a -> null_encode_a [0]
   encode_b -> null_encode_b [0]
   encode_++(v0, v1) -> null_encode_++ [0]
   rev(v0) -> null_rev [0]

The TRS has the following type information:
rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
a :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
b :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
++ :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encArg :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
cons_rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encode_rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encode_a :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encode_b :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
encode_++ :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev -> a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encArg :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encode_rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encode_a :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encode_b :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_encode_++ :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev
null_rev :: a:b:++:cons_rev:null_encArg:null_encode_rev:null_encode_a:null_encode_b:null_encode_++:null_rev

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:

   a => 0
   b => 1
   null_encArg => 0
   null_encode_rev => 0
   null_encode_a => 0
   null_encode_b => 0
   null_encode_++ => 0
   null_rev => 0

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

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

   encArg(z) -{ 0 }-> rev(rev(encArg(x_1''))) :|: z = 1 + (1 + x_1''), x_1'' >= 0
   encArg(z) -{ 0 }-> rev(1) :|: z = 1 + 1
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + 0
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + x_1, x_1 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encArg(z) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_++(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_++(z, z') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 0 }-> rev(rev(encArg(x_12))) :|: z = 1 + x_12, x_12 >= 0
   encode_rev(z) -{ 0 }-> rev(1) :|: z = 1
   encode_rev(z) -{ 0 }-> rev(0) :|: z = 0
   encode_rev(z) -{ 0 }-> rev(0) :|: x_1 >= 0, z = x_1
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   rev(z) -{ 1 }-> rev(x) :|: z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   rev(z) -{ 1 }-> 1 + rev(y) + rev(x) :|: z = 1 + x + y, x >= 0, y >= 0


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

(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 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1) :|: z = 1 + 1
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + 0
   encArg(z) -{ 0 }-> rev(0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1) :|: z = 1
   encode_rev(z) -{ 0 }-> rev(0) :|: z = 0
   encode_rev(z) -{ 0 }-> rev(0) :|: z >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> rev(x) :|: z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> 1 + rev(y) + rev(x) :|: z = 1 + x + y, x >= 0, y >= 0


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

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

   { encode_a }
   { rev }
   { encode_b }
   { encArg }
   { encode_rev }
   { encode_++ }

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

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

   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1) :|: z = 1 + 1
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + 0
   encArg(z) -{ 0 }-> rev(0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1) :|: z = 1
   encode_rev(z) -{ 0 }-> rev(0) :|: z = 0
   encode_rev(z) -{ 0 }-> rev(0) :|: z >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> rev(x) :|: z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> 1 + rev(y) + rev(x) :|: z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_a}, {rev}, {encode_b}, {encArg}, {encode_rev}, {encode_++}

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

(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 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1) :|: z = 1 + 1
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + 0
   encArg(z) -{ 0 }-> rev(0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1) :|: z = 1
   encode_rev(z) -{ 0 }-> rev(0) :|: z = 0
   encode_rev(z) -{ 0 }-> rev(0) :|: z >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> rev(x) :|: z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> 1 + rev(y) + rev(x) :|: z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_a}, {rev}, {encode_b}, {encArg}, {encode_rev}, {encode_++}

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

(23) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1) :|: z = 1 + 1
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + 0
   encArg(z) -{ 0 }-> rev(0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1) :|: z = 1
   encode_rev(z) -{ 0 }-> rev(0) :|: z = 0
   encode_rev(z) -{ 0 }-> rev(0) :|: z >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> rev(x) :|: z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> 1 + rev(y) + rev(x) :|: z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_a}, {rev}, {encode_b}, {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: ?, size: O(1) [0]

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

(25) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1) :|: z = 1 + 1
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + 0
   encArg(z) -{ 0 }-> rev(0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1) :|: z = 1
   encode_rev(z) -{ 0 }-> rev(0) :|: z = 0
   encode_rev(z) -{ 0 }-> rev(0) :|: z >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> rev(x) :|: z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> 1 + rev(y) + rev(x) :|: z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {rev}, {encode_b}, {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]

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

(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 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1) :|: z = 1 + 1
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + 0
   encArg(z) -{ 0 }-> rev(0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1) :|: z = 1
   encode_rev(z) -{ 0 }-> rev(0) :|: z = 0
   encode_rev(z) -{ 0 }-> rev(0) :|: z >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> rev(x) :|: z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> 1 + rev(y) + rev(x) :|: z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {rev}, {encode_b}, {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]

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

(29) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1) :|: z = 1 + 1
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + 0
   encArg(z) -{ 0 }-> rev(0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1) :|: z = 1
   encode_rev(z) -{ 0 }-> rev(0) :|: z = 0
   encode_rev(z) -{ 0 }-> rev(0) :|: z >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> rev(x) :|: z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> 1 + rev(y) + rev(x) :|: z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {rev}, {encode_b}, {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: ?, size: O(n^1) [1 + z]

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

(31) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1) :|: z = 1 + 1
   encArg(z) -{ 0 }-> rev(0) :|: z = 1 + 0
   encArg(z) -{ 0 }-> rev(0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1) :|: z = 1
   encode_rev(z) -{ 0 }-> rev(0) :|: z = 0
   encode_rev(z) -{ 0 }-> rev(0) :|: z >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> rev(x) :|: z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 1 }-> 1 + rev(y) + rev(x) :|: z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_b}, {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]

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

(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) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_b}, {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]

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

(35) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_b}, {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: ?, size: O(1) [1]

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

(37) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]

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

(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) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]

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

(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: 2 + 2*z

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

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

   encArg(z) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encArg}, {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]
  encArg: runtime: ?, size: O(n^1) [2 + 2*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: 3 + 9*z + 8*z^2

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

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

   encArg(z) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> rev(rev(encArg(z - 2))) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> rev(1 + encArg(x_1') + encArg(x_2')) :|: z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   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_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 0 }-> 1 + encArg(z) + encArg(z') :|: z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> rev(rev(encArg(z - 1))) :|: z - 1 >= 0
   encode_rev(z) -{ 0 }-> rev(1 + encArg(x_11) + encArg(x_2'')) :|: z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]
  encArg: runtime: O(n^2) [3 + 9*z + 8*z^2], size: O(n^1) [2 + 2*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) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 9 + 2*s10 + 2*s9 + 9*x_1' + 8*x_1'^2 + 9*x_2' + 8*x_2'^2 }-> s11 :|: s9 >= 0, s9 <= 2 * x_1' + 2, s10 >= 0, s10 <= 2 * x_2' + 2, s11 >= 0, s11 <= 1 + s9 + s10 + 1, z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 19 + 2*s12 + 2*s13 + -23*z + 8*z^2 }-> s14 :|: s12 >= 0, s12 <= 2 * (z - 2) + 2, s13 >= 0, s13 <= s12 + 1, s14 >= 0, s14 <= s13 + 1, z - 2 >= 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 6 + 9*x_1 + 8*x_1^2 + 9*x_2 + 8*x_2^2 }-> 1 + s7 + s8 :|: s7 >= 0, s7 <= 2 * x_1 + 2, s8 >= 0, s8 <= 2 * x_2 + 2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 6 + 9*z + 8*z^2 + 9*z' + 8*z'^2 }-> 1 + s21 + s22 :|: s21 >= 0, s21 <= 2 * z + 2, s22 >= 0, s22 <= 2 * z' + 2, z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 9 + 2*s15 + 2*s16 + 9*x_11 + 8*x_11^2 + 9*x_2'' + 8*x_2''^2 }-> s17 :|: s15 >= 0, s15 <= 2 * x_11 + 2, s16 >= 0, s16 <= 2 * x_2'' + 2, s17 >= 0, s17 <= 1 + s15 + s16 + 1, z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 4 + 2*s18 + 2*s19 + -7*z + 8*z^2 }-> s20 :|: s18 >= 0, s18 <= 2 * (z - 1) + 2, s19 >= 0, s19 <= s18 + 1, s20 >= 0, s20 <= s19 + 1, z - 1 >= 0
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]
  encArg: runtime: O(n^2) [3 + 9*z + 8*z^2], size: O(n^1) [2 + 2*z]

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

(47) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 9 + 2*s10 + 2*s9 + 9*x_1' + 8*x_1'^2 + 9*x_2' + 8*x_2'^2 }-> s11 :|: s9 >= 0, s9 <= 2 * x_1' + 2, s10 >= 0, s10 <= 2 * x_2' + 2, s11 >= 0, s11 <= 1 + s9 + s10 + 1, z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 19 + 2*s12 + 2*s13 + -23*z + 8*z^2 }-> s14 :|: s12 >= 0, s12 <= 2 * (z - 2) + 2, s13 >= 0, s13 <= s12 + 1, s14 >= 0, s14 <= s13 + 1, z - 2 >= 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 6 + 9*x_1 + 8*x_1^2 + 9*x_2 + 8*x_2^2 }-> 1 + s7 + s8 :|: s7 >= 0, s7 <= 2 * x_1 + 2, s8 >= 0, s8 <= 2 * x_2 + 2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 6 + 9*z + 8*z^2 + 9*z' + 8*z'^2 }-> 1 + s21 + s22 :|: s21 >= 0, s21 <= 2 * z + 2, s22 >= 0, s22 <= 2 * z' + 2, z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 9 + 2*s15 + 2*s16 + 9*x_11 + 8*x_11^2 + 9*x_2'' + 8*x_2''^2 }-> s17 :|: s15 >= 0, s15 <= 2 * x_11 + 2, s16 >= 0, s16 <= 2 * x_2'' + 2, s17 >= 0, s17 <= 1 + s15 + s16 + 1, z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 4 + 2*s18 + 2*s19 + -7*z + 8*z^2 }-> s20 :|: s18 >= 0, s18 <= 2 * (z - 1) + 2, s19 >= 0, s19 <= s18 + 1, s20 >= 0, s20 <= s19 + 1, z - 1 >= 0
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_rev}, {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]
  encArg: runtime: O(n^2) [3 + 9*z + 8*z^2], size: O(n^1) [2 + 2*z]
  encode_rev: runtime: ?, size: O(n^1) [4 + 2*z]

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

(49) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   encArg(z) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 9 + 2*s10 + 2*s9 + 9*x_1' + 8*x_1'^2 + 9*x_2' + 8*x_2'^2 }-> s11 :|: s9 >= 0, s9 <= 2 * x_1' + 2, s10 >= 0, s10 <= 2 * x_2' + 2, s11 >= 0, s11 <= 1 + s9 + s10 + 1, z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 19 + 2*s12 + 2*s13 + -23*z + 8*z^2 }-> s14 :|: s12 >= 0, s12 <= 2 * (z - 2) + 2, s13 >= 0, s13 <= s12 + 1, s14 >= 0, s14 <= s13 + 1, z - 2 >= 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 6 + 9*x_1 + 8*x_1^2 + 9*x_2 + 8*x_2^2 }-> 1 + s7 + s8 :|: s7 >= 0, s7 <= 2 * x_1 + 2, s8 >= 0, s8 <= 2 * x_2 + 2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 6 + 9*z + 8*z^2 + 9*z' + 8*z'^2 }-> 1 + s21 + s22 :|: s21 >= 0, s21 <= 2 * z + 2, s22 >= 0, s22 <= 2 * z' + 2, z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 9 + 2*s15 + 2*s16 + 9*x_11 + 8*x_11^2 + 9*x_2'' + 8*x_2''^2 }-> s17 :|: s15 >= 0, s15 <= 2 * x_11 + 2, s16 >= 0, s16 <= 2 * x_2'' + 2, s17 >= 0, s17 <= 1 + s15 + s16 + 1, z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 4 + 2*s18 + 2*s19 + -7*z + 8*z^2 }-> s20 :|: s18 >= 0, s18 <= 2 * (z - 1) + 2, s19 >= 0, s19 <= s18 + 1, s20 >= 0, s20 <= s19 + 1, z - 1 >= 0
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]
  encArg: runtime: O(n^2) [3 + 9*z + 8*z^2], size: O(n^1) [2 + 2*z]
  encode_rev: runtime: O(n^2) [26 + 29*z + 24*z^2], size: O(n^1) [4 + 2*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) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 9 + 2*s10 + 2*s9 + 9*x_1' + 8*x_1'^2 + 9*x_2' + 8*x_2'^2 }-> s11 :|: s9 >= 0, s9 <= 2 * x_1' + 2, s10 >= 0, s10 <= 2 * x_2' + 2, s11 >= 0, s11 <= 1 + s9 + s10 + 1, z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 19 + 2*s12 + 2*s13 + -23*z + 8*z^2 }-> s14 :|: s12 >= 0, s12 <= 2 * (z - 2) + 2, s13 >= 0, s13 <= s12 + 1, s14 >= 0, s14 <= s13 + 1, z - 2 >= 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 6 + 9*x_1 + 8*x_1^2 + 9*x_2 + 8*x_2^2 }-> 1 + s7 + s8 :|: s7 >= 0, s7 <= 2 * x_1 + 2, s8 >= 0, s8 <= 2 * x_2 + 2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 6 + 9*z + 8*z^2 + 9*z' + 8*z'^2 }-> 1 + s21 + s22 :|: s21 >= 0, s21 <= 2 * z + 2, s22 >= 0, s22 <= 2 * z' + 2, z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 9 + 2*s15 + 2*s16 + 9*x_11 + 8*x_11^2 + 9*x_2'' + 8*x_2''^2 }-> s17 :|: s15 >= 0, s15 <= 2 * x_11 + 2, s16 >= 0, s16 <= 2 * x_2'' + 2, s17 >= 0, s17 <= 1 + s15 + s16 + 1, z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 4 + 2*s18 + 2*s19 + -7*z + 8*z^2 }-> s20 :|: s18 >= 0, s18 <= 2 * (z - 1) + 2, s19 >= 0, s19 <= s18 + 1, s20 >= 0, s20 <= s19 + 1, z - 1 >= 0
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]
  encArg: runtime: O(n^2) [3 + 9*z + 8*z^2], size: O(n^1) [2 + 2*z]
  encode_rev: runtime: O(n^2) [26 + 29*z + 24*z^2], size: O(n^1) [4 + 2*z]

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

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

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

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

   encArg(z) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 9 + 2*s10 + 2*s9 + 9*x_1' + 8*x_1'^2 + 9*x_2' + 8*x_2'^2 }-> s11 :|: s9 >= 0, s9 <= 2 * x_1' + 2, s10 >= 0, s10 <= 2 * x_2' + 2, s11 >= 0, s11 <= 1 + s9 + s10 + 1, z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 19 + 2*s12 + 2*s13 + -23*z + 8*z^2 }-> s14 :|: s12 >= 0, s12 <= 2 * (z - 2) + 2, s13 >= 0, s13 <= s12 + 1, s14 >= 0, s14 <= s13 + 1, z - 2 >= 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 6 + 9*x_1 + 8*x_1^2 + 9*x_2 + 8*x_2^2 }-> 1 + s7 + s8 :|: s7 >= 0, s7 <= 2 * x_1 + 2, s8 >= 0, s8 <= 2 * x_2 + 2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 6 + 9*z + 8*z^2 + 9*z' + 8*z'^2 }-> 1 + s21 + s22 :|: s21 >= 0, s21 <= 2 * z + 2, s22 >= 0, s22 <= 2 * z' + 2, z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 9 + 2*s15 + 2*s16 + 9*x_11 + 8*x_11^2 + 9*x_2'' + 8*x_2''^2 }-> s17 :|: s15 >= 0, s15 <= 2 * x_11 + 2, s16 >= 0, s16 <= 2 * x_2'' + 2, s17 >= 0, s17 <= 1 + s15 + s16 + 1, z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 4 + 2*s18 + 2*s19 + -7*z + 8*z^2 }-> s20 :|: s18 >= 0, s18 <= 2 * (z - 1) + 2, s19 >= 0, s19 <= s18 + 1, s20 >= 0, s20 <= s19 + 1, z - 1 >= 0
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: {encode_++}
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]
  encArg: runtime: O(n^2) [3 + 9*z + 8*z^2], size: O(n^1) [2 + 2*z]
  encode_rev: runtime: O(n^2) [26 + 29*z + 24*z^2], size: O(n^1) [4 + 2*z]
  encode_++: runtime: ?, size: O(n^1) [5 + 2*z + 2*z']

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

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

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

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

   encArg(z) -{ 1 }-> s1 :|: s1 >= 0, s1 <= 0 + 1, z = 1 + 0
   encArg(z) -{ 9 + 2*s10 + 2*s9 + 9*x_1' + 8*x_1'^2 + 9*x_2' + 8*x_2'^2 }-> s11 :|: s9 >= 0, s9 <= 2 * x_1' + 2, s10 >= 0, s10 <= 2 * x_2' + 2, s11 >= 0, s11 <= 1 + s9 + s10 + 1, z = 1 + (1 + x_1' + x_2'), x_2' >= 0, x_1' >= 0
   encArg(z) -{ 19 + 2*s12 + 2*s13 + -23*z + 8*z^2 }-> s14 :|: s12 >= 0, s12 <= 2 * (z - 2) + 2, s13 >= 0, s13 <= s12 + 1, s14 >= 0, s14 <= s13 + 1, z - 2 >= 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 1 + 1, z = 1 + 1
   encArg(z) -{ 1 }-> s3 :|: s3 >= 0, s3 <= 0 + 1, z - 1 >= 0
   encArg(z) -{ 0 }-> 1 :|: z = 1
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 6 + 9*x_1 + 8*x_1^2 + 9*x_2 + 8*x_2^2 }-> 1 + s7 + s8 :|: s7 >= 0, s7 <= 2 * x_1 + 2, s8 >= 0, s8 <= 2 * x_2 + 2, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encode_++(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_++(z, z') -{ 6 + 9*z + 8*z^2 + 9*z' + 8*z'^2 }-> 1 + s21 + s22 :|: s21 >= 0, s21 <= 2 * z + 2, s22 >= 0, s22 <= 2 * z' + 2, z >= 0, z' >= 0
   encode_a -{ 0 }-> 0 :|: 
   encode_b -{ 0 }-> 1 :|: 
   encode_b -{ 0 }-> 0 :|: 
   encode_rev(z) -{ 9 + 2*s15 + 2*s16 + 9*x_11 + 8*x_11^2 + 9*x_2'' + 8*x_2''^2 }-> s17 :|: s15 >= 0, s15 <= 2 * x_11 + 2, s16 >= 0, s16 <= 2 * x_2'' + 2, s17 >= 0, s17 <= 1 + s15 + s16 + 1, z = 1 + x_11 + x_2'', x_11 >= 0, x_2'' >= 0
   encode_rev(z) -{ 4 + 2*s18 + 2*s19 + -7*z + 8*z^2 }-> s20 :|: s18 >= 0, s18 <= 2 * (z - 1) + 2, s19 >= 0, s19 <= s18 + 1, s20 >= 0, s20 <= s19 + 1, z - 1 >= 0
   encode_rev(z) -{ 1 }-> s4 :|: s4 >= 0, s4 <= 0 + 1, z = 0
   encode_rev(z) -{ 3 }-> s5 :|: s5 >= 0, s5 <= 1 + 1, z = 1
   encode_rev(z) -{ 1 }-> s6 :|: s6 >= 0, s6 <= 0 + 1, z >= 0
   encode_rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 2 + 2*x }-> s'' :|: s'' >= 0, s'' <= x + 1, z = 1 + x + x, x >= 0
   rev(z) -{ 1 }-> 1 :|: z = 1
   rev(z) -{ 1 }-> 0 :|: z = 0
   rev(z) -{ 0 }-> 0 :|: z >= 0
   rev(z) -{ 3 + 2*x + 2*y }-> 1 + s + s' :|: s >= 0, s <= y + 1, s' >= 0, s' <= x + 1, z = 1 + x + y, x >= 0, y >= 0

Function symbols to be analyzed: 
Previous analysis results are:
  encode_a: runtime: O(1) [0], size: O(1) [0]
  rev: runtime: O(n^1) [1 + 2*z], size: O(n^1) [1 + z]
  encode_b: runtime: O(1) [0], size: O(1) [1]
  encArg: runtime: O(n^2) [3 + 9*z + 8*z^2], size: O(n^1) [2 + 2*z]
  encode_rev: runtime: O(n^2) [26 + 29*z + 24*z^2], size: O(n^1) [4 + 2*z]
  encode_++: runtime: O(n^2) [6 + 9*z + 8*z^2 + 9*z' + 8*z'^2], size: O(n^1) [5 + 2*z + 2*z']

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

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

(58)
BOUNDS(1, n^2)

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

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

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

   rev(a) -> a
   rev(b) -> b
   rev(++(x, y)) -> ++(rev(y), rev(x))
   rev(++(x, x)) -> rev(x)

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

   encArg(a) -> a
   encArg(b) -> b
   encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
   encArg(cons_rev(x_1)) -> rev(encArg(x_1))
   encode_rev(x_1) -> rev(encArg(x_1))
   encode_a -> a
   encode_b -> b
   encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))

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

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

(62)
Obligation:
TRS:
Rules:
rev(a) -> a
rev(b) -> b
rev(++(x, y)) -> ++(rev(y), rev(x))
rev(++(x, x)) -> rev(x)
encArg(a) -> a
encArg(b) -> b
encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
encArg(cons_rev(x_1)) -> rev(encArg(x_1))
encode_rev(x_1) -> rev(encArg(x_1))
encode_a -> a
encode_b -> b
encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))

Types:
rev :: a:b:++:cons_rev -> a:b:++:cons_rev
a :: a:b:++:cons_rev
b :: a:b:++:cons_rev
++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev
encArg :: a:b:++:cons_rev -> a:b:++:cons_rev
cons_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_a :: a:b:++:cons_rev
encode_b :: a:b:++:cons_rev
encode_++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev
hole_a:b:++:cons_rev1_0 :: a:b:++:cons_rev
gen_a:b:++:cons_rev2_0 :: Nat -> a:b:++:cons_rev

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

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

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

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

(64)
Obligation:
TRS:
Rules:
rev(a) -> a
rev(b) -> b
rev(++(x, y)) -> ++(rev(y), rev(x))
rev(++(x, x)) -> rev(x)
encArg(a) -> a
encArg(b) -> b
encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
encArg(cons_rev(x_1)) -> rev(encArg(x_1))
encode_rev(x_1) -> rev(encArg(x_1))
encode_a -> a
encode_b -> b
encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))

Types:
rev :: a:b:++:cons_rev -> a:b:++:cons_rev
a :: a:b:++:cons_rev
b :: a:b:++:cons_rev
++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev
encArg :: a:b:++:cons_rev -> a:b:++:cons_rev
cons_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_a :: a:b:++:cons_rev
encode_b :: a:b:++:cons_rev
encode_++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev
hole_a:b:++:cons_rev1_0 :: a:b:++:cons_rev
gen_a:b:++:cons_rev2_0 :: Nat -> a:b:++:cons_rev


Generator Equations:
gen_a:b:++:cons_rev2_0(0) <=> a
gen_a:b:++:cons_rev2_0(+(x, 1)) <=> ++(a, gen_a:b:++:cons_rev2_0(x))


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

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

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

(65) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
rev(gen_a:b:++:cons_rev2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0)

Induction Base:
rev(gen_a:b:++:cons_rev2_0(+(1, 0)))

Induction Step:
rev(gen_a:b:++:cons_rev2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1)
++(rev(gen_a:b:++:cons_rev2_0(+(1, n4_0))), rev(a)) ->_IH
++(*3_0, rev(a)) ->_R^Omega(1)
++(*3_0, a)

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

(66)
Complex Obligation (BEST)

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

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

TRS:
Rules:
rev(a) -> a
rev(b) -> b
rev(++(x, y)) -> ++(rev(y), rev(x))
rev(++(x, x)) -> rev(x)
encArg(a) -> a
encArg(b) -> b
encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
encArg(cons_rev(x_1)) -> rev(encArg(x_1))
encode_rev(x_1) -> rev(encArg(x_1))
encode_a -> a
encode_b -> b
encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))

Types:
rev :: a:b:++:cons_rev -> a:b:++:cons_rev
a :: a:b:++:cons_rev
b :: a:b:++:cons_rev
++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev
encArg :: a:b:++:cons_rev -> a:b:++:cons_rev
cons_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_a :: a:b:++:cons_rev
encode_b :: a:b:++:cons_rev
encode_++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev
hole_a:b:++:cons_rev1_0 :: a:b:++:cons_rev
gen_a:b:++:cons_rev2_0 :: Nat -> a:b:++:cons_rev


Generator Equations:
gen_a:b:++:cons_rev2_0(0) <=> a
gen_a:b:++:cons_rev2_0(+(x, 1)) <=> ++(a, gen_a:b:++:cons_rev2_0(x))


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

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

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

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

(69)
BOUNDS(n^1, INF)

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

(70)
Obligation:
TRS:
Rules:
rev(a) -> a
rev(b) -> b
rev(++(x, y)) -> ++(rev(y), rev(x))
rev(++(x, x)) -> rev(x)
encArg(a) -> a
encArg(b) -> b
encArg(++(x_1, x_2)) -> ++(encArg(x_1), encArg(x_2))
encArg(cons_rev(x_1)) -> rev(encArg(x_1))
encode_rev(x_1) -> rev(encArg(x_1))
encode_a -> a
encode_b -> b
encode_++(x_1, x_2) -> ++(encArg(x_1), encArg(x_2))

Types:
rev :: a:b:++:cons_rev -> a:b:++:cons_rev
a :: a:b:++:cons_rev
b :: a:b:++:cons_rev
++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev
encArg :: a:b:++:cons_rev -> a:b:++:cons_rev
cons_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_rev :: a:b:++:cons_rev -> a:b:++:cons_rev
encode_a :: a:b:++:cons_rev
encode_b :: a:b:++:cons_rev
encode_++ :: a:b:++:cons_rev -> a:b:++:cons_rev -> a:b:++:cons_rev
hole_a:b:++:cons_rev1_0 :: a:b:++:cons_rev
gen_a:b:++:cons_rev2_0 :: Nat -> a:b:++:cons_rev


Lemmas:
rev(gen_a:b:++:cons_rev2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0)


Generator Equations:
gen_a:b:++:cons_rev2_0(0) <=> a
gen_a:b:++:cons_rev2_0(+(x, 1)) <=> ++(a, gen_a:b:++:cons_rev2_0(x))


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

(71) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_a:b:++:cons_rev2_0(n11769_0)) -> gen_a:b:++:cons_rev2_0(n11769_0), rt in Omega(0)

Induction Base:
encArg(gen_a:b:++:cons_rev2_0(0)) ->_R^Omega(0)
a

Induction Step:
encArg(gen_a:b:++:cons_rev2_0(+(n11769_0, 1))) ->_R^Omega(0)
++(encArg(a), encArg(gen_a:b:++:cons_rev2_0(n11769_0))) ->_R^Omega(0)
++(a, encArg(gen_a:b:++:cons_rev2_0(n11769_0))) ->_IH
++(a, gen_a:b:++:cons_rev2_0(c11770_0))

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

(72)
BOUNDS(1, INF)