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


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


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


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

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 189 ms]
(4) CpxRelTRS
(5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxRelTRS
    (7) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
    (8) CdtProblem
    (9) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
    (10) CdtProblem
    (11) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) CdtProblem
    (13) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
    (14) CdtProblem
    (15) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (16) CdtProblem
    (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 91 ms]
    (18) CdtProblem
    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 193 ms]
    (20) CdtProblem
    (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 180 ms]
    (22) CdtProblem
    (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 162 ms]
    (24) CdtProblem
    (25) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
    (26) BOUNDS(1, 1)
(27) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(28) TRS for Loop Detection
    (29) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (30) BEST
        (31) proven lower bound
            (32) LowerBoundPropagationProof [FINISHED, 0 ms]
            (33) BOUNDS(n^1, INF)
        (34) TRS for Loop Detection


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

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

   concat(leaf, Y) -> Y
   concat(cons(U, V), Y) -> cons(U, concat(V, Y))
   lessleaves(X, leaf) -> false
   lessleaves(leaf, cons(W, Z)) -> true
   lessleaves(cons(U, V), cons(W, Z)) -> lessleaves(concat(U, V), concat(W, Z))

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(leaf) -> leaf
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(x_1, x_2)) -> concat(encArg(x_1), encArg(x_2))
   encArg(cons_lessleaves(x_1, x_2)) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_concat(x_1, x_2) -> concat(encArg(x_1), encArg(x_2))
   encode_leaf -> leaf
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_lessleaves(x_1, x_2) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true


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

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

   concat(leaf, Y) -> Y
   concat(cons(U, V), Y) -> cons(U, concat(V, Y))
   lessleaves(X, leaf) -> false
   lessleaves(leaf, cons(W, Z)) -> true
   lessleaves(cons(U, V), cons(W, Z)) -> lessleaves(concat(U, V), concat(W, Z))

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

   encArg(leaf) -> leaf
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(x_1, x_2)) -> concat(encArg(x_1), encArg(x_2))
   encArg(cons_lessleaves(x_1, x_2)) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_concat(x_1, x_2) -> concat(encArg(x_1), encArg(x_2))
   encode_leaf -> leaf
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_lessleaves(x_1, x_2) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true

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:

   concat(leaf, Y) -> Y
   concat(cons(U, V), Y) -> cons(U, concat(V, Y))
   lessleaves(X, leaf) -> false
   lessleaves(leaf, cons(W, Z)) -> true
   lessleaves(cons(U, V), cons(W, Z)) -> lessleaves(concat(U, V), concat(W, Z))

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

   encArg(leaf) -> leaf
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(x_1, x_2)) -> concat(encArg(x_1), encArg(x_2))
   encArg(cons_lessleaves(x_1, x_2)) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_concat(x_1, x_2) -> concat(encArg(x_1), encArg(x_2))
   encode_leaf -> leaf
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_lessleaves(x_1, x_2) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true

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:

   concat(leaf, Y) -> Y
   concat(cons(U, V), Y) -> cons(U, concat(V, Y))
   lessleaves(X, leaf) -> false
   lessleaves(leaf, cons(W, Z)) -> true
   lessleaves(cons(U, V), cons(W, Z)) -> lessleaves(concat(U, V), concat(W, Z))

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

   encArg(leaf) -> leaf
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(x_1, x_2)) -> concat(encArg(x_1), encArg(x_2))
   encArg(cons_lessleaves(x_1, x_2)) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_concat(x_1, x_2) -> concat(encArg(x_1), encArg(x_2))
   encode_leaf -> leaf
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_lessleaves(x_1, x_2) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true

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

