348.07/291.51	WORST_CASE(Omega(n^1), O(n^2))
348.07/291.52	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
348.07/291.52	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
348.07/291.52	
348.07/291.52	
348.07/291.52	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
348.07/291.52	
348.07/291.52	(0) CpxRelTRS
348.07/291.52	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 159 ms]
348.07/291.52	(2) CpxRelTRS
348.07/291.52	(3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
348.07/291.52	(4) CdtProblem
348.07/291.52	    (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
348.07/291.52	    (6) CdtProblem
348.07/291.52	    (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
348.07/291.52	    (8) CdtProblem
348.07/291.52	    (9) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms]
348.07/291.52	    (10) CdtProblem
348.07/291.52	    (11) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
348.07/291.52	    (12) CdtProblem
348.07/291.52	    (13) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
348.07/291.52	    (14) CdtProblem
348.07/291.52	    (15) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
348.07/291.52	    (16) CdtProblem
348.07/291.52	    (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 54 ms]
348.07/291.52	    (18) CdtProblem
348.07/291.52	    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 24 ms]
348.07/291.52	    (20) CdtProblem
348.07/291.52	    (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 23 ms]
348.07/291.52	    (22) CdtProblem
348.07/291.52	    (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 67 ms]
348.07/291.52	    (24) CdtProblem
348.07/291.52	    (25) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
348.07/291.52	    (26) BOUNDS(1, 1)
348.07/291.52	(27) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
348.07/291.52	(28) TRS for Loop Detection
348.07/291.52	    (29) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
348.07/291.52	    (30) BEST
348.07/291.52	        (31) proven lower bound
348.07/291.52	            (32) LowerBoundPropagationProof [FINISHED, 0 ms]
348.07/291.52	            (33) BOUNDS(n^1, INF)
348.07/291.52	        (34) TRS for Loop Detection
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(0)
348.07/291.52	Obligation:
348.07/291.52	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
348.07/291.52	
348.07/291.52	
348.07/291.52	The TRS R consists of the following rules:
348.07/291.52	
348.07/291.52	   bsort(S(x'), Cons(x, xs)) -> bsort(x', bubble(x, xs))
348.07/291.52	   len(Cons(x, xs)) -> +(S(0), len(xs))
348.07/291.52	   bubble(x', Cons(x, xs)) -> bubble[Ite][False][Ite](<(x', x), x', Cons(x, xs))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   bubble(x, Nil) -> Cons(x, Nil)
348.07/291.52	   bsort(0, xs) -> xs
348.07/291.52	   bubblesort(xs) -> bsort(len(xs), xs)
348.07/291.52	
348.07/291.52	The (relative) TRS S consists of the following rules:
348.07/291.52	
348.07/291.52	   +(x, S(0)) -> S(x)
348.07/291.52	   +(S(0), y) -> S(y)
348.07/291.52	   <(S(x), S(y)) -> <(x, y)
348.07/291.52	   <(0, S(y)) -> True
348.07/291.52	   <(x, 0) -> False
348.07/291.52	   bubble[Ite][False][Ite](False, x', Cons(x, xs)) -> Cons(x, bubble(x', xs))
348.07/291.52	   bubble[Ite][False][Ite](True, x', Cons(x, xs)) -> Cons(x', bubble(x, xs))
348.07/291.52	
348.07/291.52	Rewrite Strategy: INNERMOST
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
348.07/291.52	proved termination of relative rules
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(2)
348.07/291.52	Obligation:
348.07/291.52	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
348.07/291.52	
348.07/291.52	
348.07/291.52	The TRS R consists of the following rules:
348.07/291.52	
348.07/291.52	   bsort(S(x'), Cons(x, xs)) -> bsort(x', bubble(x, xs))
348.07/291.52	   len(Cons(x, xs)) -> +(S(0), len(xs))
348.07/291.52	   bubble(x', Cons(x, xs)) -> bubble[Ite][False][Ite](<(x', x), x', Cons(x, xs))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   bubble(x, Nil) -> Cons(x, Nil)
348.07/291.52	   bsort(0, xs) -> xs
348.07/291.52	   bubblesort(xs) -> bsort(len(xs), xs)
348.07/291.52	
348.07/291.52	The (relative) TRS S consists of the following rules:
348.07/291.52	
348.07/291.52	   +(x, S(0)) -> S(x)
348.07/291.52	   +(S(0), y) -> S(y)
348.07/291.52	   <(S(x), S(y)) -> <(x, y)
348.07/291.52	   <(0, S(y)) -> True
348.07/291.52	   <(x, 0) -> False
348.07/291.52	   bubble[Ite][False][Ite](False, x', Cons(x, xs)) -> Cons(x, bubble(x', xs))
348.07/291.52	   bubble[Ite][False][Ite](True, x', Cons(x, xs)) -> Cons(x', bubble(x, xs))
348.07/291.52	
348.07/291.52	Rewrite Strategy: INNERMOST
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(3) CpxTrsToCdtProof (UPPER BOUND(ID))
348.07/291.52	Converted Cpx (relative) TRS to CDT
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(4)
348.07/291.52	Obligation:
348.07/291.52	Complexity Dependency Tuples Problem
348.07/291.52	
348.07/291.52	Rules:
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	   <(S(z0), S(z1)) -> <(z0, z1)
348.07/291.52	   <(0, S(z0)) -> True
348.07/291.52	   <(z0, 0) -> False
348.07/291.52	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.07/291.52	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.07/291.52	   bsort(S(z0), Cons(z1, z2)) -> bsort(z0, bubble(z1, z2))
348.07/291.52	   bsort(0, z0) -> z0
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.07/291.52	   bubble(z0, Nil) -> Cons(z0, Nil)
348.07/291.52	   bubblesort(z0) -> bsort(len(z0), z0)
348.07/291.52	Tuples:
348.07/291.52	   +'(z0, S(0)) -> c
348.07/291.52	   +'(S(0), z0) -> c1
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   <'(0, S(z0)) -> c3
348.07/291.52	   <'(z0, 0) -> c4
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BSORT(0, z0) -> c8
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(+'(S(0), len(z1)), LEN(z1))
348.07/291.52	   LEN(Nil) -> c10
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   BUBBLESORT(z0) -> c13(BSORT(len(z0), z0), LEN(z0))
348.07/291.52	S tuples:
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BSORT(0, z0) -> c8
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(+'(S(0), len(z1)), LEN(z1))
348.07/291.52	   LEN(Nil) -> c10
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   BUBBLESORT(z0) -> c13(BSORT(len(z0), z0), LEN(z0))
348.07/291.52	K tuples:none
348.07/291.52	Defined Rule Symbols:   bsort_2, len_1, bubble_2, bubblesort_1, +_2, <_2, bubble[Ite][False][Ite]_3
348.07/291.52	
348.07/291.52	Defined Pair Symbols:   +'_2, <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, LEN_1, BUBBLE_2, BUBBLESORT_1
348.07/291.52	
348.07/291.52	Compound Symbols:   c, c1, c2_1, c3, c4, c5_1, c6_1, c7_2, c8, c9_2, c10, c11_2, c12, c13_2
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
348.07/291.52	Removed 6 trailing nodes:
348.07/291.52	   LEN(Nil) -> c10
348.07/291.52	   <'(z0, 0) -> c4
348.07/291.52	   +'(S(0), z0) -> c1
348.07/291.52	   BSORT(0, z0) -> c8
348.07/291.52	   +'(z0, S(0)) -> c
348.07/291.52	   <'(0, S(z0)) -> c3
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(6)
348.07/291.52	Obligation:
348.07/291.52	Complexity Dependency Tuples Problem
348.07/291.52	
348.07/291.52	Rules:
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	   <(S(z0), S(z1)) -> <(z0, z1)
348.07/291.52	   <(0, S(z0)) -> True
348.07/291.52	   <(z0, 0) -> False
348.07/291.52	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.07/291.52	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.07/291.52	   bsort(S(z0), Cons(z1, z2)) -> bsort(z0, bubble(z1, z2))
348.07/291.52	   bsort(0, z0) -> z0
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.07/291.52	   bubble(z0, Nil) -> Cons(z0, Nil)
348.07/291.52	   bubblesort(z0) -> bsort(len(z0), z0)
348.07/291.52	Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(+'(S(0), len(z1)), LEN(z1))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   BUBBLESORT(z0) -> c13(BSORT(len(z0), z0), LEN(z0))
348.07/291.52	S tuples:
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(+'(S(0), len(z1)), LEN(z1))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   BUBBLESORT(z0) -> c13(BSORT(len(z0), z0), LEN(z0))
348.07/291.52	K tuples:none
348.07/291.52	Defined Rule Symbols:   bsort_2, len_1, bubble_2, bubblesort_1, +_2, <_2, bubble[Ite][False][Ite]_3
348.07/291.52	
348.07/291.52	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, LEN_1, BUBBLE_2, BUBBLESORT_1
348.07/291.52	
348.07/291.52	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c9_2, c11_2, c12, c13_2
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
348.07/291.52	Removed 1 trailing tuple parts
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(8)
348.07/291.52	Obligation:
348.07/291.52	Complexity Dependency Tuples Problem
348.07/291.52	
348.07/291.52	Rules:
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	   <(S(z0), S(z1)) -> <(z0, z1)
348.07/291.52	   <(0, S(z0)) -> True
348.07/291.52	   <(z0, 0) -> False
348.07/291.52	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.07/291.52	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.07/291.52	   bsort(S(z0), Cons(z1, z2)) -> bsort(z0, bubble(z1, z2))
348.07/291.52	   bsort(0, z0) -> z0
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.07/291.52	   bubble(z0, Nil) -> Cons(z0, Nil)
348.07/291.52	   bubblesort(z0) -> bsort(len(z0), z0)
348.07/291.52	Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   BUBBLESORT(z0) -> c13(BSORT(len(z0), z0), LEN(z0))
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	S tuples:
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   BUBBLESORT(z0) -> c13(BSORT(len(z0), z0), LEN(z0))
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	K tuples:none
348.07/291.52	Defined Rule Symbols:   bsort_2, len_1, bubble_2, bubblesort_1, +_2, <_2, bubble[Ite][False][Ite]_3
348.07/291.52	
348.07/291.52	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, BUBBLE_2, BUBBLESORT_1, LEN_1
348.07/291.52	
348.07/291.52	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c11_2, c12, c13_2, c9_1
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(9) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID))
348.07/291.52	Split RHS of tuples not part of any SCC
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(10)
348.07/291.52	Obligation:
348.07/291.52	Complexity Dependency Tuples Problem
348.07/291.52	
348.07/291.52	Rules:
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	   <(S(z0), S(z1)) -> <(z0, z1)
348.07/291.52	   <(0, S(z0)) -> True
348.07/291.52	   <(z0, 0) -> False
348.07/291.52	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.07/291.52	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.07/291.52	   bsort(S(z0), Cons(z1, z2)) -> bsort(z0, bubble(z1, z2))
348.07/291.52	   bsort(0, z0) -> z0
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.07/291.52	   bubble(z0, Nil) -> Cons(z0, Nil)
348.07/291.52	   bubblesort(z0) -> bsort(len(z0), z0)
348.07/291.52	Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	   BUBBLESORT(z0) -> c(LEN(z0))
348.07/291.52	S tuples:
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	   BUBBLESORT(z0) -> c(LEN(z0))
348.07/291.52	K tuples:none
348.07/291.52	Defined Rule Symbols:   bsort_2, len_1, bubble_2, bubblesort_1, +_2, <_2, bubble[Ite][False][Ite]_3
348.07/291.52	
348.07/291.52	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, BUBBLE_2, LEN_1, BUBBLESORT_1
348.07/291.52	
348.07/291.52	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c11_2, c12, c9_1, c_1
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(11) CdtLeafRemovalProof (ComplexityIfPolyImplication)
348.07/291.52	Removed 1 leading nodes:
348.07/291.52	   BUBBLESORT(z0) -> c(LEN(z0))
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(12)
348.07/291.52	Obligation:
348.07/291.52	Complexity Dependency Tuples Problem
348.07/291.52	
348.07/291.52	Rules:
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	   <(S(z0), S(z1)) -> <(z0, z1)
348.07/291.52	   <(0, S(z0)) -> True
348.07/291.52	   <(z0, 0) -> False
348.07/291.52	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.07/291.52	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.07/291.52	   bsort(S(z0), Cons(z1, z2)) -> bsort(z0, bubble(z1, z2))
348.07/291.52	   bsort(0, z0) -> z0
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.07/291.52	   bubble(z0, Nil) -> Cons(z0, Nil)
348.07/291.52	   bubblesort(z0) -> bsort(len(z0), z0)
348.07/291.52	Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	S tuples:
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	K tuples:none
348.07/291.52	Defined Rule Symbols:   bsort_2, len_1, bubble_2, bubblesort_1, +_2, <_2, bubble[Ite][False][Ite]_3
348.07/291.52	
348.07/291.52	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, BUBBLE_2, LEN_1, BUBBLESORT_1
348.07/291.52	
348.07/291.52	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c11_2, c12, c9_1, c_1
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(13) CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
348.07/291.52	The following tuples could be moved from S to K by knowledge propagation:
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(14)
348.07/291.52	Obligation:
348.07/291.52	Complexity Dependency Tuples Problem
348.07/291.52	
348.07/291.52	Rules:
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	   <(S(z0), S(z1)) -> <(z0, z1)
348.07/291.52	   <(0, S(z0)) -> True
348.07/291.52	   <(z0, 0) -> False
348.07/291.52	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.07/291.52	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.07/291.52	   bsort(S(z0), Cons(z1, z2)) -> bsort(z0, bubble(z1, z2))
348.07/291.52	   bsort(0, z0) -> z0
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.07/291.52	   bubble(z0, Nil) -> Cons(z0, Nil)
348.07/291.52	   bubblesort(z0) -> bsort(len(z0), z0)
348.07/291.52	Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	S tuples:
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	K tuples:
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	Defined Rule Symbols:   bsort_2, len_1, bubble_2, bubblesort_1, +_2, <_2, bubble[Ite][False][Ite]_3
348.07/291.52	
348.07/291.52	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, BUBBLE_2, LEN_1, BUBBLESORT_1
348.07/291.52	
348.07/291.52	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c11_2, c12, c9_1, c_1
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(15) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
348.07/291.52	The following rules are not usable and were removed:
348.07/291.52	   bsort(S(z0), Cons(z1, z2)) -> bsort(z0, bubble(z1, z2))
348.07/291.52	   bsort(0, z0) -> z0
348.07/291.52	   bubblesort(z0) -> bsort(len(z0), z0)
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(16)
348.07/291.52	Obligation:
348.07/291.52	Complexity Dependency Tuples Problem
348.07/291.52	
348.07/291.52	Rules:
348.07/291.52	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.07/291.52	   bubble(z0, Nil) -> Cons(z0, Nil)
348.07/291.52	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.07/291.52	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.07/291.52	   <(S(z0), S(z1)) -> <(z0, z1)
348.07/291.52	   <(0, S(z0)) -> True
348.07/291.52	   <(z0, 0) -> False
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	S tuples:
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	K tuples:
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	Defined Rule Symbols:   bubble_2, bubble[Ite][False][Ite]_3, <_2, len_1, +_2
348.07/291.52	
348.07/291.52	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, BUBBLE_2, LEN_1, BUBBLESORT_1
348.07/291.52	
348.07/291.52	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c11_2, c12, c9_1, c_1
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
348.07/291.52	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	We considered the (Usable) Rules:none
348.07/291.52	And the Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	The order we found is given by the following interpretation:
348.07/291.52	
348.07/291.52	Polynomial interpretation :
348.07/291.52	
348.07/291.52	   POL(+(x_1, x_2)) = [1] + x_1 + x_2
348.07/291.52	   POL(0) = 0
348.07/291.52	   POL(<(x_1, x_2)) = [1] + x_2
348.07/291.52	   POL(<'(x_1, x_2)) = 0
348.07/291.52	   POL(BSORT(x_1, x_2)) = [1]
348.07/291.52	   POL(BUBBLE(x_1, x_2)) = 0
348.07/291.52	   POL(BUBBLESORT(x_1)) = [1]
348.07/291.52	   POL(BUBBLE[ITE][FALSE][ITE](x_1, x_2, x_3)) = 0
348.07/291.52	   POL(Cons(x_1, x_2)) = [1] + x_1 + x_2
348.07/291.52	   POL(False) = [1]
348.07/291.52	   POL(LEN(x_1)) = x_1
348.07/291.52	   POL(Nil) = [1]
348.07/291.52	   POL(S(x_1)) = 0
348.07/291.52	   POL(True) = [1]
348.07/291.52	   POL(bubble(x_1, x_2)) = [1] + x_1 + x_2
348.07/291.52	   POL(bubble[Ite][False][Ite](x_1, x_2, x_3)) = [1] + x_2 + x_3
348.07/291.52	   POL(c(x_1)) = x_1
348.07/291.52	   POL(c11(x_1, x_2)) = x_1 + x_2
348.07/291.52	   POL(c12) = 0
348.07/291.52	   POL(c2(x_1)) = x_1
348.07/291.52	   POL(c5(x_1)) = x_1
348.07/291.52	   POL(c6(x_1)) = x_1
348.07/291.52	   POL(c7(x_1, x_2)) = x_1 + x_2
348.07/291.52	   POL(c9(x_1)) = x_1
348.07/291.52	   POL(len(x_1)) = [1] + x_1
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(18)
348.07/291.52	Obligation:
348.07/291.52	Complexity Dependency Tuples Problem
348.07/291.52	
348.07/291.52	Rules:
348.07/291.52	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.07/291.52	   bubble(z0, Nil) -> Cons(z0, Nil)
348.07/291.52	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.07/291.52	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.07/291.52	   <(S(z0), S(z1)) -> <(z0, z1)
348.07/291.52	   <(0, S(z0)) -> True
348.07/291.52	   <(z0, 0) -> False
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	S tuples:
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	K tuples:
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	Defined Rule Symbols:   bubble_2, bubble[Ite][False][Ite]_3, <_2, len_1, +_2
348.07/291.52	
348.07/291.52	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, BUBBLE_2, LEN_1, BUBBLESORT_1
348.07/291.52	
348.07/291.52	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c11_2, c12, c9_1, c_1
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
348.07/291.52	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	We considered the (Usable) Rules:
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	And the Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	The order we found is given by the following interpretation:
348.07/291.52	
348.07/291.52	Polynomial interpretation :
348.07/291.52	
348.07/291.52	   POL(+(x_1, x_2)) = x_1 + x_2
348.07/291.52	   POL(0) = 0
348.07/291.52	   POL(<(x_1, x_2)) = x_1 + x_2
348.07/291.52	   POL(<'(x_1, x_2)) = 0
348.07/291.52	   POL(BSORT(x_1, x_2)) = x_1
348.07/291.52	   POL(BUBBLE(x_1, x_2)) = 0
348.07/291.52	   POL(BUBBLESORT(x_1)) = [1] + x_1
348.07/291.52	   POL(BUBBLE[ITE][FALSE][ITE](x_1, x_2, x_3)) = 0
348.07/291.52	   POL(Cons(x_1, x_2)) = [1] + x_1 + x_2
348.07/291.52	   POL(False) = 0
348.07/291.52	   POL(LEN(x_1)) = x_1
348.07/291.52	   POL(Nil) = 0
348.07/291.52	   POL(S(x_1)) = [1] + x_1
348.07/291.52	   POL(True) = [1]
348.07/291.52	   POL(bubble(x_1, x_2)) = [1] + x_1 + x_2
348.07/291.52	   POL(bubble[Ite][False][Ite](x_1, x_2, x_3)) = [1] + x_2 + x_3
348.07/291.52	   POL(c(x_1)) = x_1
348.07/291.52	   POL(c11(x_1, x_2)) = x_1 + x_2
348.07/291.52	   POL(c12) = 0
348.07/291.52	   POL(c2(x_1)) = x_1
348.07/291.52	   POL(c5(x_1)) = x_1
348.07/291.52	   POL(c6(x_1)) = x_1
348.07/291.52	   POL(c7(x_1, x_2)) = x_1 + x_2
348.07/291.52	   POL(c9(x_1)) = x_1
348.07/291.52	   POL(len(x_1)) = [1] + x_1
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(20)
348.07/291.52	Obligation:
348.07/291.52	Complexity Dependency Tuples Problem
348.07/291.52	
348.07/291.52	Rules:
348.07/291.52	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.07/291.52	   bubble(z0, Nil) -> Cons(z0, Nil)
348.07/291.52	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.07/291.52	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.07/291.52	   <(S(z0), S(z1)) -> <(z0, z1)
348.07/291.52	   <(0, S(z0)) -> True
348.07/291.52	   <(z0, 0) -> False
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	S tuples:
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	K tuples:
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	Defined Rule Symbols:   bubble_2, bubble[Ite][False][Ite]_3, <_2, len_1, +_2
348.07/291.52	
348.07/291.52	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, BUBBLE_2, LEN_1, BUBBLESORT_1
348.07/291.52	
348.07/291.52	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c11_2, c12, c9_1, c_1
348.07/291.52	
348.07/291.52	
348.07/291.52	----------------------------------------
348.07/291.52	
348.07/291.52	(21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
348.07/291.52	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	We considered the (Usable) Rules:
348.07/291.52	   len(Nil) -> 0
348.07/291.52	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.07/291.52	   +(z0, S(0)) -> S(z0)
348.07/291.52	   +(S(0), z0) -> S(z0)
348.07/291.52	And the Tuples:
348.07/291.52	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.07/291.52	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.07/291.52	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.07/291.52	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.07/291.52	   BUBBLE(z0, Nil) -> c12
348.07/291.52	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.07/291.52	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.07/291.52	The order we found is given by the following interpretation:
348.07/291.52	
348.07/291.52	Polynomial interpretation :
348.07/291.52	
348.07/291.52	   POL(+(x_1, x_2)) = x_1 + x_2
348.07/291.52	   POL(0) = 0
348.07/291.52	   POL(<(x_1, x_2)) = 0
348.07/291.52	   POL(<'(x_1, x_2)) = 0
348.13/291.53	   POL(BSORT(x_1, x_2)) = [3] + [2]x_1
348.13/291.53	   POL(BUBBLE(x_1, x_2)) = [1]
348.13/291.53	   POL(BUBBLESORT(x_1)) = [3] + [3]x_1
348.13/291.53	   POL(BUBBLE[ITE][FALSE][ITE](x_1, x_2, x_3)) = [1]
348.13/291.53	   POL(Cons(x_1, x_2)) = [2] + x_2
348.13/291.53	   POL(False) = 0
348.13/291.53	   POL(LEN(x_1)) = [3]x_1
348.13/291.53	   POL(Nil) = 0
348.13/291.53	   POL(S(x_1)) = [2] + x_1
348.13/291.53	   POL(True) = 0
348.13/291.53	   POL(bubble(x_1, x_2)) = [3] + [2]x_1 + [2]x_2
348.13/291.53	   POL(bubble[Ite][False][Ite](x_1, x_2, x_3)) = [3] + [3]x_2
348.13/291.53	   POL(c(x_1)) = x_1
348.13/291.53	   POL(c11(x_1, x_2)) = x_1 + x_2
348.13/291.53	   POL(c12) = 0
348.13/291.53	   POL(c2(x_1)) = x_1
348.13/291.53	   POL(c5(x_1)) = x_1
348.13/291.53	   POL(c6(x_1)) = x_1
348.13/291.53	   POL(c7(x_1, x_2)) = x_1 + x_2
348.13/291.53	   POL(c9(x_1)) = x_1
348.13/291.53	   POL(len(x_1)) = x_1
348.13/291.53	
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(22)
348.13/291.53	Obligation:
348.13/291.53	Complexity Dependency Tuples Problem
348.13/291.53	
348.13/291.53	Rules:
348.13/291.53	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.13/291.53	   bubble(z0, Nil) -> Cons(z0, Nil)
348.13/291.53	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.13/291.53	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.13/291.53	   <(S(z0), S(z1)) -> <(z0, z1)
348.13/291.53	   <(0, S(z0)) -> True
348.13/291.53	   <(z0, 0) -> False
348.13/291.53	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.13/291.53	   len(Nil) -> 0
348.13/291.53	   +(z0, S(0)) -> S(z0)
348.13/291.53	   +(S(0), z0) -> S(z0)
348.13/291.53	Tuples:
348.13/291.53	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.13/291.53	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.13/291.53	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.13/291.53	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.13/291.53	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.13/291.53	   BUBBLE(z0, Nil) -> c12
348.13/291.53	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.13/291.53	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.13/291.53	S tuples:
348.13/291.53	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.13/291.53	K tuples:
348.13/291.53	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.13/291.53	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.13/291.53	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.13/291.53	   BUBBLE(z0, Nil) -> c12
348.13/291.53	Defined Rule Symbols:   bubble_2, bubble[Ite][False][Ite]_3, <_2, len_1, +_2
348.13/291.53	
348.13/291.53	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, BUBBLE_2, LEN_1, BUBBLESORT_1
348.13/291.53	
348.13/291.53	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c11_2, c12, c9_1, c_1
348.13/291.53	
348.13/291.53	
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(23) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
348.13/291.53	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
348.13/291.53	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.13/291.53	We considered the (Usable) Rules:
348.13/291.53	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.13/291.53	   len(Nil) -> 0
348.13/291.53	   bubble(z0, Nil) -> Cons(z0, Nil)
348.13/291.53	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.13/291.53	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.13/291.53	   +(z0, S(0)) -> S(z0)
348.13/291.53	   +(S(0), z0) -> S(z0)
348.13/291.53	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.13/291.53	And the Tuples:
348.13/291.53	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.13/291.53	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.13/291.53	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.13/291.53	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.13/291.53	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.13/291.53	   BUBBLE(z0, Nil) -> c12
348.13/291.53	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.13/291.53	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.13/291.53	The order we found is given by the following interpretation:
348.13/291.53	
348.13/291.53	Polynomial interpretation :
348.13/291.53	
348.13/291.53	   POL(+(x_1, x_2)) = x_1 + x_2
348.13/291.53	   POL(0) = 0
348.13/291.53	   POL(<(x_1, x_2)) = 0
348.13/291.53	   POL(<'(x_1, x_2)) = 0
348.13/291.53	   POL(BSORT(x_1, x_2)) = [2]x_1 + [2]x_1*x_2
348.13/291.53	   POL(BUBBLE(x_1, x_2)) = [2] + [2]x_2
348.13/291.53	   POL(BUBBLESORT(x_1)) = [2] + [2]x_1 + [2]x_1^2
348.13/291.53	   POL(BUBBLE[ITE][FALSE][ITE](x_1, x_2, x_3)) = [2]x_3
348.13/291.53	   POL(Cons(x_1, x_2)) = [1] + x_2
348.13/291.53	   POL(False) = 0
348.13/291.53	   POL(LEN(x_1)) = [2]x_1 + x_1^2
348.13/291.53	   POL(Nil) = 0
348.13/291.53	   POL(S(x_1)) = [1] + x_1
348.13/291.53	   POL(True) = 0
348.13/291.53	   POL(bubble(x_1, x_2)) = [1] + x_2
348.13/291.53	   POL(bubble[Ite][False][Ite](x_1, x_2, x_3)) = [1] + x_3
348.13/291.53	   POL(c(x_1)) = x_1
348.13/291.53	   POL(c11(x_1, x_2)) = x_1 + x_2
348.13/291.53	   POL(c12) = 0
348.13/291.53	   POL(c2(x_1)) = x_1
348.13/291.53	   POL(c5(x_1)) = x_1
348.13/291.53	   POL(c6(x_1)) = x_1
348.13/291.53	   POL(c7(x_1, x_2)) = x_1 + x_2
348.13/291.53	   POL(c9(x_1)) = x_1
348.13/291.53	   POL(len(x_1)) = x_1
348.13/291.53	
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(24)
348.13/291.53	Obligation:
348.13/291.53	Complexity Dependency Tuples Problem
348.13/291.53	
348.13/291.53	Rules:
348.13/291.53	   bubble(z0, Cons(z1, z2)) -> bubble[Ite][False][Ite](<(z0, z1), z0, Cons(z1, z2))
348.13/291.53	   bubble(z0, Nil) -> Cons(z0, Nil)
348.13/291.53	   bubble[Ite][False][Ite](False, z0, Cons(z1, z2)) -> Cons(z1, bubble(z0, z2))
348.13/291.53	   bubble[Ite][False][Ite](True, z0, Cons(z1, z2)) -> Cons(z0, bubble(z1, z2))
348.13/291.53	   <(S(z0), S(z1)) -> <(z0, z1)
348.13/291.53	   <(0, S(z0)) -> True
348.13/291.53	   <(z0, 0) -> False
348.13/291.53	   len(Cons(z0, z1)) -> +(S(0), len(z1))
348.13/291.53	   len(Nil) -> 0
348.13/291.53	   +(z0, S(0)) -> S(z0)
348.13/291.53	   +(S(0), z0) -> S(z0)
348.13/291.53	Tuples:
348.13/291.53	   <'(S(z0), S(z1)) -> c2(<'(z0, z1))
348.13/291.53	   BUBBLE[ITE][FALSE][ITE](False, z0, Cons(z1, z2)) -> c5(BUBBLE(z0, z2))
348.13/291.53	   BUBBLE[ITE][FALSE][ITE](True, z0, Cons(z1, z2)) -> c6(BUBBLE(z1, z2))
348.13/291.53	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.13/291.53	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.13/291.53	   BUBBLE(z0, Nil) -> c12
348.13/291.53	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.13/291.53	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.13/291.53	S tuples:none
348.13/291.53	K tuples:
348.13/291.53	   BUBBLESORT(z0) -> c(BSORT(len(z0), z0))
348.13/291.53	   LEN(Cons(z0, z1)) -> c9(LEN(z1))
348.13/291.53	   BSORT(S(z0), Cons(z1, z2)) -> c7(BSORT(z0, bubble(z1, z2)), BUBBLE(z1, z2))
348.13/291.53	   BUBBLE(z0, Nil) -> c12
348.13/291.53	   BUBBLE(z0, Cons(z1, z2)) -> c11(BUBBLE[ITE][FALSE][ITE](<(z0, z1), z0, Cons(z1, z2)), <'(z0, z1))
348.13/291.53	Defined Rule Symbols:   bubble_2, bubble[Ite][False][Ite]_3, <_2, len_1, +_2
348.13/291.53	
348.13/291.53	Defined Pair Symbols:   <'_2, BUBBLE[ITE][FALSE][ITE]_3, BSORT_2, BUBBLE_2, LEN_1, BUBBLESORT_1
348.13/291.53	
348.13/291.53	Compound Symbols:   c2_1, c5_1, c6_1, c7_2, c11_2, c12, c9_1, c_1
348.13/291.53	
348.13/291.53	
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(25) SIsEmptyProof (BOTH BOUNDS(ID, ID))
348.13/291.53	The set S is empty
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(26)
348.13/291.53	BOUNDS(1, 1)
348.13/291.53	
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(27) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
348.13/291.53	Transformed a relative TRS into a decreasing-loop problem.
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(28)
348.13/291.53	Obligation:
348.13/291.53	Analyzing the following TRS for decreasing loops:
348.13/291.53	
348.13/291.53	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
348.13/291.53	
348.13/291.53	
348.13/291.53	The TRS R consists of the following rules:
348.13/291.53	
348.13/291.53	   bsort(S(x'), Cons(x, xs)) -> bsort(x', bubble(x, xs))
348.13/291.53	   len(Cons(x, xs)) -> +(S(0), len(xs))
348.13/291.53	   bubble(x', Cons(x, xs)) -> bubble[Ite][False][Ite](<(x', x), x', Cons(x, xs))
348.13/291.53	   len(Nil) -> 0
348.13/291.53	   bubble(x, Nil) -> Cons(x, Nil)
348.13/291.53	   bsort(0, xs) -> xs
348.13/291.53	   bubblesort(xs) -> bsort(len(xs), xs)
348.13/291.53	
348.13/291.53	The (relative) TRS S consists of the following rules:
348.13/291.53	
348.13/291.53	   +(x, S(0)) -> S(x)
348.13/291.53	   +(S(0), y) -> S(y)
348.13/291.53	   <(S(x), S(y)) -> <(x, y)
348.13/291.53	   <(0, S(y)) -> True
348.13/291.53	   <(x, 0) -> False
348.13/291.53	   bubble[Ite][False][Ite](False, x', Cons(x, xs)) -> Cons(x, bubble(x', xs))
348.13/291.53	   bubble[Ite][False][Ite](True, x', Cons(x, xs)) -> Cons(x', bubble(x, xs))
348.13/291.53	
348.13/291.53	Rewrite Strategy: INNERMOST
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(29) DecreasingLoopProof (LOWER BOUND(ID))
348.13/291.53	The following loop(s) give(s) rise to the lower bound Omega(n^1):
348.13/291.53	
348.13/291.53	The rewrite sequence
348.13/291.53	
348.13/291.53	len(Cons(x, xs)) ->^+ +(S(0), len(xs))
348.13/291.53	
348.13/291.53	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
348.13/291.53	
348.13/291.53	The pumping substitution is [xs / Cons(x, xs)].
348.13/291.53	
348.13/291.53	The result substitution is [ ].
348.13/291.53	
348.13/291.53	
348.13/291.53	
348.13/291.53	
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(30)
348.13/291.53	Complex Obligation (BEST)
348.13/291.53	
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(31)
348.13/291.53	Obligation:
348.13/291.53	Proved the lower bound n^1 for the following obligation:
348.13/291.53	
348.13/291.53	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
348.13/291.53	
348.13/291.53	
348.13/291.53	The TRS R consists of the following rules:
348.13/291.53	
348.13/291.53	   bsort(S(x'), Cons(x, xs)) -> bsort(x', bubble(x, xs))
348.13/291.53	   len(Cons(x, xs)) -> +(S(0), len(xs))
348.13/291.53	   bubble(x', Cons(x, xs)) -> bubble[Ite][False][Ite](<(x', x), x', Cons(x, xs))
348.13/291.53	   len(Nil) -> 0
348.13/291.53	   bubble(x, Nil) -> Cons(x, Nil)
348.13/291.53	   bsort(0, xs) -> xs
348.13/291.53	   bubblesort(xs) -> bsort(len(xs), xs)
348.13/291.53	
348.13/291.53	The (relative) TRS S consists of the following rules:
348.13/291.53	
348.13/291.53	   +(x, S(0)) -> S(x)
348.13/291.53	   +(S(0), y) -> S(y)
348.13/291.53	   <(S(x), S(y)) -> <(x, y)
348.13/291.53	   <(0, S(y)) -> True
348.13/291.53	   <(x, 0) -> False
348.13/291.53	   bubble[Ite][False][Ite](False, x', Cons(x, xs)) -> Cons(x, bubble(x', xs))
348.13/291.53	   bubble[Ite][False][Ite](True, x', Cons(x, xs)) -> Cons(x', bubble(x, xs))
348.13/291.53	
348.13/291.53	Rewrite Strategy: INNERMOST
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(32) LowerBoundPropagationProof (FINISHED)
348.13/291.53	Propagated lower bound.
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(33)
348.13/291.53	BOUNDS(n^1, INF)
348.13/291.53	
348.13/291.53	----------------------------------------
348.13/291.53	
348.13/291.53	(34)
348.13/291.53	Obligation:
348.13/291.53	Analyzing the following TRS for decreasing loops:
348.13/291.53	
348.13/291.53	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).
348.13/291.53	
348.13/291.53	
348.13/291.53	The TRS R consists of the following rules:
348.13/291.53	
348.13/291.53	   bsort(S(x'), Cons(x, xs)) -> bsort(x', bubble(x, xs))
348.13/291.53	   len(Cons(x, xs)) -> +(S(0), len(xs))
348.13/291.53	   bubble(x', Cons(x, xs)) -> bubble[Ite][False][Ite](<(x', x), x', Cons(x, xs))
348.13/291.53	   len(Nil) -> 0
348.13/291.53	   bubble(x, Nil) -> Cons(x, Nil)
348.13/291.53	   bsort(0, xs) -> xs
348.13/291.53	   bubblesort(xs) -> bsort(len(xs), xs)
348.13/291.53	
348.13/291.53	The (relative) TRS S consists of the following rules:
348.13/291.53	
348.13/291.53	   +(x, S(0)) -> S(x)
348.13/291.53	   +(S(0), y) -> S(y)
348.13/291.53	   <(S(x), S(y)) -> <(x, y)
348.13/291.53	   <(0, S(y)) -> True
348.13/291.53	   <(x, 0) -> False
348.13/291.53	   bubble[Ite][False][Ite](False, x', Cons(x, xs)) -> Cons(x, bubble(x', xs))
348.13/291.53	   bubble[Ite][False][Ite](True, x', Cons(x, xs)) -> Cons(x', bubble(x, xs))
348.13/291.53	
348.13/291.53	Rewrite Strategy: INNERMOST
348.13/291.57	EOF