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


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


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


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

(0) CpxTRS
(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
(2) CdtProblem
    (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CdtProblem
    (5) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 99 ms]
    (6) CdtProblem
    (7) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CdtProblem
    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 91 ms]
    (10) CdtProblem
    (11) CdtKnowledgeProof [FINISHED, 0 ms]
    (12) BOUNDS(1, 1)
(13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(14) CpxTRS
    (15) SlicingProof [LOWER BOUND(ID), 0 ms]
    (16) CpxTRS
    (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) typed CpxTrs
    (19) OrderProof [LOWER BOUND(ID), 0 ms]
    (20) typed CpxTrs
    (21) RewriteLemmaProof [LOWER BOUND(ID), 236 ms]
    (22) BEST
        (23) proven lower bound
            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
            (25) BOUNDS(n^1, INF)
        (26) typed CpxTrs
            (27) RewriteLemmaProof [LOWER BOUND(ID), 41 ms]
            (28) typed CpxTrs


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

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


The TRS R consists of the following rules:

   append(@l1, @l2) -> append#1(@l1, @l2)
   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
   append#1(nil, @l2) -> @l2
   subtrees(@t) -> subtrees#1(@t)
   subtrees#1(leaf) -> nil
   subtrees#1(node(@x, @t1, @t2)) -> subtrees#2(subtrees(@t1), @t1, @t2, @x)
   subtrees#2(@l1, @t1, @t2, @x) -> subtrees#3(subtrees(@t2), @l1, @t1, @t2, @x)
   subtrees#3(@l2, @l1, @t1, @t2, @x) -> ::(node(@x, @t1, @t2), append(@l1, @l2))

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

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

(2)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   append(z0, z1) -> append#1(z0, z1)
   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
   append#1(nil, z0) -> z0
   subtrees(z0) -> subtrees#1(z0)
   subtrees#1(leaf) -> nil
   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
Tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   APPEND#1(nil, z0) -> c2
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(leaf) -> c4
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
S tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   APPEND#1(nil, z0) -> c2
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(leaf) -> c4
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
K tuples:none
Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5

Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5

Compound Symbols:   c_1, c1_1, c2, c3_1, c4, c5_2, c6_2, c7_1


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

(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 2 trailing nodes:
   APPEND#1(nil, z0) -> c2
   SUBTREES#1(leaf) -> c4

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

(4)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   append(z0, z1) -> append#1(z0, z1)
   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
   append#1(nil, z0) -> z0
   subtrees(z0) -> subtrees#1(z0)
   subtrees#1(leaf) -> nil
   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
Tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
S tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
K tuples:none
Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5

Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5

Compound Symbols:   c_1, c1_1, c3_1, c5_2, c6_2, c7_1


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

(5) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
We considered the (Usable) Rules:
   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
   append(z0, z1) -> append#1(z0, z1)
   append#1(nil, z0) -> z0
   subtrees(z0) -> subtrees#1(z0)
   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
   subtrees#1(leaf) -> nil
   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
And the Tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(::(x_1, x_2)) = x_2
   POL(APPEND(x_1, x_2)) = x_1 + x_2
   POL(APPEND#1(x_1, x_2)) = x_1 + x_2
   POL(SUBTREES(x_1)) = x_1
   POL(SUBTREES#1(x_1)) = x_1
   POL(SUBTREES#2(x_1, x_2, x_3, x_4)) = x_1 + x_3 + x_4
   POL(SUBTREES#3(x_1, x_2, x_3, x_4, x_5)) = x_1 + x_2 + x_5
   POL(append(x_1, x_2)) = x_1 + x_2
   POL(append#1(x_1, x_2)) = x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c1(x_1)) = x_1
   POL(c3(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2)) = x_1 + x_2
   POL(c7(x_1)) = x_1
   POL(leaf) = [1]
   POL(nil) = 0
   POL(node(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(subtrees(x_1)) = 0
   POL(subtrees#1(x_1)) = 0
   POL(subtrees#2(x_1, x_2, x_3, x_4)) = x_1
   POL(subtrees#3(x_1, x_2, x_3, x_4, x_5)) = x_1 + x_2

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

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   append(z0, z1) -> append#1(z0, z1)
   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
   append#1(nil, z0) -> z0
   subtrees(z0) -> subtrees#1(z0)
   subtrees#1(leaf) -> nil
   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
Tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
S tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
K tuples:
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5

Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5

Compound Symbols:   c_1, c1_1, c3_1, c5_2, c6_2, c7_1


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

(7) CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
The following tuples could be moved from S to K by knowledge propagation:
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))

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

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   append(z0, z1) -> append#1(z0, z1)
   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
   append#1(nil, z0) -> z0
   subtrees(z0) -> subtrees#1(z0)
   subtrees#1(leaf) -> nil
   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
Tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
S tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
K tuples:
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5

Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5

Compound Symbols:   c_1, c1_1, c3_1, c5_2, c6_2, c7_1


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

(9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
We considered the (Usable) Rules:
   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
   append(z0, z1) -> append#1(z0, z1)
   append#1(nil, z0) -> z0
   subtrees(z0) -> subtrees#1(z0)
   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
   subtrees#1(leaf) -> nil
   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
And the Tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(::(x_1, x_2)) = [2] + x_2
   POL(APPEND(x_1, x_2)) = [2]x_1
   POL(APPEND#1(x_1, x_2)) = [2]x_1
   POL(SUBTREES(x_1)) = x_1^2
   POL(SUBTREES#1(x_1)) = x_1^2
   POL(SUBTREES#2(x_1, x_2, x_3, x_4)) = [2]x_1 + x_3^2 + [2]x_2*x_3
   POL(SUBTREES#3(x_1, x_2, x_3, x_4, x_5)) = [2]x_2 + x_3*x_4
   POL(append(x_1, x_2)) = x_1 + x_2
   POL(append#1(x_1, x_2)) = x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c1(x_1)) = x_1
   POL(c3(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2)) = x_1 + x_2
   POL(c7(x_1)) = x_1
   POL(leaf) = 0
   POL(nil) = 0
   POL(node(x_1, x_2, x_3)) = [2] + x_2 + x_3
   POL(subtrees(x_1)) = [2]x_1
   POL(subtrees#1(x_1)) = [2]x_1
   POL(subtrees#2(x_1, x_2, x_3, x_4)) = [2] + x_1 + [2]x_3
   POL(subtrees#3(x_1, x_2, x_3, x_4, x_5)) = [2] + x_1 + x_2

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

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   append(z0, z1) -> append#1(z0, z1)
   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
   append#1(nil, z0) -> z0
   subtrees(z0) -> subtrees#1(z0)
   subtrees#1(leaf) -> nil
   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
Tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
S tuples:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
K tuples:
   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
   SUBTREES(z0) -> c3(SUBTREES#1(z0))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5

Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5

Compound Symbols:   c_1, c1_1, c3_1, c5_2, c6_2, c7_1


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

(11) CdtKnowledgeProof (FINISHED)
The following tuples could be moved from S to K by knowledge propagation:
   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
Now S is empty
----------------------------------------

(12)
BOUNDS(1, 1)

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

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

(14)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   append(@l1, @l2) -> append#1(@l1, @l2)
   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
   append#1(nil, @l2) -> @l2
   subtrees(@t) -> subtrees#1(@t)
   subtrees#1(leaf) -> nil
   subtrees#1(node(@x, @t1, @t2)) -> subtrees#2(subtrees(@t1), @t1, @t2, @x)
   subtrees#2(@l1, @t1, @t2, @x) -> subtrees#3(subtrees(@t2), @l1, @t1, @t2, @x)
   subtrees#3(@l2, @l1, @t1, @t2, @x) -> ::(node(@x, @t1, @t2), append(@l1, @l2))

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

(15) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
::/0
node/0
subtrees#2/1
subtrees#2/3
subtrees#3/2
subtrees#3/3
subtrees#3/4

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

(16)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   append(@l1, @l2) -> append#1(@l1, @l2)
   append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
   append#1(nil, @l2) -> @l2
   subtrees(@t) -> subtrees#1(@t)
   subtrees#1(leaf) -> nil
   subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
   subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
   subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))

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

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

(18)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
append#1(nil, @l2) -> @l2
subtrees(@t) -> subtrees#1(@t)
subtrees#1(leaf) -> nil
subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil
nil :: :::nil
subtrees :: leaf:node -> :::nil
subtrees#1 :: leaf:node -> :::nil
leaf :: leaf:node
node :: leaf:node -> leaf:node -> leaf:node
subtrees#2 :: :::nil -> leaf:node -> :::nil
subtrees#3 :: :::nil -> :::nil -> :::nil
hole_:::nil1_0 :: :::nil
hole_leaf:node2_0 :: leaf:node
gen_:::nil3_0 :: Nat -> :::nil
gen_leaf:node4_0 :: Nat -> leaf:node

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

(19) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
append, append#1, subtrees, subtrees#1

They will be analysed ascendingly in the following order:
append = append#1
subtrees = subtrees#1

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

(20)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
append#1(nil, @l2) -> @l2
subtrees(@t) -> subtrees#1(@t)
subtrees#1(leaf) -> nil
subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil
nil :: :::nil
subtrees :: leaf:node -> :::nil
subtrees#1 :: leaf:node -> :::nil
leaf :: leaf:node
node :: leaf:node -> leaf:node -> leaf:node
subtrees#2 :: :::nil -> leaf:node -> :::nil
subtrees#3 :: :::nil -> :::nil -> :::nil
hole_:::nil1_0 :: :::nil
hole_leaf:node2_0 :: leaf:node
gen_:::nil3_0 :: Nat -> :::nil
gen_leaf:node4_0 :: Nat -> leaf:node


Generator Equations:
gen_:::nil3_0(0) <=> nil
gen_:::nil3_0(+(x, 1)) <=> ::(gen_:::nil3_0(x))
gen_leaf:node4_0(0) <=> leaf
gen_leaf:node4_0(+(x, 1)) <=> node(leaf, gen_leaf:node4_0(x))


The following defined symbols remain to be analysed:
subtrees#1, append, append#1, subtrees

They will be analysed ascendingly in the following order:
append = append#1
subtrees = subtrees#1

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

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
subtrees#1(gen_leaf:node4_0(n6_0)) -> gen_:::nil3_0(n6_0), rt in Omega(1 + n6_0)

Induction Base:
subtrees#1(gen_leaf:node4_0(0)) ->_R^Omega(1)
nil

Induction Step:
subtrees#1(gen_leaf:node4_0(+(n6_0, 1))) ->_R^Omega(1)
subtrees#2(subtrees(leaf), gen_leaf:node4_0(n6_0)) ->_R^Omega(1)
subtrees#2(subtrees#1(leaf), gen_leaf:node4_0(n6_0)) ->_R^Omega(1)
subtrees#2(nil, gen_leaf:node4_0(n6_0)) ->_R^Omega(1)
subtrees#3(subtrees(gen_leaf:node4_0(n6_0)), nil) ->_R^Omega(1)
subtrees#3(subtrees#1(gen_leaf:node4_0(n6_0)), nil) ->_IH
subtrees#3(gen_:::nil3_0(c7_0), nil) ->_R^Omega(1)
::(append(nil, gen_:::nil3_0(n6_0))) ->_R^Omega(1)
::(append#1(nil, gen_:::nil3_0(n6_0))) ->_R^Omega(1)
::(gen_:::nil3_0(n6_0))

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

(22)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
append#1(nil, @l2) -> @l2
subtrees(@t) -> subtrees#1(@t)
subtrees#1(leaf) -> nil
subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil
nil :: :::nil
subtrees :: leaf:node -> :::nil
subtrees#1 :: leaf:node -> :::nil
leaf :: leaf:node
node :: leaf:node -> leaf:node -> leaf:node
subtrees#2 :: :::nil -> leaf:node -> :::nil
subtrees#3 :: :::nil -> :::nil -> :::nil
hole_:::nil1_0 :: :::nil
hole_leaf:node2_0 :: leaf:node
gen_:::nil3_0 :: Nat -> :::nil
gen_leaf:node4_0 :: Nat -> leaf:node


Generator Equations:
gen_:::nil3_0(0) <=> nil
gen_:::nil3_0(+(x, 1)) <=> ::(gen_:::nil3_0(x))
gen_leaf:node4_0(0) <=> leaf
gen_leaf:node4_0(+(x, 1)) <=> node(leaf, gen_leaf:node4_0(x))


The following defined symbols remain to be analysed:
subtrees#1, append, append#1, subtrees

They will be analysed ascendingly in the following order:
append = append#1
subtrees = subtrees#1

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

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

(25)
BOUNDS(n^1, INF)

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

(26)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
append#1(nil, @l2) -> @l2
subtrees(@t) -> subtrees#1(@t)
subtrees#1(leaf) -> nil
subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil
nil :: :::nil
subtrees :: leaf:node -> :::nil
subtrees#1 :: leaf:node -> :::nil
leaf :: leaf:node
node :: leaf:node -> leaf:node -> leaf:node
subtrees#2 :: :::nil -> leaf:node -> :::nil
subtrees#3 :: :::nil -> :::nil -> :::nil
hole_:::nil1_0 :: :::nil
hole_leaf:node2_0 :: leaf:node
gen_:::nil3_0 :: Nat -> :::nil
gen_leaf:node4_0 :: Nat -> leaf:node


Lemmas:
subtrees#1(gen_leaf:node4_0(n6_0)) -> gen_:::nil3_0(n6_0), rt in Omega(1 + n6_0)


Generator Equations:
gen_:::nil3_0(0) <=> nil
gen_:::nil3_0(+(x, 1)) <=> ::(gen_:::nil3_0(x))
gen_leaf:node4_0(0) <=> leaf
gen_leaf:node4_0(+(x, 1)) <=> node(leaf, gen_leaf:node4_0(x))


The following defined symbols remain to be analysed:
subtrees, append, append#1

They will be analysed ascendingly in the following order:
append = append#1
subtrees = subtrees#1

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

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
append#1(gen_:::nil3_0(n383_0), gen_:::nil3_0(b)) -> gen_:::nil3_0(+(n383_0, b)), rt in Omega(1 + n383_0)

Induction Base:
append#1(gen_:::nil3_0(0), gen_:::nil3_0(b)) ->_R^Omega(1)
gen_:::nil3_0(b)

Induction Step:
append#1(gen_:::nil3_0(+(n383_0, 1)), gen_:::nil3_0(b)) ->_R^Omega(1)
::(append(gen_:::nil3_0(n383_0), gen_:::nil3_0(b))) ->_R^Omega(1)
::(append#1(gen_:::nil3_0(n383_0), gen_:::nil3_0(b))) ->_IH
::(gen_:::nil3_0(+(b, c384_0)))

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

(28)
Obligation:
Innermost TRS:
Rules:
append(@l1, @l2) -> append#1(@l1, @l2)
append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
append#1(nil, @l2) -> @l2
subtrees(@t) -> subtrees#1(@t)
subtrees#1(leaf) -> nil
subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))

Types:
append :: :::nil -> :::nil -> :::nil
append#1 :: :::nil -> :::nil -> :::nil
:: :: :::nil -> :::nil
nil :: :::nil
subtrees :: leaf:node -> :::nil
subtrees#1 :: leaf:node -> :::nil
leaf :: leaf:node
node :: leaf:node -> leaf:node -> leaf:node
subtrees#2 :: :::nil -> leaf:node -> :::nil
subtrees#3 :: :::nil -> :::nil -> :::nil
hole_:::nil1_0 :: :::nil
hole_leaf:node2_0 :: leaf:node
gen_:::nil3_0 :: Nat -> :::nil
gen_leaf:node4_0 :: Nat -> leaf:node


Lemmas:
subtrees#1(gen_leaf:node4_0(n6_0)) -> gen_:::nil3_0(n6_0), rt in Omega(1 + n6_0)
append#1(gen_:::nil3_0(n383_0), gen_:::nil3_0(b)) -> gen_:::nil3_0(+(n383_0, b)), rt in Omega(1 + n383_0)


Generator Equations:
gen_:::nil3_0(0) <=> nil
gen_:::nil3_0(+(x, 1)) <=> ::(gen_:::nil3_0(x))
gen_leaf:node4_0(0) <=> leaf
gen_leaf:node4_0(+(x, 1)) <=> node(leaf, gen_leaf:node4_0(x))


The following defined symbols remain to be analysed:
append

They will be analysed ascendingly in the following order:
append = append#1