(7) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(leaf) -> leaf
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   encode_concat(z0, z1) -> concat(encArg(z0), encArg(z1))
   encode_leaf -> leaf
   encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1))
   encode_lessleaves(z0, z1) -> lessleaves(encArg(z0), encArg(z1))
   encode_false -> false
   encode_true -> true
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   lessleaves(z0, leaf) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
Tuples:
   ENCARG(leaf) -> c
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(false) -> c2
   ENCARG(true) -> c3
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_CONCAT(z0, z1) -> c6(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_LEAF -> c7
   ENCODE_CONS(z0, z1) -> c8(ENCARG(z0), ENCARG(z1))
   ENCODE_LESSLEAVES(z0, z1) -> c9(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_FALSE -> c10
   ENCODE_TRUE -> c11
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
S tuples:
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
K tuples:none
Defined Rule Symbols:   concat_2, lessleaves_2, encArg_1, encode_concat_2, encode_leaf, encode_cons_2, encode_lessleaves_2, encode_false, encode_true

Defined Pair Symbols:   ENCARG_1, ENCODE_CONCAT_2, ENCODE_LEAF, ENCODE_CONS_2, ENCODE_LESSLEAVES_2, ENCODE_FALSE, ENCODE_TRUE, CONCAT_2, LESSLEAVES_2

Compound Symbols:   c, c1_2, c2, c3, c4_3, c5_3, c6_3, c7, c8_2, c9_3, c10, c11, c12, c13_1, c14, c15, c16_3


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

(9) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 1 leading nodes:
   ENCODE_CONS(z0, z1) -> c8(ENCARG(z0), ENCARG(z1))
Removed 6 trailing nodes:
   ENCODE_FALSE -> c10
   ENCARG(false) -> c2
   ENCODE_LEAF -> c7
   ENCODE_TRUE -> c11
   ENCARG(true) -> c3
   ENCARG(leaf) -> c

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

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(leaf) -> leaf
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   encode_concat(z0, z1) -> concat(encArg(z0), encArg(z1))
   encode_leaf -> leaf
   encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1))
   encode_lessleaves(z0, z1) -> lessleaves(encArg(z0), encArg(z1))
   encode_false -> false
   encode_true -> true
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   lessleaves(z0, leaf) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_CONCAT(z0, z1) -> c6(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_LESSLEAVES(z0, z1) -> c9(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
S tuples:
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
K tuples:none
Defined Rule Symbols:   concat_2, lessleaves_2, encArg_1, encode_concat_2, encode_leaf, encode_cons_2, encode_lessleaves_2, encode_false, encode_true

Defined Pair Symbols:   ENCARG_1, ENCODE_CONCAT_2, ENCODE_LESSLEAVES_2, CONCAT_2, LESSLEAVES_2

Compound Symbols:   c1_2, c4_3, c5_3, c6_3, c9_3, c12, c13_1, c14, c15, c16_3


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

(11) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID))
Split RHS of tuples not part of any SCC
----------------------------------------

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(leaf) -> leaf
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   encode_concat(z0, z1) -> concat(encArg(z0), encArg(z1))
   encode_leaf -> leaf
   encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1))
   encode_lessleaves(z0, z1) -> lessleaves(encArg(z0), encArg(z1))
   encode_false -> false
   encode_true -> true
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   lessleaves(z0, leaf) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_CONCAT(z0, z1) -> c(ENCARG(z0))
   ENCODE_CONCAT(z0, z1) -> c(ENCARG(z1))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(ENCARG(z0))
   ENCODE_LESSLEAVES(z0, z1) -> c(ENCARG(z1))
S tuples:
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
K tuples:none
Defined Rule Symbols:   concat_2, lessleaves_2, encArg_1, encode_concat_2, encode_leaf, encode_cons_2, encode_lessleaves_2, encode_false, encode_true

Defined Pair Symbols:   ENCARG_1, CONCAT_2, LESSLEAVES_2, ENCODE_CONCAT_2, ENCODE_LESSLEAVES_2

Compound Symbols:   c1_2, c4_3, c5_3, c12, c13_1, c14, c15, c16_3, c_1


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

(13) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 4 leading nodes:
   ENCODE_CONCAT(z0, z1) -> c(ENCARG(z0))
   ENCODE_CONCAT(z0, z1) -> c(ENCARG(z1))
   ENCODE_LESSLEAVES(z0, z1) -> c(ENCARG(z0))
   ENCODE_LESSLEAVES(z0, z1) -> c(ENCARG(z1))

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

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(leaf) -> leaf
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   encode_concat(z0, z1) -> concat(encArg(z0), encArg(z1))
   encode_leaf -> leaf
   encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1))
   encode_lessleaves(z0, z1) -> lessleaves(encArg(z0), encArg(z1))
   encode_false -> false
   encode_true -> true
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   lessleaves(z0, leaf) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
S tuples:
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
K tuples:none
Defined Rule Symbols:   concat_2, lessleaves_2, encArg_1, encode_concat_2, encode_leaf, encode_cons_2, encode_lessleaves_2, encode_false, encode_true

