11.96/3.95	WORST_CASE(Omega(n^3), O(n^3))
12.49/3.96	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
12.49/3.96	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
12.49/3.96	
12.49/3.96	
12.49/3.96	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3).
12.49/3.96	
12.49/3.96	(0) CpxTRS
12.49/3.96	(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
12.49/3.96	(2) CdtProblem
12.49/3.96	    (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
12.49/3.96	    (4) CdtProblem
12.49/3.96	    (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
12.49/3.96	    (6) CdtProblem
12.49/3.96	    (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 49 ms]
12.49/3.96	    (8) CdtProblem
12.49/3.96	    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 85 ms]
12.49/3.96	    (10) CdtProblem
12.49/3.96	    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 49 ms]
12.49/3.96	    (12) CdtProblem
12.49/3.96	    (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
12.49/3.96	    (14) BOUNDS(1, 1)
12.49/3.96	(15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
12.49/3.96	(16) CpxTRS
12.49/3.96	    (17) SlicingProof [LOWER BOUND(ID), 0 ms]
12.49/3.96	    (18) CpxTRS
12.49/3.96	    (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
12.49/3.96	    (20) typed CpxTrs
12.49/3.96	    (21) OrderProof [LOWER BOUND(ID), 0 ms]
12.49/3.96	    (22) typed CpxTrs
12.49/3.96	    (23) RewriteLemmaProof [LOWER BOUND(ID), 313 ms]
12.49/3.96	    (24) BEST
12.49/3.96	        (25) proven lower bound
12.49/3.96	            (26) LowerBoundPropagationProof [FINISHED, 0 ms]
12.49/3.96	            (27) BOUNDS(n^1, INF)
12.49/3.96	        (28) typed CpxTrs
12.49/3.96	            (29) RewriteLemmaProof [LOWER BOUND(ID), 33 ms]
12.49/3.96	            (30) BEST
12.49/3.96	                (31) proven lower bound
12.49/3.96	                    (32) LowerBoundPropagationProof [FINISHED, 0 ms]
12.49/3.96	                    (33) BOUNDS(n^2, INF)
12.49/3.96	                (34) typed CpxTrs
12.49/3.96	                    (35) RewriteLemmaProof [LOWER BOUND(ID), 20 ms]
12.49/3.96	                    (36) proven lower bound
12.49/3.96	                    (37) LowerBoundPropagationProof [FINISHED, 0 ms]
12.49/3.96	                    (38) BOUNDS(n^3, INF)
12.49/3.96	
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(0)
12.49/3.96	Obligation:
12.49/3.96	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3).
12.49/3.96	
12.49/3.96	
12.49/3.96	The TRS R consists of the following rules:
12.49/3.96	
12.49/3.96	   shuffle(Cons(x, xs)) -> Cons(x, shuffle(reverse(xs)))
12.49/3.96	   reverse(Cons(x, xs)) -> append(reverse(xs), Cons(x, Nil))
12.49/3.96	   append(Cons(x, xs), ys) -> Cons(x, append(xs, ys))
12.49/3.96	   shuffle(Nil) -> Nil
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Nil, ys) -> ys
12.49/3.96	   goal(xs) -> shuffle(xs)
12.49/3.96	
12.49/3.96	S is empty.
12.49/3.96	Rewrite Strategy: INNERMOST
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(1) CpxTrsToCdtProof (UPPER BOUND(ID))
12.49/3.96	Converted Cpx (relative) TRS to CDT
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(2)
12.49/3.96	Obligation:
12.49/3.96	Complexity Dependency Tuples Problem
12.49/3.96	
12.49/3.96	Rules:
12.49/3.96	   shuffle(Cons(z0, z1)) -> Cons(z0, shuffle(reverse(z1)))
12.49/3.96	   shuffle(Nil) -> Nil
12.49/3.96	   reverse(Cons(z0, z1)) -> append(reverse(z1), Cons(z0, Nil))
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Cons(z0, z1), z2) -> Cons(z0, append(z1, z2))
12.49/3.96	   append(Nil, z0) -> z0
12.49/3.96	   goal(z0) -> shuffle(z0)
12.49/3.96	Tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   SHUFFLE(Nil) -> c1
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   REVERSE(Nil) -> c3
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	   APPEND(Nil, z0) -> c5
12.49/3.96	   GOAL(z0) -> c6(SHUFFLE(z0))
12.49/3.96	S tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   SHUFFLE(Nil) -> c1
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   REVERSE(Nil) -> c3
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	   APPEND(Nil, z0) -> c5
12.49/3.96	   GOAL(z0) -> c6(SHUFFLE(z0))
12.49/3.96	K tuples:none
12.49/3.96	Defined Rule Symbols:   shuffle_1, reverse_1, append_2, goal_1
12.49/3.96	
12.49/3.96	Defined Pair Symbols:   SHUFFLE_1, REVERSE_1, APPEND_2, GOAL_1
12.49/3.96	
12.49/3.96	Compound Symbols:   c_2, c1, c2_2, c3, c4_1, c5, c6_1
12.49/3.96	
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(3) CdtLeafRemovalProof (ComplexityIfPolyImplication)
12.49/3.96	Removed 1 leading nodes:
12.49/3.96	   GOAL(z0) -> c6(SHUFFLE(z0))
12.49/3.96	Removed 3 trailing nodes:
12.49/3.96	   SHUFFLE(Nil) -> c1
12.49/3.96	   REVERSE(Nil) -> c3
12.49/3.96	   APPEND(Nil, z0) -> c5
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(4)
12.49/3.96	Obligation:
12.49/3.96	Complexity Dependency Tuples Problem
12.49/3.96	
12.49/3.96	Rules:
12.49/3.96	   shuffle(Cons(z0, z1)) -> Cons(z0, shuffle(reverse(z1)))
12.49/3.96	   shuffle(Nil) -> Nil
12.49/3.96	   reverse(Cons(z0, z1)) -> append(reverse(z1), Cons(z0, Nil))
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Cons(z0, z1), z2) -> Cons(z0, append(z1, z2))
12.49/3.96	   append(Nil, z0) -> z0
12.49/3.96	   goal(z0) -> shuffle(z0)
12.49/3.96	Tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	S tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	K tuples:none
12.49/3.96	Defined Rule Symbols:   shuffle_1, reverse_1, append_2, goal_1
12.49/3.96	
12.49/3.96	Defined Pair Symbols:   SHUFFLE_1, REVERSE_1, APPEND_2
12.49/3.96	
12.49/3.96	Compound Symbols:   c_2, c2_2, c4_1
12.49/3.96	
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
12.49/3.96	The following rules are not usable and were removed:
12.49/3.96	   shuffle(Cons(z0, z1)) -> Cons(z0, shuffle(reverse(z1)))
12.49/3.96	   shuffle(Nil) -> Nil
12.49/3.96	   goal(z0) -> shuffle(z0)
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(6)
12.49/3.96	Obligation:
12.49/3.96	Complexity Dependency Tuples Problem
12.49/3.96	
12.49/3.96	Rules:
12.49/3.96	   reverse(Cons(z0, z1)) -> append(reverse(z1), Cons(z0, Nil))
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Cons(z0, z1), z2) -> Cons(z0, append(z1, z2))
12.49/3.96	   append(Nil, z0) -> z0
12.49/3.96	Tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	S tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	K tuples:none
12.49/3.96	Defined Rule Symbols:   reverse_1, append_2
12.49/3.96	
12.49/3.96	Defined Pair Symbols:   SHUFFLE_1, REVERSE_1, APPEND_2
12.49/3.96	
12.49/3.96	Compound Symbols:   c_2, c2_2, c4_1
12.49/3.96	
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
12.49/3.96	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	We considered the (Usable) Rules:
12.49/3.96	   append(Cons(z0, z1), z2) -> Cons(z0, append(z1, z2))
12.49/3.96	   reverse(Cons(z0, z1)) -> append(reverse(z1), Cons(z0, Nil))
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Nil, z0) -> z0
12.49/3.96	And the Tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	The order we found is given by the following interpretation:
12.49/3.96	
12.49/3.96	Polynomial interpretation :
12.49/3.96	
12.49/3.96	   POL(APPEND(x_1, x_2)) = 0
12.49/3.96	   POL(Cons(x_1, x_2)) = [1] + x_1 + x_2
12.49/3.96	   POL(Nil) = 0
12.49/3.96	   POL(REVERSE(x_1)) = 0
12.49/3.96	   POL(SHUFFLE(x_1)) = x_1
12.49/3.96	   POL(append(x_1, x_2)) = x_1 + x_2
12.49/3.96	   POL(c(x_1, x_2)) = x_1 + x_2
12.49/3.96	   POL(c2(x_1, x_2)) = x_1 + x_2
12.49/3.96	   POL(c4(x_1)) = x_1
12.49/3.96	   POL(reverse(x_1)) = x_1
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(8)
12.49/3.96	Obligation:
12.49/3.96	Complexity Dependency Tuples Problem
12.49/3.96	
12.49/3.96	Rules:
12.49/3.96	   reverse(Cons(z0, z1)) -> append(reverse(z1), Cons(z0, Nil))
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Cons(z0, z1), z2) -> Cons(z0, append(z1, z2))
12.49/3.96	   append(Nil, z0) -> z0
12.49/3.96	Tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	S tuples:
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	K tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	Defined Rule Symbols:   reverse_1, append_2
12.49/3.96	
12.49/3.96	Defined Pair Symbols:   SHUFFLE_1, REVERSE_1, APPEND_2
12.49/3.96	
12.49/3.96	Compound Symbols:   c_2, c2_2, c4_1
12.49/3.96	
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
12.49/3.96	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	We considered the (Usable) Rules:
12.49/3.96	   append(Cons(z0, z1), z2) -> Cons(z0, append(z1, z2))
12.49/3.96	   reverse(Cons(z0, z1)) -> append(reverse(z1), Cons(z0, Nil))
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Nil, z0) -> z0
12.49/3.96	And the Tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	The order we found is given by the following interpretation:
12.49/3.96	
12.49/3.96	Polynomial interpretation :
12.49/3.96	
12.49/3.96	   POL(APPEND(x_1, x_2)) = 0
12.49/3.96	   POL(Cons(x_1, x_2)) = [1] + x_2
12.49/3.96	   POL(Nil) = 0
12.49/3.96	   POL(REVERSE(x_1)) = x_1
12.49/3.96	   POL(SHUFFLE(x_1)) = x_1^2
12.49/3.96	   POL(append(x_1, x_2)) = x_1 + x_2
12.49/3.96	   POL(c(x_1, x_2)) = x_1 + x_2
12.49/3.96	   POL(c2(x_1, x_2)) = x_1 + x_2
12.49/3.96	   POL(c4(x_1)) = x_1
12.49/3.96	   POL(reverse(x_1)) = x_1
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(10)
12.49/3.96	Obligation:
12.49/3.96	Complexity Dependency Tuples Problem
12.49/3.96	
12.49/3.96	Rules:
12.49/3.96	   reverse(Cons(z0, z1)) -> append(reverse(z1), Cons(z0, Nil))
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Cons(z0, z1), z2) -> Cons(z0, append(z1, z2))
12.49/3.96	   append(Nil, z0) -> z0
12.49/3.96	Tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	S tuples:
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	K tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	Defined Rule Symbols:   reverse_1, append_2
12.49/3.96	
12.49/3.96	Defined Pair Symbols:   SHUFFLE_1, REVERSE_1, APPEND_2
12.49/3.96	
12.49/3.96	Compound Symbols:   c_2, c2_2, c4_1
12.49/3.96	
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3)))
12.49/3.96	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	We considered the (Usable) Rules:
12.49/3.96	   append(Cons(z0, z1), z2) -> Cons(z0, append(z1, z2))
12.49/3.96	   reverse(Cons(z0, z1)) -> append(reverse(z1), Cons(z0, Nil))
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Nil, z0) -> z0
12.49/3.96	And the Tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	The order we found is given by the following interpretation:
12.49/3.96	
12.49/3.96	Polynomial interpretation :
12.49/3.96	
12.49/3.96	   POL(APPEND(x_1, x_2)) = x_1
12.49/3.96	   POL(Cons(x_1, x_2)) = [1] + x_2
12.49/3.96	   POL(Nil) = 0
12.49/3.96	   POL(REVERSE(x_1)) = x_1^2
12.49/3.96	   POL(SHUFFLE(x_1)) = x_1^3
12.49/3.96	   POL(append(x_1, x_2)) = x_1 + x_2
12.49/3.96	   POL(c(x_1, x_2)) = x_1 + x_2
12.49/3.96	   POL(c2(x_1, x_2)) = x_1 + x_2
12.49/3.96	   POL(c4(x_1)) = x_1
12.49/3.96	   POL(reverse(x_1)) = x_1
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(12)
12.49/3.96	Obligation:
12.49/3.96	Complexity Dependency Tuples Problem
12.49/3.96	
12.49/3.96	Rules:
12.49/3.96	   reverse(Cons(z0, z1)) -> append(reverse(z1), Cons(z0, Nil))
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Cons(z0, z1), z2) -> Cons(z0, append(z1, z2))
12.49/3.96	   append(Nil, z0) -> z0
12.49/3.96	Tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	S tuples:none
12.49/3.96	K tuples:
12.49/3.96	   SHUFFLE(Cons(z0, z1)) -> c(SHUFFLE(reverse(z1)), REVERSE(z1))
12.49/3.96	   REVERSE(Cons(z0, z1)) -> c2(APPEND(reverse(z1), Cons(z0, Nil)), REVERSE(z1))
12.49/3.96	   APPEND(Cons(z0, z1), z2) -> c4(APPEND(z1, z2))
12.49/3.96	Defined Rule Symbols:   reverse_1, append_2
12.49/3.96	
12.49/3.96	Defined Pair Symbols:   SHUFFLE_1, REVERSE_1, APPEND_2
12.49/3.96	
12.49/3.96	Compound Symbols:   c_2, c2_2, c4_1
12.49/3.96	
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(13) SIsEmptyProof (BOTH BOUNDS(ID, ID))
12.49/3.96	The set S is empty
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(14)
12.49/3.96	BOUNDS(1, 1)
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(15) RenamingProof (BOTH BOUNDS(ID, ID))
12.49/3.96	Renamed function symbols to avoid clashes with predefined symbol.
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(16)
12.49/3.96	Obligation:
12.49/3.96	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).
12.49/3.96	
12.49/3.96	
12.49/3.96	The TRS R consists of the following rules:
12.49/3.96	
12.49/3.96	   shuffle(Cons(x, xs)) -> Cons(x, shuffle(reverse(xs)))
12.49/3.96	   reverse(Cons(x, xs)) -> append(reverse(xs), Cons(x, Nil))
12.49/3.96	   append(Cons(x, xs), ys) -> Cons(x, append(xs, ys))
12.49/3.96	   shuffle(Nil) -> Nil
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Nil, ys) -> ys
12.49/3.96	   goal(xs) -> shuffle(xs)
12.49/3.96	
12.49/3.96	S is empty.
12.49/3.96	Rewrite Strategy: INNERMOST
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(17) SlicingProof (LOWER BOUND(ID))
12.49/3.96	Sliced the following arguments:
12.49/3.96	Cons/0
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(18)
12.49/3.96	Obligation:
12.49/3.96	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).
12.49/3.96	
12.49/3.96	
12.49/3.96	The TRS R consists of the following rules:
12.49/3.96	
12.49/3.96	   shuffle(Cons(xs)) -> Cons(shuffle(reverse(xs)))
12.49/3.96	   reverse(Cons(xs)) -> append(reverse(xs), Cons(Nil))
12.49/3.96	   append(Cons(xs), ys) -> Cons(append(xs, ys))
12.49/3.96	   shuffle(Nil) -> Nil
12.49/3.96	   reverse(Nil) -> Nil
12.49/3.96	   append(Nil, ys) -> ys
12.49/3.96	   goal(xs) -> shuffle(xs)
12.49/3.96	
12.49/3.96	S is empty.
12.49/3.96	Rewrite Strategy: INNERMOST
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(19) TypeInferenceProof (BOTH BOUNDS(ID, ID))
12.49/3.96	Infered types.
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(20)
12.49/3.96	Obligation:
12.49/3.96	Innermost TRS:
12.49/3.96	Rules:
12.49/3.96	shuffle(Cons(xs)) -> Cons(shuffle(reverse(xs)))
12.49/3.96	reverse(Cons(xs)) -> append(reverse(xs), Cons(Nil))
12.49/3.96	append(Cons(xs), ys) -> Cons(append(xs, ys))
12.49/3.96	shuffle(Nil) -> Nil
12.49/3.96	reverse(Nil) -> Nil
12.49/3.96	append(Nil, ys) -> ys
12.49/3.96	goal(xs) -> shuffle(xs)
12.49/3.96	
12.49/3.96	Types:
12.49/3.96	shuffle :: Cons:Nil -> Cons:Nil
12.49/3.96	Cons :: Cons:Nil -> Cons:Nil
12.49/3.96	reverse :: Cons:Nil -> Cons:Nil
12.49/3.96	append :: Cons:Nil -> Cons:Nil -> Cons:Nil
12.49/3.96	Nil :: Cons:Nil
12.49/3.96	goal :: Cons:Nil -> Cons:Nil
12.49/3.96	hole_Cons:Nil1_0 :: Cons:Nil
12.49/3.96	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(21) OrderProof (LOWER BOUND(ID))
12.49/3.96	Heuristically decided to analyse the following defined symbols:
12.49/3.96	shuffle, reverse, append
12.49/3.96	
12.49/3.96	They will be analysed ascendingly in the following order:
12.49/3.96	reverse < shuffle
12.49/3.96	append < reverse
12.49/3.96	
12.49/3.96	----------------------------------------
12.49/3.96	
12.49/3.96	(22)
12.49/3.96	Obligation:
12.49/3.96	Innermost TRS:
12.49/3.96	Rules:
12.49/3.96	shuffle(Cons(xs)) -> Cons(shuffle(reverse(xs)))
12.49/3.96	reverse(Cons(xs)) -> append(reverse(xs), Cons(Nil))
12.49/3.96	append(Cons(xs), ys) -> Cons(append(xs, ys))
12.49/3.96	shuffle(Nil) -> Nil
12.49/3.96	reverse(Nil) -> Nil
12.49/3.96	append(Nil, ys) -> ys
12.49/3.96	goal(xs) -> shuffle(xs)
12.49/3.96	
12.49/3.96	Types:
12.49/3.96	shuffle :: Cons:Nil -> Cons:Nil
12.49/3.96	Cons :: Cons:Nil -> Cons:Nil
12.49/3.96	reverse :: Cons:Nil -> Cons:Nil
12.49/3.96	append :: Cons:Nil -> Cons:Nil -> Cons:Nil
12.49/3.96	Nil :: Cons:Nil
12.49/3.97	goal :: Cons:Nil -> Cons:Nil
12.49/3.97	hole_Cons:Nil1_0 :: Cons:Nil
12.49/3.97	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
12.49/3.97	
12.49/3.97	
12.49/3.97	Generator Equations:
12.49/3.97	gen_Cons:Nil2_0(0) <=> Nil
12.49/3.97	gen_Cons:Nil2_0(+(x, 1)) <=> Cons(gen_Cons:Nil2_0(x))
12.49/3.97	
12.49/3.97	
12.49/3.97	The following defined symbols remain to be analysed:
12.49/3.97	append, shuffle, reverse
12.49/3.97	
12.49/3.97	They will be analysed ascendingly in the following order:
12.49/3.97	reverse < shuffle
12.49/3.97	append < reverse
12.49/3.97	
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(23) RewriteLemmaProof (LOWER BOUND(ID))
12.49/3.97	Proved the following rewrite lemma:
12.49/3.97	append(gen_Cons:Nil2_0(n4_0), gen_Cons:Nil2_0(b)) -> gen_Cons:Nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
12.49/3.97	
12.49/3.97	Induction Base:
12.49/3.97	append(gen_Cons:Nil2_0(0), gen_Cons:Nil2_0(b)) ->_R^Omega(1)
12.49/3.97	gen_Cons:Nil2_0(b)
12.49/3.97	
12.49/3.97	Induction Step:
12.49/3.97	append(gen_Cons:Nil2_0(+(n4_0, 1)), gen_Cons:Nil2_0(b)) ->_R^Omega(1)
12.49/3.97	Cons(append(gen_Cons:Nil2_0(n4_0), gen_Cons:Nil2_0(b))) ->_IH
12.49/3.97	Cons(gen_Cons:Nil2_0(+(b, c5_0)))
12.49/3.97	
12.49/3.97	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(24)
12.49/3.97	Complex Obligation (BEST)
12.49/3.97	
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(25)
12.49/3.97	Obligation:
12.49/3.97	Proved the lower bound n^1 for the following obligation:
12.49/3.97	
12.49/3.97	Innermost TRS:
12.49/3.97	Rules:
12.49/3.97	shuffle(Cons(xs)) -> Cons(shuffle(reverse(xs)))
12.49/3.97	reverse(Cons(xs)) -> append(reverse(xs), Cons(Nil))
12.49/3.97	append(Cons(xs), ys) -> Cons(append(xs, ys))
12.49/3.97	shuffle(Nil) -> Nil
12.49/3.97	reverse(Nil) -> Nil
12.49/3.97	append(Nil, ys) -> ys
12.49/3.97	goal(xs) -> shuffle(xs)
12.49/3.97	
12.49/3.97	Types:
12.49/3.97	shuffle :: Cons:Nil -> Cons:Nil
12.49/3.97	Cons :: Cons:Nil -> Cons:Nil
12.49/3.97	reverse :: Cons:Nil -> Cons:Nil
12.49/3.97	append :: Cons:Nil -> Cons:Nil -> Cons:Nil
12.49/3.97	Nil :: Cons:Nil
12.49/3.97	goal :: Cons:Nil -> Cons:Nil
12.49/3.97	hole_Cons:Nil1_0 :: Cons:Nil
12.49/3.97	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
12.49/3.97	
12.49/3.97	
12.49/3.97	Generator Equations:
12.49/3.97	gen_Cons:Nil2_0(0) <=> Nil
12.49/3.97	gen_Cons:Nil2_0(+(x, 1)) <=> Cons(gen_Cons:Nil2_0(x))
12.49/3.97	
12.49/3.97	
12.49/3.97	The following defined symbols remain to be analysed:
12.49/3.97	append, shuffle, reverse
12.49/3.97	
12.49/3.97	They will be analysed ascendingly in the following order:
12.49/3.97	reverse < shuffle
12.49/3.97	append < reverse
12.49/3.97	
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(26) LowerBoundPropagationProof (FINISHED)
12.49/3.97	Propagated lower bound.
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(27)
12.49/3.97	BOUNDS(n^1, INF)
12.49/3.97	
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(28)
12.49/3.97	Obligation:
12.49/3.97	Innermost TRS:
12.49/3.97	Rules:
12.49/3.97	shuffle(Cons(xs)) -> Cons(shuffle(reverse(xs)))
12.49/3.97	reverse(Cons(xs)) -> append(reverse(xs), Cons(Nil))
12.49/3.97	append(Cons(xs), ys) -> Cons(append(xs, ys))
12.49/3.97	shuffle(Nil) -> Nil
12.49/3.97	reverse(Nil) -> Nil
12.49/3.97	append(Nil, ys) -> ys
12.49/3.97	goal(xs) -> shuffle(xs)
12.49/3.97	
12.49/3.97	Types:
12.49/3.97	shuffle :: Cons:Nil -> Cons:Nil
12.49/3.97	Cons :: Cons:Nil -> Cons:Nil
12.49/3.97	reverse :: Cons:Nil -> Cons:Nil
12.49/3.97	append :: Cons:Nil -> Cons:Nil -> Cons:Nil
12.49/3.97	Nil :: Cons:Nil
12.49/3.97	goal :: Cons:Nil -> Cons:Nil
12.49/3.97	hole_Cons:Nil1_0 :: Cons:Nil
12.49/3.97	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
12.49/3.97	
12.49/3.97	
12.49/3.97	Lemmas:
12.49/3.97	append(gen_Cons:Nil2_0(n4_0), gen_Cons:Nil2_0(b)) -> gen_Cons:Nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
12.49/3.97	
12.49/3.97	
12.49/3.97	Generator Equations:
12.49/3.97	gen_Cons:Nil2_0(0) <=> Nil
12.49/3.97	gen_Cons:Nil2_0(+(x, 1)) <=> Cons(gen_Cons:Nil2_0(x))
12.49/3.97	
12.49/3.97	
12.49/3.97	The following defined symbols remain to be analysed:
12.49/3.97	reverse, shuffle
12.49/3.97	
12.49/3.97	They will be analysed ascendingly in the following order:
12.49/3.97	reverse < shuffle
12.49/3.97	
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(29) RewriteLemmaProof (LOWER BOUND(ID))
12.49/3.97	Proved the following rewrite lemma:
12.49/3.97	reverse(gen_Cons:Nil2_0(n504_0)) -> gen_Cons:Nil2_0(n504_0), rt in Omega(1 + n504_0 + n504_0^2)
12.49/3.97	
12.49/3.97	Induction Base:
12.49/3.97	reverse(gen_Cons:Nil2_0(0)) ->_R^Omega(1)
12.49/3.97	Nil
12.49/3.97	
12.49/3.97	Induction Step:
12.49/3.97	reverse(gen_Cons:Nil2_0(+(n504_0, 1))) ->_R^Omega(1)
12.49/3.97	append(reverse(gen_Cons:Nil2_0(n504_0)), Cons(Nil)) ->_IH
12.49/3.97	append(gen_Cons:Nil2_0(c505_0), Cons(Nil)) ->_L^Omega(1 + n504_0)
12.49/3.97	gen_Cons:Nil2_0(+(n504_0, +(0, 1)))
12.49/3.97	
12.49/3.97	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(30)
12.49/3.97	Complex Obligation (BEST)
12.49/3.97	
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(31)
12.49/3.97	Obligation:
12.49/3.97	Proved the lower bound n^2 for the following obligation:
12.49/3.97	
12.49/3.97	Innermost TRS:
12.49/3.97	Rules:
12.49/3.97	shuffle(Cons(xs)) -> Cons(shuffle(reverse(xs)))
12.49/3.97	reverse(Cons(xs)) -> append(reverse(xs), Cons(Nil))
12.49/3.97	append(Cons(xs), ys) -> Cons(append(xs, ys))
12.49/3.97	shuffle(Nil) -> Nil
12.49/3.97	reverse(Nil) -> Nil
12.49/3.97	append(Nil, ys) -> ys
12.49/3.97	goal(xs) -> shuffle(xs)
12.49/3.97	
12.49/3.97	Types:
12.49/3.97	shuffle :: Cons:Nil -> Cons:Nil
12.49/3.97	Cons :: Cons:Nil -> Cons:Nil
12.49/3.97	reverse :: Cons:Nil -> Cons:Nil
12.49/3.97	append :: Cons:Nil -> Cons:Nil -> Cons:Nil
12.49/3.97	Nil :: Cons:Nil
12.49/3.97	goal :: Cons:Nil -> Cons:Nil
12.49/3.97	hole_Cons:Nil1_0 :: Cons:Nil
12.49/3.97	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
12.49/3.97	
12.49/3.97	
12.49/3.97	Lemmas:
12.49/3.97	append(gen_Cons:Nil2_0(n4_0), gen_Cons:Nil2_0(b)) -> gen_Cons:Nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
12.49/3.97	
12.49/3.97	
12.49/3.97	Generator Equations:
12.49/3.97	gen_Cons:Nil2_0(0) <=> Nil
12.49/3.97	gen_Cons:Nil2_0(+(x, 1)) <=> Cons(gen_Cons:Nil2_0(x))
12.49/3.97	
12.49/3.97	
12.49/3.97	The following defined symbols remain to be analysed:
12.49/3.97	reverse, shuffle
12.49/3.97	
12.49/3.97	They will be analysed ascendingly in the following order:
12.49/3.97	reverse < shuffle
12.49/3.97	
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(32) LowerBoundPropagationProof (FINISHED)
12.49/3.97	Propagated lower bound.
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(33)
12.49/3.97	BOUNDS(n^2, INF)
12.49/3.97	
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(34)
12.49/3.97	Obligation:
12.49/3.97	Innermost TRS:
12.49/3.97	Rules:
12.49/3.97	shuffle(Cons(xs)) -> Cons(shuffle(reverse(xs)))
12.49/3.97	reverse(Cons(xs)) -> append(reverse(xs), Cons(Nil))
12.49/3.97	append(Cons(xs), ys) -> Cons(append(xs, ys))
12.49/3.97	shuffle(Nil) -> Nil
12.49/3.97	reverse(Nil) -> Nil
12.49/3.97	append(Nil, ys) -> ys
12.49/3.97	goal(xs) -> shuffle(xs)
12.49/3.97	
12.49/3.97	Types:
12.49/3.97	shuffle :: Cons:Nil -> Cons:Nil
12.49/3.97	Cons :: Cons:Nil -> Cons:Nil
12.49/3.97	reverse :: Cons:Nil -> Cons:Nil
12.49/3.97	append :: Cons:Nil -> Cons:Nil -> Cons:Nil
12.49/3.97	Nil :: Cons:Nil
12.49/3.97	goal :: Cons:Nil -> Cons:Nil
12.49/3.97	hole_Cons:Nil1_0 :: Cons:Nil
12.49/3.97	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
12.49/3.97	
12.49/3.97	
12.49/3.97	Lemmas:
12.49/3.97	append(gen_Cons:Nil2_0(n4_0), gen_Cons:Nil2_0(b)) -> gen_Cons:Nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
12.49/3.97	reverse(gen_Cons:Nil2_0(n504_0)) -> gen_Cons:Nil2_0(n504_0), rt in Omega(1 + n504_0 + n504_0^2)
12.49/3.97	
12.49/3.97	
12.49/3.97	Generator Equations:
12.49/3.97	gen_Cons:Nil2_0(0) <=> Nil
12.49/3.97	gen_Cons:Nil2_0(+(x, 1)) <=> Cons(gen_Cons:Nil2_0(x))
12.49/3.97	
12.49/3.97	
12.49/3.97	The following defined symbols remain to be analysed:
12.49/3.97	shuffle
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(35) RewriteLemmaProof (LOWER BOUND(ID))
12.49/3.97	Proved the following rewrite lemma:
12.49/3.97	shuffle(gen_Cons:Nil2_0(n719_0)) -> gen_Cons:Nil2_0(n719_0), rt in Omega(1 + n719_0 + n719_0^2 + n719_0^3)
12.49/3.97	
12.49/3.97	Induction Base:
12.49/3.97	shuffle(gen_Cons:Nil2_0(0)) ->_R^Omega(1)
12.49/3.97	Nil
12.49/3.97	
12.49/3.97	Induction Step:
12.49/3.97	shuffle(gen_Cons:Nil2_0(+(n719_0, 1))) ->_R^Omega(1)
12.49/3.97	Cons(shuffle(reverse(gen_Cons:Nil2_0(n719_0)))) ->_L^Omega(1 + n719_0 + n719_0^2)
12.49/3.97	Cons(shuffle(gen_Cons:Nil2_0(n719_0))) ->_IH
12.49/3.97	Cons(gen_Cons:Nil2_0(c720_0))
12.49/3.97	
12.49/3.97	We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3).
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(36)
12.49/3.97	Obligation:
12.49/3.97	Proved the lower bound n^3 for the following obligation:
12.49/3.97	
12.49/3.97	Innermost TRS:
12.49/3.97	Rules:
12.49/3.97	shuffle(Cons(xs)) -> Cons(shuffle(reverse(xs)))
12.49/3.97	reverse(Cons(xs)) -> append(reverse(xs), Cons(Nil))
12.49/3.97	append(Cons(xs), ys) -> Cons(append(xs, ys))
12.49/3.97	shuffle(Nil) -> Nil
12.49/3.97	reverse(Nil) -> Nil
12.49/3.97	append(Nil, ys) -> ys
12.49/3.97	goal(xs) -> shuffle(xs)
12.49/3.97	
12.49/3.97	Types:
12.49/3.97	shuffle :: Cons:Nil -> Cons:Nil
12.49/3.97	Cons :: Cons:Nil -> Cons:Nil
12.49/3.97	reverse :: Cons:Nil -> Cons:Nil
12.49/3.97	append :: Cons:Nil -> Cons:Nil -> Cons:Nil
12.49/3.97	Nil :: Cons:Nil
12.49/3.97	goal :: Cons:Nil -> Cons:Nil
12.49/3.97	hole_Cons:Nil1_0 :: Cons:Nil
12.49/3.97	gen_Cons:Nil2_0 :: Nat -> Cons:Nil
12.49/3.97	
12.49/3.97	
12.49/3.97	Lemmas:
12.49/3.97	append(gen_Cons:Nil2_0(n4_0), gen_Cons:Nil2_0(b)) -> gen_Cons:Nil2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
12.49/3.97	reverse(gen_Cons:Nil2_0(n504_0)) -> gen_Cons:Nil2_0(n504_0), rt in Omega(1 + n504_0 + n504_0^2)
12.49/3.97	
12.49/3.97	
12.49/3.97	Generator Equations:
12.49/3.97	gen_Cons:Nil2_0(0) <=> Nil
12.49/3.97	gen_Cons:Nil2_0(+(x, 1)) <=> Cons(gen_Cons:Nil2_0(x))
12.49/3.97	
12.49/3.97	
12.49/3.97	The following defined symbols remain to be analysed:
12.49/3.97	shuffle
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(37) LowerBoundPropagationProof (FINISHED)
12.49/3.97	Propagated lower bound.
12.49/3.97	----------------------------------------
12.49/3.97	
12.49/3.97	(38)
12.49/3.97	BOUNDS(n^3, INF)
12.56/4.00	EOF