/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


WORST_CASE(Omega(n^1), ?)
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).

(0) CpxRelTRS
(1) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 198 ms]
(2) CpxRelTRS
(3) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(4) TRS for Loop Detection
(5) DecreasingLoopProof [LOWER BOUND(ID), 122 ms]
(6) BEST
    (7) proven lower bound
        (8) LowerBoundPropagationProof [FINISHED, 0 ms]
        (9) BOUNDS(n^1, INF)
    (10) TRS for Loop Detection


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

(0)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   merge(@l1, @l2) -> merge#1(@l1, @l2)
   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
   merge#1(nil, @l2) -> @l2
   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
   merge#2(nil, @x, @xs) -> ::(@x, @xs)
   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
   mergesort(@l) -> mergesort#1(@l)
   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
   mergesort#1(nil) -> nil
   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
   mergesort#2(nil, @x1) -> ::(@x1, nil)
   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
   msplit(@l) -> msplit#1(@l)
   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
   msplit#1(nil) -> tuple#2(nil, nil)
   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))

The (relative) TRS S consists of the following rules:

   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(@y)) -> #GT
   #compare(#0, #pos(@y)) -> #LT
   #compare(#0, #s(@y)) -> #LT
   #compare(#neg(@x), #0) -> #LT
   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
   #compare(#neg(@x), #pos(@y)) -> #LT
   #compare(#pos(@x), #0) -> #GT
   #compare(#pos(@x), #neg(@y)) -> #GT
   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
   #compare(#s(@x), #0) -> #GT
   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Rewrite Strategy: INNERMOST
----------------------------------------

(1) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

(2)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   merge(@l1, @l2) -> merge#1(@l1, @l2)
   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
   merge#1(nil, @l2) -> @l2
   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
   merge#2(nil, @x, @xs) -> ::(@x, @xs)
   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
   mergesort(@l) -> mergesort#1(@l)
   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
   mergesort#1(nil) -> nil
   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
   mergesort#2(nil, @x1) -> ::(@x1, nil)
   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
   msplit(@l) -> msplit#1(@l)
   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
   msplit#1(nil) -> tuple#2(nil, nil)
   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))

The (relative) TRS S consists of the following rules:

   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(@y)) -> #GT
   #compare(#0, #pos(@y)) -> #LT
   #compare(#0, #s(@y)) -> #LT
   #compare(#neg(@x), #0) -> #LT
   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
   #compare(#neg(@x), #pos(@y)) -> #LT
   #compare(#pos(@x), #0) -> #GT
   #compare(#pos(@x), #neg(@y)) -> #GT
   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
   #compare(#s(@x), #0) -> #GT
   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Rewrite Strategy: INNERMOST
----------------------------------------

(3) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

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

The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   merge(@l1, @l2) -> merge#1(@l1, @l2)
   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
   merge#1(nil, @l2) -> @l2
   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
   merge#2(nil, @x, @xs) -> ::(@x, @xs)
   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
   mergesort(@l) -> mergesort#1(@l)
   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
   mergesort#1(nil) -> nil
   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
   mergesort#2(nil, @x1) -> ::(@x1, nil)
   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
   msplit(@l) -> msplit#1(@l)
   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
   msplit#1(nil) -> tuple#2(nil, nil)
   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))

The (relative) TRS S consists of the following rules:

   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(@y)) -> #GT
   #compare(#0, #pos(@y)) -> #LT
   #compare(#0, #s(@y)) -> #LT
   #compare(#neg(@x), #0) -> #LT
   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
   #compare(#neg(@x), #pos(@y)) -> #LT
   #compare(#pos(@x), #0) -> #GT
   #compare(#pos(@x), #neg(@y)) -> #GT
   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
   #compare(#s(@x), #0) -> #GT
   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Rewrite Strategy: INNERMOST
----------------------------------------

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

The rewrite sequence

msplit#2(::(@x2, ::(@x11_0, @xs2_0)), @x1) ->^+ msplit#3(msplit#2(@xs2_0, @x11_0), @x1, @x2)

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

The pumping substitution is [@xs2_0 / ::(@x2, ::(@x11_0, @xs2_0))].

The result substitution is [@x1 / @x11_0].




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

(6)
Complex Obligation (BEST)

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

(7)
Obligation:
Proved the lower bound n^1 for the following obligation:

The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   merge(@l1, @l2) -> merge#1(@l1, @l2)
   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
   merge#1(nil, @l2) -> @l2
   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
   merge#2(nil, @x, @xs) -> ::(@x, @xs)
   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
   mergesort(@l) -> mergesort#1(@l)
   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
   mergesort#1(nil) -> nil
   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
   mergesort#2(nil, @x1) -> ::(@x1, nil)
   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
   msplit(@l) -> msplit#1(@l)
   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
   msplit#1(nil) -> tuple#2(nil, nil)
   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))

The (relative) TRS S consists of the following rules:

   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(@y)) -> #GT
   #compare(#0, #pos(@y)) -> #LT
   #compare(#0, #s(@y)) -> #LT
   #compare(#neg(@x), #0) -> #LT
   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
   #compare(#neg(@x), #pos(@y)) -> #LT
   #compare(#pos(@x), #0) -> #GT
   #compare(#pos(@x), #neg(@y)) -> #GT
   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
   #compare(#s(@x), #0) -> #GT
   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Rewrite Strategy: INNERMOST
----------------------------------------

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

(9)
BOUNDS(n^1, INF)

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

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

The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   merge(@l1, @l2) -> merge#1(@l1, @l2)
   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
   merge#1(nil, @l2) -> @l2
   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
   merge#2(nil, @x, @xs) -> ::(@x, @xs)
   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
   mergesort(@l) -> mergesort#1(@l)
   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
   mergesort#1(nil) -> nil
   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
   mergesort#2(nil, @x1) -> ::(@x1, nil)
   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
   msplit(@l) -> msplit#1(@l)
   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
   msplit#1(nil) -> tuple#2(nil, nil)
   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))

The (relative) TRS S consists of the following rules:

   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(@y)) -> #GT
   #compare(#0, #pos(@y)) -> #LT
   #compare(#0, #s(@y)) -> #LT
   #compare(#neg(@x), #0) -> #LT
   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
   #compare(#neg(@x), #pos(@y)) -> #LT
   #compare(#pos(@x), #0) -> #GT
   #compare(#pos(@x), #neg(@y)) -> #GT
   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
   #compare(#s(@x), #0) -> #GT
   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Rewrite Strategy: INNERMOST