Defined Pair Symbols:   ENCARG_1, CONCAT_2, LESSLEAVES_2, ENCODE_CONCAT_2, ENCODE_LESSLEAVES_2

Compound Symbols:   c1_2, c4_3, c5_3, c12, c13_1, c14, c15, c16_3, c_1


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

(15) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   encode_concat(z0, z1) -> concat(encArg(z0), encArg(z1))
   encode_leaf -> leaf
   encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1))
   encode_lessleaves(z0, z1) -> lessleaves(encArg(z0), encArg(z1))
   encode_false -> false
   encode_true -> true

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

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(leaf) -> leaf
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   lessleaves(z0, leaf) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
S tuples:
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
K tuples:none
Defined Rule Symbols:   encArg_1, concat_2, lessleaves_2

Defined Pair Symbols:   ENCARG_1, CONCAT_2, LESSLEAVES_2, ENCODE_CONCAT_2, ENCODE_LESSLEAVES_2

Compound Symbols:   c1_2, c4_3, c5_3, c12, c13_1, c14, c15, c16_3, c_1


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

(17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
We considered the (Usable) Rules:none
And the Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(CONCAT(x_1, x_2)) = 0
   POL(ENCARG(x_1)) = x_1
   POL(ENCODE_CONCAT(x_1, x_2)) = 0
   POL(ENCODE_LESSLEAVES(x_1, x_2)) = [1]
   POL(LESSLEAVES(x_1, x_2)) = [1]
   POL(c(x_1)) = x_1
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c12) = 0
   POL(c13(x_1)) = x_1
   POL(c14) = 0
   POL(c15) = 0
   POL(c16(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c4(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c5(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(concat(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_concat(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_lessleaves(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = x_1
   POL(false) = 0
   POL(leaf) = [1]
   POL(lessleaves(x_1, x_2)) = [1] + x_1 + x_2
   POL(true) = [1]

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

(18)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(leaf) -> leaf
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   lessleaves(z0, leaf) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
S tuples:
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
K tuples:
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
Defined Rule Symbols:   encArg_1, concat_2, lessleaves_2

Defined Pair Symbols:   ENCARG_1, CONCAT_2, LESSLEAVES_2, ENCODE_CONCAT_2, ENCODE_LESSLEAVES_2

Compound Symbols:   c1_2, c4_3, c5_3, c12, c13_1, c14, c15, c16_3, c_1


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

(19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   CONCAT(leaf, z0) -> c12
We considered the (Usable) Rules:
   encArg(leaf) -> leaf
   encArg(false) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   encArg(true) -> true
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   lessleaves(z0, leaf) -> false
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
And the Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(CONCAT(x_1, x_2)) = [1]
   POL(ENCARG(x_1)) = x_1^2
   POL(ENCODE_CONCAT(x_1, x_2)) = [2] + [2]x_1 + [2]x_2^2 + x_1*x_2 + [2]x_1^2
   POL(ENCODE_LESSLEAVES(x_1, x_2)) = [1] + [2]x_1 + [2]x_2 + [2]x_2^2 + x_1*x_2 + x_1^2
   POL(LESSLEAVES(x_1, x_2)) = [2]x_2
   POL(c(x_1)) = x_1
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c12) = 0
   POL(c13(x_1)) = x_1
   POL(c14) = 0
   POL(c15) = 0
   POL(c16(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c4(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c5(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(concat(x_1, x_2)) = x_1 + x_2
   POL(cons(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_concat(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_lessleaves(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = x_1
   POL(false) = 0
   POL(leaf) = 0
   POL(lessleaves(x_1, x_2)) = 0
   POL(true) = 0

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

(20)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(leaf) -> leaf
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   lessleaves(z0, leaf) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
S tuples:
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
K tuples:
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   CONCAT(leaf, z0) -> c12
Defined Rule Symbols:   encArg_1, concat_2, lessleaves_2

Defined Pair Symbols:   ENCARG_1, CONCAT_2, LESSLEAVES_2, ENCODE_CONCAT_2, ENCODE_LESSLEAVES_2

Compound Symbols:   c1_2, c4_3, c5_3, c12, c13_1, c14, c15, c16_3, c_1


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

(21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
We considered the (Usable) Rules:
   encArg(leaf) -> leaf
   encArg(false) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   encArg(true) -> true
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   lessleaves(z0, leaf) -> false
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
And the Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(CONCAT(x_1, x_2)) = 0
   POL(ENCARG(x_1)) = x_1^2
   POL(ENCODE_CONCAT(x_1, x_2)) = [1] + [2]x_1 + [2]x_2^2 + [2]x_1*x_2 + x_1^2
   POL(ENCODE_LESSLEAVES(x_1, x_2)) = [2] + [2]x_1 + [2]x_2^2 + x_1*x_2 + [2]x_1^2
   POL(LESSLEAVES(x_1, x_2)) = x_1
   POL(c(x_1)) = x_1
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c12) = 0
   POL(c13(x_1)) = x_1
   POL(c14) = 0
   POL(c15) = 0
   POL(c16(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c4(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c5(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(concat(x_1, x_2)) = x_1 + x_2
   POL(cons(x_1, x_2)) = [2] + x_1 + x_2
   POL(cons_concat(x_1, x_2)) = x_1 + x_2
   POL(cons_lessleaves(x_1, x_2)) = [2] + x_1 + x_2
   POL(encArg(x_1)) = x_1
   POL(false) = 0
   POL(leaf) = 0
   POL(lessleaves(x_1, x_2)) = 0
   POL(true) = 0

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

(22)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(leaf) -> leaf
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   lessleaves(z0, leaf) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
S tuples:
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
K tuples:
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   CONCAT(leaf, z0) -> c12
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
Defined Rule Symbols:   encArg_1, concat_2, lessleaves_2

Defined Pair Symbols:   ENCARG_1, CONCAT_2, LESSLEAVES_2, ENCODE_CONCAT_2, ENCODE_LESSLEAVES_2

Compound Symbols:   c1_2, c4_3, c5_3, c12, c13_1, c14, c15, c16_3, c_1


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

(23) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
We considered the (Usable) Rules:
   encArg(leaf) -> leaf
   encArg(false) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   encArg(true) -> true
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   lessleaves(z0, leaf) -> false
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
And the Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(CONCAT(x_1, x_2)) = x_1
   POL(ENCARG(x_1)) = x_1^2
   POL(ENCODE_CONCAT(x_1, x_2)) = [1] + [2]x_1 + x_2 + x_2^2 + [2]x_1*x_2 + x_1^2
   POL(ENCODE_LESSLEAVES(x_1, x_2)) = [1] + [2]x_1 + x_2 + x_2^2 + [2]x_1*x_2 + [2]x_1^2
   POL(LESSLEAVES(x_1, x_2)) = [2]x_1*x_2
   POL(c(x_1)) = x_1
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c12) = 0
   POL(c13(x_1)) = x_1
   POL(c14) = 0
   POL(c15) = 0
   POL(c16(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c4(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c5(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(concat(x_1, x_2)) = x_1 + x_2
   POL(cons(x_1, x_2)) = [2] + x_1 + x_2
   POL(cons_concat(x_1, x_2)) = [2] + x_1 + x_2
   POL(cons_lessleaves(x_1, x_2)) = x_1 + x_2
   POL(encArg(x_1)) = x_1
   POL(false) = 0
   POL(leaf) = 0
   POL(lessleaves(x_1, x_2)) = 0
   POL(true) = 0

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

(24)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(leaf) -> leaf
   encArg(cons(z0, z1)) -> cons(encArg(z0), encArg(z1))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(z0, z1)) -> concat(encArg(z0), encArg(z1))
   encArg(cons_lessleaves(z0, z1)) -> lessleaves(encArg(z0), encArg(z1))
   concat(leaf, z0) -> z0
   concat(cons(z0, z1), z2) -> cons(z0, concat(z1, z2))
   lessleaves(z0, leaf) -> false
   lessleaves(leaf, cons(z0, z1)) -> true
   lessleaves(cons(z0, z1), cons(z2, z3)) -> lessleaves(concat(z0, z1), concat(z2, z3))
Tuples:
   ENCARG(cons(z0, z1)) -> c1(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_concat(z0, z1)) -> c4(CONCAT(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_lessleaves(z0, z1)) -> c5(LESSLEAVES(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   CONCAT(leaf, z0) -> c12
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   ENCODE_CONCAT(z0, z1) -> c(CONCAT(encArg(z0), encArg(z1)))
   ENCODE_LESSLEAVES(z0, z1) -> c(LESSLEAVES(encArg(z0), encArg(z1)))
S tuples:none
K tuples:
   LESSLEAVES(z0, leaf) -> c14
   LESSLEAVES(leaf, cons(z0, z1)) -> c15
   CONCAT(leaf, z0) -> c12
   LESSLEAVES(cons(z0, z1), cons(z2, z3)) -> c16(LESSLEAVES(concat(z0, z1), concat(z2, z3)), CONCAT(z0, z1), CONCAT(z2, z3))
   CONCAT(cons(z0, z1), z2) -> c13(CONCAT(z1, z2))
Defined Rule Symbols:   encArg_1, concat_2, lessleaves_2

Defined Pair Symbols:   ENCARG_1, CONCAT_2, LESSLEAVES_2, ENCODE_CONCAT_2, ENCODE_LESSLEAVES_2

Compound Symbols:   c1_2, c4_3, c5_3, c12, c13_1, c14, c15, c16_3, c_1


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

(25) SIsEmptyProof (BOTH BOUNDS(ID, ID))
The set S is empty
----------------------------------------

(26)
BOUNDS(1, 1)

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

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

(28)
Obligation:
Analyzing the following TRS for decreasing loops:

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:

   concat(leaf, Y) -> Y
   concat(cons(U, V), Y) -> cons(U, concat(V, Y))
   lessleaves(X, leaf) -> false
   lessleaves(leaf, cons(W, Z)) -> true
   lessleaves(cons(U, V), cons(W, Z)) -> lessleaves(concat(U, V), concat(W, Z))

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

   encArg(leaf) -> leaf
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(x_1, x_2)) -> concat(encArg(x_1), encArg(x_2))
   encArg(cons_lessleaves(x_1, x_2)) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_concat(x_1, x_2) -> concat(encArg(x_1), encArg(x_2))
   encode_leaf -> leaf
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_lessleaves(x_1, x_2) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true

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

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

The rewrite sequence

concat(cons(U, V), Y) ->^+ cons(U, concat(V, Y))

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

The pumping substitution is [V / cons(U, V)].

The result substitution is [ ].




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

(30)
Complex Obligation (BEST)

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

(31)
Obligation:
Proved the lower bound n^1 for the following 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:

   concat(leaf, Y) -> Y
   concat(cons(U, V), Y) -> cons(U, concat(V, Y))
   lessleaves(X, leaf) -> false
   lessleaves(leaf, cons(W, Z)) -> true
   lessleaves(cons(U, V), cons(W, Z)) -> lessleaves(concat(U, V), concat(W, Z))

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

   encArg(leaf) -> leaf
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(x_1, x_2)) -> concat(encArg(x_1), encArg(x_2))
   encArg(cons_lessleaves(x_1, x_2)) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_concat(x_1, x_2) -> concat(encArg(x_1), encArg(x_2))
   encode_leaf -> leaf
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_lessleaves(x_1, x_2) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true

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

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

(33)
BOUNDS(n^1, INF)

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

(34)
Obligation:
Analyzing the following TRS for decreasing loops:

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:

   concat(leaf, Y) -> Y
   concat(cons(U, V), Y) -> cons(U, concat(V, Y))
   lessleaves(X, leaf) -> false
   lessleaves(leaf, cons(W, Z)) -> true
   lessleaves(cons(U, V), cons(W, Z)) -> lessleaves(concat(U, V), concat(W, Z))

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

   encArg(leaf) -> leaf
   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(false) -> false
   encArg(true) -> true
   encArg(cons_concat(x_1, x_2)) -> concat(encArg(x_1), encArg(x_2))
   encArg(cons_lessleaves(x_1, x_2)) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_concat(x_1, x_2) -> concat(encArg(x_1), encArg(x_2))
   encode_leaf -> leaf
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_lessleaves(x_1, x_2) -> lessleaves(encArg(x_1), encArg(x_2))
   encode_false -> false
   encode_true -> true

Rewrite Strategy: FULL