1047.16/291.75	WORST_CASE(Omega(n^1), ?)
1047.16/291.76	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
1047.16/291.76	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1047.16/291.76	
1047.16/291.76	(0) CpxRelTRS
1047.16/291.76	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 209 ms]
1047.16/291.76	(2) CpxRelTRS
1047.16/291.76	(3) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
1047.16/291.76	(4) TRS for Loop Detection
1047.16/291.76	(5) DecreasingLoopProof [LOWER BOUND(ID), 137 ms]
1047.16/291.76	(6) BEST
1047.16/291.76	    (7) proven lower bound
1047.16/291.76	        (8) LowerBoundPropagationProof [FINISHED, 0 ms]
1047.16/291.76	        (9) BOUNDS(n^1, INF)
1047.16/291.76	    (10) TRS for Loop Detection
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(0)
1047.16/291.76	Obligation:
1047.16/291.76	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	The TRS R consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #less(@x, @y) -> #cklt(#compare(@x, @y))
1047.16/291.76	   merge(@l1, @l2) -> merge#1(@l1, @l2)
1047.16/291.76	   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
1047.16/291.76	   merge#1(nil, @l2) -> @l2
1047.16/291.76	   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
1047.16/291.76	   merge#2(nil, @x, @xs) -> ::(@x, @xs)
1047.16/291.76	   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
1047.16/291.76	   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
1047.16/291.76	   mergesort(@l) -> mergesort#1(@l)
1047.16/291.76	   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
1047.16/291.76	   mergesort#1(nil) -> nil
1047.16/291.76	   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
1047.16/291.76	   mergesort#2(nil, @x1) -> ::(@x1, nil)
1047.16/291.76	   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
1047.16/291.76	   msplit(@l) -> msplit#1(@l)
1047.16/291.76	   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
1047.16/291.76	   msplit#1(nil) -> tuple#2(nil, nil)
1047.16/291.76	   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
1047.16/291.76	   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
1047.16/291.76	   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
1047.16/291.76	
1047.16/291.76	The (relative) TRS S consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #cklt(#EQ) -> #false
1047.16/291.76	   #cklt(#GT) -> #false
1047.16/291.76	   #cklt(#LT) -> #true
1047.16/291.76	   #compare(#0, #0) -> #EQ
1047.16/291.76	   #compare(#0, #neg(@y)) -> #GT
1047.16/291.76	   #compare(#0, #pos(@y)) -> #LT
1047.16/291.76	   #compare(#0, #s(@y)) -> #LT
1047.16/291.76	   #compare(#neg(@x), #0) -> #LT
1047.16/291.76	   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
1047.16/291.76	   #compare(#neg(@x), #pos(@y)) -> #LT
1047.16/291.76	   #compare(#pos(@x), #0) -> #GT
1047.16/291.76	   #compare(#pos(@x), #neg(@y)) -> #GT
1047.16/291.76	   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
1047.16/291.76	   #compare(#s(@x), #0) -> #GT
1047.16/291.76	   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)
1047.16/291.76	
1047.16/291.76	Rewrite Strategy: INNERMOST
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
1047.16/291.76	proved termination of relative rules
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(2)
1047.16/291.76	Obligation:
1047.16/291.76	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	The TRS R consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #less(@x, @y) -> #cklt(#compare(@x, @y))
1047.16/291.76	   merge(@l1, @l2) -> merge#1(@l1, @l2)
1047.16/291.76	   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
1047.16/291.76	   merge#1(nil, @l2) -> @l2
1047.16/291.76	   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
1047.16/291.76	   merge#2(nil, @x, @xs) -> ::(@x, @xs)
1047.16/291.76	   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
1047.16/291.76	   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
1047.16/291.76	   mergesort(@l) -> mergesort#1(@l)
1047.16/291.76	   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
1047.16/291.76	   mergesort#1(nil) -> nil
1047.16/291.76	   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
1047.16/291.76	   mergesort#2(nil, @x1) -> ::(@x1, nil)
1047.16/291.76	   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
1047.16/291.76	   msplit(@l) -> msplit#1(@l)
1047.16/291.76	   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
1047.16/291.76	   msplit#1(nil) -> tuple#2(nil, nil)
1047.16/291.76	   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
1047.16/291.76	   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
1047.16/291.76	   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
1047.16/291.76	
1047.16/291.76	The (relative) TRS S consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #cklt(#EQ) -> #false
1047.16/291.76	   #cklt(#GT) -> #false
1047.16/291.76	   #cklt(#LT) -> #true
1047.16/291.76	   #compare(#0, #0) -> #EQ
1047.16/291.76	   #compare(#0, #neg(@y)) -> #GT
1047.16/291.76	   #compare(#0, #pos(@y)) -> #LT
1047.16/291.76	   #compare(#0, #s(@y)) -> #LT
1047.16/291.76	   #compare(#neg(@x), #0) -> #LT
1047.16/291.76	   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
1047.16/291.76	   #compare(#neg(@x), #pos(@y)) -> #LT
1047.16/291.76	   #compare(#pos(@x), #0) -> #GT
1047.16/291.76	   #compare(#pos(@x), #neg(@y)) -> #GT
1047.16/291.76	   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
1047.16/291.76	   #compare(#s(@x), #0) -> #GT
1047.16/291.76	   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)
1047.16/291.76	
1047.16/291.76	Rewrite Strategy: INNERMOST
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(3) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
1047.16/291.76	Transformed a relative TRS into a decreasing-loop problem.
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(4)
1047.16/291.76	Obligation:
1047.16/291.76	Analyzing the following TRS for decreasing loops:
1047.16/291.76	
1047.16/291.76	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	The TRS R consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #less(@x, @y) -> #cklt(#compare(@x, @y))
1047.16/291.76	   merge(@l1, @l2) -> merge#1(@l1, @l2)
1047.16/291.76	   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
1047.16/291.76	   merge#1(nil, @l2) -> @l2
1047.16/291.76	   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
1047.16/291.76	   merge#2(nil, @x, @xs) -> ::(@x, @xs)
1047.16/291.76	   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
1047.16/291.76	   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
1047.16/291.76	   mergesort(@l) -> mergesort#1(@l)
1047.16/291.76	   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
1047.16/291.76	   mergesort#1(nil) -> nil
1047.16/291.76	   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
1047.16/291.76	   mergesort#2(nil, @x1) -> ::(@x1, nil)
1047.16/291.76	   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
1047.16/291.76	   msplit(@l) -> msplit#1(@l)
1047.16/291.76	   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
1047.16/291.76	   msplit#1(nil) -> tuple#2(nil, nil)
1047.16/291.76	   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
1047.16/291.76	   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
1047.16/291.76	   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
1047.16/291.76	
1047.16/291.76	The (relative) TRS S consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #cklt(#EQ) -> #false
1047.16/291.76	   #cklt(#GT) -> #false
1047.16/291.76	   #cklt(#LT) -> #true
1047.16/291.76	   #compare(#0, #0) -> #EQ
1047.16/291.76	   #compare(#0, #neg(@y)) -> #GT
1047.16/291.76	   #compare(#0, #pos(@y)) -> #LT
1047.16/291.76	   #compare(#0, #s(@y)) -> #LT
1047.16/291.76	   #compare(#neg(@x), #0) -> #LT
1047.16/291.76	   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
1047.16/291.76	   #compare(#neg(@x), #pos(@y)) -> #LT
1047.16/291.76	   #compare(#pos(@x), #0) -> #GT
1047.16/291.76	   #compare(#pos(@x), #neg(@y)) -> #GT
1047.16/291.76	   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
1047.16/291.76	   #compare(#s(@x), #0) -> #GT
1047.16/291.76	   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)
1047.16/291.76	
1047.16/291.76	Rewrite Strategy: INNERMOST
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(5) DecreasingLoopProof (LOWER BOUND(ID))
1047.16/291.76	The following loop(s) give(s) rise to the lower bound Omega(n^1):
1047.16/291.76	
1047.16/291.76	The rewrite sequence
1047.16/291.76	
1047.16/291.76	msplit#2(::(@x2, ::(@x11_0, @xs2_0)), @x1) ->^+ msplit#3(msplit#2(@xs2_0, @x11_0), @x1, @x2)
1047.16/291.76	
1047.16/291.76	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
1047.16/291.76	
1047.16/291.76	The pumping substitution is [@xs2_0 / ::(@x2, ::(@x11_0, @xs2_0))].
1047.16/291.76	
1047.16/291.76	The result substitution is [@x1 / @x11_0].
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(6)
1047.16/291.76	Complex Obligation (BEST)
1047.16/291.76	
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(7)
1047.16/291.76	Obligation:
1047.16/291.76	Proved the lower bound n^1 for the following obligation:
1047.16/291.76	
1047.16/291.76	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	The TRS R consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #less(@x, @y) -> #cklt(#compare(@x, @y))
1047.16/291.76	   merge(@l1, @l2) -> merge#1(@l1, @l2)
1047.16/291.76	   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
1047.16/291.76	   merge#1(nil, @l2) -> @l2
1047.16/291.76	   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
1047.16/291.76	   merge#2(nil, @x, @xs) -> ::(@x, @xs)
1047.16/291.76	   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
1047.16/291.76	   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
1047.16/291.76	   mergesort(@l) -> mergesort#1(@l)
1047.16/291.76	   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
1047.16/291.76	   mergesort#1(nil) -> nil
1047.16/291.76	   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
1047.16/291.76	   mergesort#2(nil, @x1) -> ::(@x1, nil)
1047.16/291.76	   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
1047.16/291.76	   msplit(@l) -> msplit#1(@l)
1047.16/291.76	   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
1047.16/291.76	   msplit#1(nil) -> tuple#2(nil, nil)
1047.16/291.76	   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
1047.16/291.76	   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
1047.16/291.76	   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
1047.16/291.76	
1047.16/291.76	The (relative) TRS S consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #cklt(#EQ) -> #false
1047.16/291.76	   #cklt(#GT) -> #false
1047.16/291.76	   #cklt(#LT) -> #true
1047.16/291.76	   #compare(#0, #0) -> #EQ
1047.16/291.76	   #compare(#0, #neg(@y)) -> #GT
1047.16/291.76	   #compare(#0, #pos(@y)) -> #LT
1047.16/291.76	   #compare(#0, #s(@y)) -> #LT
1047.16/291.76	   #compare(#neg(@x), #0) -> #LT
1047.16/291.76	   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
1047.16/291.76	   #compare(#neg(@x), #pos(@y)) -> #LT
1047.16/291.76	   #compare(#pos(@x), #0) -> #GT
1047.16/291.76	   #compare(#pos(@x), #neg(@y)) -> #GT
1047.16/291.76	   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
1047.16/291.76	   #compare(#s(@x), #0) -> #GT
1047.16/291.76	   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)
1047.16/291.76	
1047.16/291.76	Rewrite Strategy: INNERMOST
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(8) LowerBoundPropagationProof (FINISHED)
1047.16/291.76	Propagated lower bound.
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(9)
1047.16/291.76	BOUNDS(n^1, INF)
1047.16/291.76	
1047.16/291.76	----------------------------------------
1047.16/291.76	
1047.16/291.76	(10)
1047.16/291.76	Obligation:
1047.16/291.76	Analyzing the following TRS for decreasing loops:
1047.16/291.76	
1047.16/291.76	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1047.16/291.76	
1047.16/291.76	
1047.16/291.76	The TRS R consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #less(@x, @y) -> #cklt(#compare(@x, @y))
1047.16/291.76	   merge(@l1, @l2) -> merge#1(@l1, @l2)
1047.16/291.76	   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
1047.16/291.76	   merge#1(nil, @l2) -> @l2
1047.16/291.76	   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
1047.16/291.76	   merge#2(nil, @x, @xs) -> ::(@x, @xs)
1047.16/291.76	   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
1047.16/291.76	   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
1047.16/291.76	   mergesort(@l) -> mergesort#1(@l)
1047.16/291.76	   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
1047.16/291.76	   mergesort#1(nil) -> nil
1047.16/291.76	   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
1047.16/291.76	   mergesort#2(nil, @x1) -> ::(@x1, nil)
1047.16/291.76	   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
1047.16/291.76	   msplit(@l) -> msplit#1(@l)
1047.16/291.76	   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
1047.16/291.76	   msplit#1(nil) -> tuple#2(nil, nil)
1047.16/291.76	   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
1047.16/291.76	   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
1047.16/291.76	   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
1047.16/291.76	
1047.16/291.76	The (relative) TRS S consists of the following rules:
1047.16/291.76	
1047.16/291.76	   #cklt(#EQ) -> #false
1047.16/291.76	   #cklt(#GT) -> #false
1047.16/291.76	   #cklt(#LT) -> #true
1047.16/291.76	   #compare(#0, #0) -> #EQ
1047.16/291.76	   #compare(#0, #neg(@y)) -> #GT
1047.16/291.76	   #compare(#0, #pos(@y)) -> #LT
1047.16/291.76	   #compare(#0, #s(@y)) -> #LT
1047.16/291.76	   #compare(#neg(@x), #0) -> #LT
1047.16/291.76	   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
1047.16/291.76	   #compare(#neg(@x), #pos(@y)) -> #LT
1047.16/291.76	   #compare(#pos(@x), #0) -> #GT
1047.16/291.76	   #compare(#pos(@x), #neg(@y)) -> #GT
1047.16/291.76	   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
1047.16/291.76	   #compare(#s(@x), #0) -> #GT
1047.16/291.76	   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)
1047.16/291.76	
1047.16/291.76	Rewrite Strategy: INNERMOST
1047.32/291.83	EOF