311.45/291.49	WORST_CASE(Omega(n^1), O(n^2))
311.45/291.51	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
311.45/291.51	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
311.45/291.51	
311.45/291.51	
311.45/291.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
311.45/291.51	
311.45/291.51	(0) CpxTRS
311.45/291.51	(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
311.45/291.51	(2) CdtProblem
311.45/291.51	    (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
311.45/291.51	    (4) CdtProblem
311.45/291.51	    (5) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 120 ms]
311.45/291.51	    (6) CdtProblem
311.45/291.51	    (7) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
311.45/291.51	    (8) CdtProblem
311.45/291.51	    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 106 ms]
311.45/291.51	    (10) CdtProblem
311.45/291.51	    (11) CdtKnowledgeProof [FINISHED, 0 ms]
311.45/291.51	    (12) BOUNDS(1, 1)
311.45/291.51	(13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
311.45/291.51	(14) CpxTRS
311.45/291.51	    (15) SlicingProof [LOWER BOUND(ID), 0 ms]
311.45/291.51	    (16) CpxTRS
311.45/291.51	    (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
311.45/291.51	    (18) typed CpxTrs
311.45/291.51	    (19) OrderProof [LOWER BOUND(ID), 0 ms]
311.45/291.51	    (20) typed CpxTrs
311.45/291.51	    (21) RewriteLemmaProof [LOWER BOUND(ID), 249 ms]
311.45/291.51	    (22) BEST
311.45/291.51	        (23) proven lower bound
311.45/291.51	            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
311.45/291.51	            (25) BOUNDS(n^1, INF)
311.45/291.51	        (26) typed CpxTrs
311.45/291.51	            (27) RewriteLemmaProof [LOWER BOUND(ID), 13 ms]
311.45/291.51	            (28) typed CpxTrs
311.45/291.51	
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(0)
311.45/291.51	Obligation:
311.45/291.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
311.45/291.51	
311.45/291.51	
311.45/291.51	The TRS R consists of the following rules:
311.45/291.51	
311.45/291.51	   append(@l1, @l2) -> append#1(@l1, @l2)
311.45/291.51	   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
311.45/291.51	   append#1(nil, @l2) -> @l2
311.45/291.51	   subtrees(@t) -> subtrees#1(@t)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   subtrees#1(node(@x, @t1, @t2)) -> subtrees#2(subtrees(@t1), @t1, @t2, @x)
311.45/291.51	   subtrees#2(@l1, @t1, @t2, @x) -> subtrees#3(subtrees(@t2), @l1, @t1, @t2, @x)
311.45/291.51	   subtrees#3(@l2, @l1, @t1, @t2, @x) -> ::(node(@x, @t1, @t2), append(@l1, @l2))
311.45/291.51	
311.45/291.51	S is empty.
311.45/291.51	Rewrite Strategy: INNERMOST
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(1) CpxTrsToCdtProof (UPPER BOUND(ID))
311.45/291.51	Converted Cpx (relative) TRS to CDT
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(2)
311.45/291.51	Obligation:
311.45/291.51	Complexity Dependency Tuples Problem
311.45/291.51	
311.45/291.51	Rules:
311.45/291.51	   append(z0, z1) -> append#1(z0, z1)
311.45/291.51	   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
311.45/291.51	   append#1(nil, z0) -> z0
311.45/291.51	   subtrees(z0) -> subtrees#1(z0)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
311.45/291.51	   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
311.45/291.51	   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
311.45/291.51	Tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   APPEND#1(nil, z0) -> c2
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(leaf) -> c4
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	S tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   APPEND#1(nil, z0) -> c2
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(leaf) -> c4
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	K tuples:none
311.45/291.51	Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5
311.45/291.51	
311.45/291.51	Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5
311.45/291.51	
311.45/291.51	Compound Symbols:   c_1, c1_1, c2, c3_1, c4, c5_2, c6_2, c7_1
311.45/291.51	
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
311.45/291.51	Removed 2 trailing nodes:
311.45/291.51	   APPEND#1(nil, z0) -> c2
311.45/291.51	   SUBTREES#1(leaf) -> c4
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(4)
311.45/291.51	Obligation:
311.45/291.51	Complexity Dependency Tuples Problem
311.45/291.51	
311.45/291.51	Rules:
311.45/291.51	   append(z0, z1) -> append#1(z0, z1)
311.45/291.51	   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
311.45/291.51	   append#1(nil, z0) -> z0
311.45/291.51	   subtrees(z0) -> subtrees#1(z0)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
311.45/291.51	   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
311.45/291.51	   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
311.45/291.51	Tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	S tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	K tuples:none
311.45/291.51	Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5
311.45/291.51	
311.45/291.51	Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5
311.45/291.51	
311.45/291.51	Compound Symbols:   c_1, c1_1, c3_1, c5_2, c6_2, c7_1
311.45/291.51	
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(5) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
311.45/291.51	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	We considered the (Usable) Rules:
311.45/291.51	   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
311.45/291.51	   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
311.45/291.51	   append(z0, z1) -> append#1(z0, z1)
311.45/291.51	   append#1(nil, z0) -> z0
311.45/291.51	   subtrees(z0) -> subtrees#1(z0)
311.45/291.51	   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
311.45/291.51	And the Tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	The order we found is given by the following interpretation:
311.45/291.51	
311.45/291.51	Polynomial interpretation :
311.45/291.51	
311.45/291.51	   POL(::(x_1, x_2)) = x_2
311.45/291.51	   POL(APPEND(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(APPEND#1(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(SUBTREES(x_1)) = x_1
311.45/291.51	   POL(SUBTREES#1(x_1)) = x_1
311.45/291.51	   POL(SUBTREES#2(x_1, x_2, x_3, x_4)) = x_1 + x_3 + x_4
311.45/291.51	   POL(SUBTREES#3(x_1, x_2, x_3, x_4, x_5)) = x_1 + x_2 + x_5
311.45/291.51	   POL(append(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(append#1(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(c(x_1)) = x_1
311.45/291.51	   POL(c1(x_1)) = x_1
311.45/291.51	   POL(c3(x_1)) = x_1
311.45/291.51	   POL(c5(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(c6(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(c7(x_1)) = x_1
311.45/291.51	   POL(leaf) = [1]
311.45/291.51	   POL(nil) = 0
311.45/291.51	   POL(node(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
311.45/291.51	   POL(subtrees(x_1)) = 0
311.45/291.51	   POL(subtrees#1(x_1)) = 0
311.45/291.51	   POL(subtrees#2(x_1, x_2, x_3, x_4)) = x_1
311.45/291.51	   POL(subtrees#3(x_1, x_2, x_3, x_4, x_5)) = x_1 + x_2
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(6)
311.45/291.51	Obligation:
311.45/291.51	Complexity Dependency Tuples Problem
311.45/291.51	
311.45/291.51	Rules:
311.45/291.51	   append(z0, z1) -> append#1(z0, z1)
311.45/291.51	   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
311.45/291.51	   append#1(nil, z0) -> z0
311.45/291.51	   subtrees(z0) -> subtrees#1(z0)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
311.45/291.51	   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
311.45/291.51	   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
311.45/291.51	Tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	S tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	K tuples:
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5
311.45/291.51	
311.45/291.51	Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5
311.45/291.51	
311.45/291.51	Compound Symbols:   c_1, c1_1, c3_1, c5_2, c6_2, c7_1
311.45/291.51	
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(7) CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
311.45/291.51	The following tuples could be moved from S to K by knowledge propagation:
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(8)
311.45/291.51	Obligation:
311.45/291.51	Complexity Dependency Tuples Problem
311.45/291.51	
311.45/291.51	Rules:
311.45/291.51	   append(z0, z1) -> append#1(z0, z1)
311.45/291.51	   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
311.45/291.51	   append#1(nil, z0) -> z0
311.45/291.51	   subtrees(z0) -> subtrees#1(z0)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
311.45/291.51	   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
311.45/291.51	   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
311.45/291.51	Tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	S tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	K tuples:
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5
311.45/291.51	
311.45/291.51	Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5
311.45/291.51	
311.45/291.51	Compound Symbols:   c_1, c1_1, c3_1, c5_2, c6_2, c7_1
311.45/291.51	
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
311.45/291.51	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	We considered the (Usable) Rules:
311.45/291.51	   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
311.45/291.51	   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
311.45/291.51	   append(z0, z1) -> append#1(z0, z1)
311.45/291.51	   append#1(nil, z0) -> z0
311.45/291.51	   subtrees(z0) -> subtrees#1(z0)
311.45/291.51	   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
311.45/291.51	And the Tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	The order we found is given by the following interpretation:
311.45/291.51	
311.45/291.51	Polynomial interpretation :
311.45/291.51	
311.45/291.51	   POL(::(x_1, x_2)) = [2] + x_2
311.45/291.51	   POL(APPEND(x_1, x_2)) = [2]x_1
311.45/291.51	   POL(APPEND#1(x_1, x_2)) = [2]x_1
311.45/291.51	   POL(SUBTREES(x_1)) = x_1^2
311.45/291.51	   POL(SUBTREES#1(x_1)) = x_1^2
311.45/291.51	   POL(SUBTREES#2(x_1, x_2, x_3, x_4)) = [2]x_1 + x_3^2 + [2]x_2*x_3
311.45/291.51	   POL(SUBTREES#3(x_1, x_2, x_3, x_4, x_5)) = [2]x_2 + x_3*x_4
311.45/291.51	   POL(append(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(append#1(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(c(x_1)) = x_1
311.45/291.51	   POL(c1(x_1)) = x_1
311.45/291.51	   POL(c3(x_1)) = x_1
311.45/291.51	   POL(c5(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(c6(x_1, x_2)) = x_1 + x_2
311.45/291.51	   POL(c7(x_1)) = x_1
311.45/291.51	   POL(leaf) = 0
311.45/291.51	   POL(nil) = 0
311.45/291.51	   POL(node(x_1, x_2, x_3)) = [2] + x_2 + x_3
311.45/291.51	   POL(subtrees(x_1)) = [2]x_1
311.45/291.51	   POL(subtrees#1(x_1)) = [2]x_1
311.45/291.51	   POL(subtrees#2(x_1, x_2, x_3, x_4)) = [2] + x_1 + [2]x_3
311.45/291.51	   POL(subtrees#3(x_1, x_2, x_3, x_4, x_5)) = [2] + x_1 + x_2
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(10)
311.45/291.51	Obligation:
311.45/291.51	Complexity Dependency Tuples Problem
311.45/291.51	
311.45/291.51	Rules:
311.45/291.51	   append(z0, z1) -> append#1(z0, z1)
311.45/291.51	   append#1(::(z0, z1), z2) -> ::(z0, append(z1, z2))
311.45/291.51	   append#1(nil, z0) -> z0
311.45/291.51	   subtrees(z0) -> subtrees#1(z0)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   subtrees#1(node(z0, z1, z2)) -> subtrees#2(subtrees(z1), z1, z2, z0)
311.45/291.51	   subtrees#2(z0, z1, z2, z3) -> subtrees#3(subtrees(z2), z0, z1, z2, z3)
311.45/291.51	   subtrees#3(z0, z1, z2, z3, z4) -> ::(node(z4, z2, z3), append(z1, z0))
311.45/291.51	Tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	S tuples:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	K tuples:
311.45/291.51	   SUBTREES#1(node(z0, z1, z2)) -> c5(SUBTREES#2(subtrees(z1), z1, z2, z0), SUBTREES(z1))
311.45/291.51	   SUBTREES#2(z0, z1, z2, z3) -> c6(SUBTREES#3(subtrees(z2), z0, z1, z2, z3), SUBTREES(z2))
311.45/291.51	   SUBTREES#3(z0, z1, z2, z3, z4) -> c7(APPEND(z1, z0))
311.45/291.51	   SUBTREES(z0) -> c3(SUBTREES#1(z0))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	Defined Rule Symbols:   append_2, append#1_2, subtrees_1, subtrees#1_1, subtrees#2_4, subtrees#3_5
311.45/291.51	
311.45/291.51	Defined Pair Symbols:   APPEND_2, APPEND#1_2, SUBTREES_1, SUBTREES#1_1, SUBTREES#2_4, SUBTREES#3_5
311.45/291.51	
311.45/291.51	Compound Symbols:   c_1, c1_1, c3_1, c5_2, c6_2, c7_1
311.45/291.51	
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(11) CdtKnowledgeProof (FINISHED)
311.45/291.51	The following tuples could be moved from S to K by knowledge propagation:
311.45/291.51	   APPEND(z0, z1) -> c(APPEND#1(z0, z1))
311.45/291.51	   APPEND#1(::(z0, z1), z2) -> c1(APPEND(z1, z2))
311.45/291.51	Now S is empty
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(12)
311.45/291.51	BOUNDS(1, 1)
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(13) RenamingProof (BOTH BOUNDS(ID, ID))
311.45/291.51	Renamed function symbols to avoid clashes with predefined symbol.
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(14)
311.45/291.51	Obligation:
311.45/291.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
311.45/291.51	
311.45/291.51	
311.45/291.51	The TRS R consists of the following rules:
311.45/291.51	
311.45/291.51	   append(@l1, @l2) -> append#1(@l1, @l2)
311.45/291.51	   append#1(::(@x, @xs), @l2) -> ::(@x, append(@xs, @l2))
311.45/291.51	   append#1(nil, @l2) -> @l2
311.45/291.51	   subtrees(@t) -> subtrees#1(@t)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   subtrees#1(node(@x, @t1, @t2)) -> subtrees#2(subtrees(@t1), @t1, @t2, @x)
311.45/291.51	   subtrees#2(@l1, @t1, @t2, @x) -> subtrees#3(subtrees(@t2), @l1, @t1, @t2, @x)
311.45/291.51	   subtrees#3(@l2, @l1, @t1, @t2, @x) -> ::(node(@x, @t1, @t2), append(@l1, @l2))
311.45/291.51	
311.45/291.51	S is empty.
311.45/291.51	Rewrite Strategy: INNERMOST
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(15) SlicingProof (LOWER BOUND(ID))
311.45/291.51	Sliced the following arguments:
311.45/291.51	::/0
311.45/291.51	node/0
311.45/291.51	subtrees#2/1
311.45/291.51	subtrees#2/3
311.45/291.51	subtrees#3/2
311.45/291.51	subtrees#3/3
311.45/291.51	subtrees#3/4
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(16)
311.45/291.51	Obligation:
311.45/291.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
311.45/291.51	
311.45/291.51	
311.45/291.51	The TRS R consists of the following rules:
311.45/291.51	
311.45/291.51	   append(@l1, @l2) -> append#1(@l1, @l2)
311.45/291.51	   append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
311.45/291.51	   append#1(nil, @l2) -> @l2
311.45/291.51	   subtrees(@t) -> subtrees#1(@t)
311.45/291.51	   subtrees#1(leaf) -> nil
311.45/291.51	   subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
311.45/291.51	   subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
311.45/291.51	   subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))
311.45/291.51	
311.45/291.51	S is empty.
311.45/291.51	Rewrite Strategy: INNERMOST
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(17) TypeInferenceProof (BOTH BOUNDS(ID, ID))
311.45/291.51	Infered types.
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(18)
311.45/291.51	Obligation:
311.45/291.51	Innermost TRS:
311.45/291.51	Rules:
311.45/291.51	append(@l1, @l2) -> append#1(@l1, @l2)
311.45/291.51	append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
311.45/291.51	append#1(nil, @l2) -> @l2
311.45/291.51	subtrees(@t) -> subtrees#1(@t)
311.45/291.51	subtrees#1(leaf) -> nil
311.45/291.51	subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
311.45/291.51	subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
311.45/291.51	subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))
311.45/291.51	
311.45/291.51	Types:
311.45/291.51	append :: :::nil -> :::nil -> :::nil
311.45/291.51	append#1 :: :::nil -> :::nil -> :::nil
311.45/291.51	:: :: :::nil -> :::nil
311.45/291.51	nil :: :::nil
311.45/291.51	subtrees :: leaf:node -> :::nil
311.45/291.51	subtrees#1 :: leaf:node -> :::nil
311.45/291.51	leaf :: leaf:node
311.45/291.51	node :: leaf:node -> leaf:node -> leaf:node
311.45/291.51	subtrees#2 :: :::nil -> leaf:node -> :::nil
311.45/291.51	subtrees#3 :: :::nil -> :::nil -> :::nil
311.45/291.51	hole_:::nil1_0 :: :::nil
311.45/291.51	hole_leaf:node2_0 :: leaf:node
311.45/291.51	gen_:::nil3_0 :: Nat -> :::nil
311.45/291.51	gen_leaf:node4_0 :: Nat -> leaf:node
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(19) OrderProof (LOWER BOUND(ID))
311.45/291.51	Heuristically decided to analyse the following defined symbols:
311.45/291.51	append, append#1, subtrees, subtrees#1
311.45/291.51	
311.45/291.51	They will be analysed ascendingly in the following order:
311.45/291.51	append = append#1
311.45/291.51	subtrees = subtrees#1
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(20)
311.45/291.51	Obligation:
311.45/291.51	Innermost TRS:
311.45/291.51	Rules:
311.45/291.51	append(@l1, @l2) -> append#1(@l1, @l2)
311.45/291.51	append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
311.45/291.51	append#1(nil, @l2) -> @l2
311.45/291.51	subtrees(@t) -> subtrees#1(@t)
311.45/291.51	subtrees#1(leaf) -> nil
311.45/291.51	subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
311.45/291.51	subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
311.45/291.51	subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))
311.45/291.51	
311.45/291.51	Types:
311.45/291.51	append :: :::nil -> :::nil -> :::nil
311.45/291.51	append#1 :: :::nil -> :::nil -> :::nil
311.45/291.51	:: :: :::nil -> :::nil
311.45/291.51	nil :: :::nil
311.45/291.51	subtrees :: leaf:node -> :::nil
311.45/291.51	subtrees#1 :: leaf:node -> :::nil
311.45/291.51	leaf :: leaf:node
311.45/291.51	node :: leaf:node -> leaf:node -> leaf:node
311.45/291.51	subtrees#2 :: :::nil -> leaf:node -> :::nil
311.45/291.51	subtrees#3 :: :::nil -> :::nil -> :::nil
311.45/291.51	hole_:::nil1_0 :: :::nil
311.45/291.51	hole_leaf:node2_0 :: leaf:node
311.45/291.51	gen_:::nil3_0 :: Nat -> :::nil
311.45/291.51	gen_leaf:node4_0 :: Nat -> leaf:node
311.45/291.51	
311.45/291.51	
311.45/291.51	Generator Equations:
311.45/291.51	gen_:::nil3_0(0) <=> nil
311.45/291.51	gen_:::nil3_0(+(x, 1)) <=> ::(gen_:::nil3_0(x))
311.45/291.51	gen_leaf:node4_0(0) <=> leaf
311.45/291.51	gen_leaf:node4_0(+(x, 1)) <=> node(leaf, gen_leaf:node4_0(x))
311.45/291.51	
311.45/291.51	
311.45/291.51	The following defined symbols remain to be analysed:
311.45/291.51	subtrees#1, append, append#1, subtrees
311.45/291.51	
311.45/291.51	They will be analysed ascendingly in the following order:
311.45/291.51	append = append#1
311.45/291.51	subtrees = subtrees#1
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(21) RewriteLemmaProof (LOWER BOUND(ID))
311.45/291.51	Proved the following rewrite lemma:
311.45/291.51	subtrees#1(gen_leaf:node4_0(n6_0)) -> gen_:::nil3_0(n6_0), rt in Omega(1 + n6_0)
311.45/291.51	
311.45/291.51	Induction Base:
311.45/291.51	subtrees#1(gen_leaf:node4_0(0)) ->_R^Omega(1)
311.45/291.51	nil
311.45/291.51	
311.45/291.51	Induction Step:
311.45/291.51	subtrees#1(gen_leaf:node4_0(+(n6_0, 1))) ->_R^Omega(1)
311.45/291.51	subtrees#2(subtrees(leaf), gen_leaf:node4_0(n6_0)) ->_R^Omega(1)
311.45/291.51	subtrees#2(subtrees#1(leaf), gen_leaf:node4_0(n6_0)) ->_R^Omega(1)
311.45/291.51	subtrees#2(nil, gen_leaf:node4_0(n6_0)) ->_R^Omega(1)
311.45/291.51	subtrees#3(subtrees(gen_leaf:node4_0(n6_0)), nil) ->_R^Omega(1)
311.45/291.51	subtrees#3(subtrees#1(gen_leaf:node4_0(n6_0)), nil) ->_IH
311.45/291.51	subtrees#3(gen_:::nil3_0(c7_0), nil) ->_R^Omega(1)
311.45/291.51	::(append(nil, gen_:::nil3_0(n6_0))) ->_R^Omega(1)
311.45/291.51	::(append#1(nil, gen_:::nil3_0(n6_0))) ->_R^Omega(1)
311.45/291.51	::(gen_:::nil3_0(n6_0))
311.45/291.51	
311.45/291.51	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(22)
311.45/291.51	Complex Obligation (BEST)
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(23)
311.45/291.51	Obligation:
311.45/291.51	Proved the lower bound n^1 for the following obligation:
311.45/291.51	
311.45/291.51	Innermost TRS:
311.45/291.51	Rules:
311.45/291.51	append(@l1, @l2) -> append#1(@l1, @l2)
311.45/291.51	append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
311.45/291.51	append#1(nil, @l2) -> @l2
311.45/291.51	subtrees(@t) -> subtrees#1(@t)
311.45/291.51	subtrees#1(leaf) -> nil
311.45/291.51	subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
311.45/291.51	subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
311.45/291.51	subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))
311.45/291.51	
311.45/291.51	Types:
311.45/291.51	append :: :::nil -> :::nil -> :::nil
311.45/291.51	append#1 :: :::nil -> :::nil -> :::nil
311.45/291.51	:: :: :::nil -> :::nil
311.45/291.51	nil :: :::nil
311.45/291.51	subtrees :: leaf:node -> :::nil
311.45/291.51	subtrees#1 :: leaf:node -> :::nil
311.45/291.51	leaf :: leaf:node
311.45/291.51	node :: leaf:node -> leaf:node -> leaf:node
311.45/291.51	subtrees#2 :: :::nil -> leaf:node -> :::nil
311.45/291.51	subtrees#3 :: :::nil -> :::nil -> :::nil
311.45/291.51	hole_:::nil1_0 :: :::nil
311.45/291.51	hole_leaf:node2_0 :: leaf:node
311.45/291.51	gen_:::nil3_0 :: Nat -> :::nil
311.45/291.51	gen_leaf:node4_0 :: Nat -> leaf:node
311.45/291.51	
311.45/291.51	
311.45/291.51	Generator Equations:
311.45/291.51	gen_:::nil3_0(0) <=> nil
311.45/291.51	gen_:::nil3_0(+(x, 1)) <=> ::(gen_:::nil3_0(x))
311.45/291.51	gen_leaf:node4_0(0) <=> leaf
311.45/291.51	gen_leaf:node4_0(+(x, 1)) <=> node(leaf, gen_leaf:node4_0(x))
311.45/291.51	
311.45/291.51	
311.45/291.51	The following defined symbols remain to be analysed:
311.45/291.51	subtrees#1, append, append#1, subtrees
311.45/291.51	
311.45/291.51	They will be analysed ascendingly in the following order:
311.45/291.51	append = append#1
311.45/291.51	subtrees = subtrees#1
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(24) LowerBoundPropagationProof (FINISHED)
311.45/291.51	Propagated lower bound.
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(25)
311.45/291.51	BOUNDS(n^1, INF)
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(26)
311.45/291.51	Obligation:
311.45/291.51	Innermost TRS:
311.45/291.51	Rules:
311.45/291.51	append(@l1, @l2) -> append#1(@l1, @l2)
311.45/291.51	append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
311.45/291.51	append#1(nil, @l2) -> @l2
311.45/291.51	subtrees(@t) -> subtrees#1(@t)
311.45/291.51	subtrees#1(leaf) -> nil
311.45/291.51	subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
311.45/291.51	subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
311.45/291.51	subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))
311.45/291.51	
311.45/291.51	Types:
311.45/291.51	append :: :::nil -> :::nil -> :::nil
311.45/291.51	append#1 :: :::nil -> :::nil -> :::nil
311.45/291.51	:: :: :::nil -> :::nil
311.45/291.51	nil :: :::nil
311.45/291.51	subtrees :: leaf:node -> :::nil
311.45/291.51	subtrees#1 :: leaf:node -> :::nil
311.45/291.51	leaf :: leaf:node
311.45/291.51	node :: leaf:node -> leaf:node -> leaf:node
311.45/291.51	subtrees#2 :: :::nil -> leaf:node -> :::nil
311.45/291.51	subtrees#3 :: :::nil -> :::nil -> :::nil
311.45/291.51	hole_:::nil1_0 :: :::nil
311.45/291.51	hole_leaf:node2_0 :: leaf:node
311.45/291.51	gen_:::nil3_0 :: Nat -> :::nil
311.45/291.51	gen_leaf:node4_0 :: Nat -> leaf:node
311.45/291.51	
311.45/291.51	
311.45/291.51	Lemmas:
311.45/291.51	subtrees#1(gen_leaf:node4_0(n6_0)) -> gen_:::nil3_0(n6_0), rt in Omega(1 + n6_0)
311.45/291.51	
311.45/291.51	
311.45/291.51	Generator Equations:
311.45/291.51	gen_:::nil3_0(0) <=> nil
311.45/291.51	gen_:::nil3_0(+(x, 1)) <=> ::(gen_:::nil3_0(x))
311.45/291.51	gen_leaf:node4_0(0) <=> leaf
311.45/291.51	gen_leaf:node4_0(+(x, 1)) <=> node(leaf, gen_leaf:node4_0(x))
311.45/291.51	
311.45/291.51	
311.45/291.51	The following defined symbols remain to be analysed:
311.45/291.51	subtrees, append, append#1
311.45/291.51	
311.45/291.51	They will be analysed ascendingly in the following order:
311.45/291.51	append = append#1
311.45/291.51	subtrees = subtrees#1
311.45/291.51	
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(27) RewriteLemmaProof (LOWER BOUND(ID))
311.45/291.51	Proved the following rewrite lemma:
311.45/291.51	append#1(gen_:::nil3_0(n383_0), gen_:::nil3_0(b)) -> gen_:::nil3_0(+(n383_0, b)), rt in Omega(1 + n383_0)
311.45/291.51	
311.45/291.51	Induction Base:
311.45/291.51	append#1(gen_:::nil3_0(0), gen_:::nil3_0(b)) ->_R^Omega(1)
311.45/291.51	gen_:::nil3_0(b)
311.45/291.51	
311.45/291.51	Induction Step:
311.45/291.51	append#1(gen_:::nil3_0(+(n383_0, 1)), gen_:::nil3_0(b)) ->_R^Omega(1)
311.45/291.51	::(append(gen_:::nil3_0(n383_0), gen_:::nil3_0(b))) ->_R^Omega(1)
311.45/291.51	::(append#1(gen_:::nil3_0(n383_0), gen_:::nil3_0(b))) ->_IH
311.45/291.51	::(gen_:::nil3_0(+(b, c384_0)))
311.45/291.51	
311.45/291.51	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
311.45/291.51	----------------------------------------
311.45/291.51	
311.45/291.51	(28)
311.45/291.51	Obligation:
311.45/291.51	Innermost TRS:
311.45/291.51	Rules:
311.45/291.51	append(@l1, @l2) -> append#1(@l1, @l2)
311.45/291.51	append#1(::(@xs), @l2) -> ::(append(@xs, @l2))
311.45/291.51	append#1(nil, @l2) -> @l2
311.45/291.51	subtrees(@t) -> subtrees#1(@t)
311.45/291.51	subtrees#1(leaf) -> nil
311.45/291.51	subtrees#1(node(@t1, @t2)) -> subtrees#2(subtrees(@t1), @t2)
311.45/291.51	subtrees#2(@l1, @t2) -> subtrees#3(subtrees(@t2), @l1)
311.45/291.51	subtrees#3(@l2, @l1) -> ::(append(@l1, @l2))
311.45/291.51	
311.45/291.51	Types:
311.45/291.51	append :: :::nil -> :::nil -> :::nil
311.45/291.51	append#1 :: :::nil -> :::nil -> :::nil
311.45/291.51	:: :: :::nil -> :::nil
311.45/291.51	nil :: :::nil
311.45/291.51	subtrees :: leaf:node -> :::nil
311.45/291.51	subtrees#1 :: leaf:node -> :::nil
311.45/291.51	leaf :: leaf:node
311.45/291.51	node :: leaf:node -> leaf:node -> leaf:node
311.45/291.51	subtrees#2 :: :::nil -> leaf:node -> :::nil
311.45/291.51	subtrees#3 :: :::nil -> :::nil -> :::nil
311.45/291.51	hole_:::nil1_0 :: :::nil
311.45/291.51	hole_leaf:node2_0 :: leaf:node
311.45/291.51	gen_:::nil3_0 :: Nat -> :::nil
311.45/291.51	gen_leaf:node4_0 :: Nat -> leaf:node
311.45/291.51	
311.45/291.51	
311.45/291.51	Lemmas:
311.45/291.51	subtrees#1(gen_leaf:node4_0(n6_0)) -> gen_:::nil3_0(n6_0), rt in Omega(1 + n6_0)
311.45/291.51	append#1(gen_:::nil3_0(n383_0), gen_:::nil3_0(b)) -> gen_:::nil3_0(+(n383_0, b)), rt in Omega(1 + n383_0)
311.45/291.51	
311.45/291.51	
311.45/291.51	Generator Equations:
311.45/291.51	gen_:::nil3_0(0) <=> nil
311.45/291.51	gen_:::nil3_0(+(x, 1)) <=> ::(gen_:::nil3_0(x))
311.45/291.51	gen_leaf:node4_0(0) <=> leaf
311.45/291.51	gen_leaf:node4_0(+(x, 1)) <=> node(leaf, gen_leaf:node4_0(x))
311.45/291.51	
311.45/291.51	
311.45/291.51	The following defined symbols remain to be analysed:
311.45/291.51	append
311.45/291.51	
311.45/291.51	They will be analysed ascendingly in the following order:
311.45/291.51	append = append#1
311.45/291.55	EOF