/export/starexec/sandbox2/solver/bin/starexec_run_complexity /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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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)), 119 ms]
    (6) CdtProblem
    (7) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CdtProblem
    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 118 ms]
    (10) CdtProblem
    (11) CdtKnowledgeProof [FINISHED, 0 ms]
    (12) BOUNDS(1, 1)
(13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(14) TRS for Loop Detection
    (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (16) BEST
        (17) proven lower bound
            (18) LowerBoundPropagationProof [FINISHED, 0 ms]
            (19) BOUNDS(n^1, INF)
        (20) TRS for Loop Detection


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

(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) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

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

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

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

The rewrite sequence

subtrees(node(@x1_0, @t12_0, @t23_0)) ->^+ subtrees#2(subtrees(@t12_0), @t12_0, @t23_0, @x1_0)

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

The pumping substitution is [@t12_0 / node(@x1_0, @t12_0, @t23_0)].

The result substitution is [ ].




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

(16)
Complex Obligation (BEST)

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

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

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

(19)
BOUNDS(n^1, INF)

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

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

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