/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), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) CpxRelTRS
(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 179 ms]
(2) CpxRelTRS
(3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
(4) CdtProblem
    (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CdtProblem
    (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CdtProblem
    (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CdtProblem
    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 113 ms]
    (12) CdtProblem
    (13) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) CdtProblem
    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 203 ms]
    (16) CdtProblem
    (17) CdtKnowledgeProof [FINISHED, 0 ms]
    (18) BOUNDS(1, 1)
(19) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(20) TRS for Loop Detection
    (21) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (22) BEST
        (23) proven lower bound
            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
            (25) BOUNDS(n^1, INF)
        (26) TRS for Loop Detection


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

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


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   findMin(@l) -> findMin#1(@l)
   findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x)
   findMin#1(nil) -> nil
   findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys)
   findMin#2(nil, @x) -> ::(@x, nil)
   findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys))
   findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys))
   minSort(@l) -> minSort#1(findMin(@l))
   minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs))
   minSort#1(nil) -> nil

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) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved termination of relative rules
----------------------------------------

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


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   findMin(@l) -> findMin#1(@l)
   findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x)
   findMin#1(nil) -> nil
   findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys)
   findMin#2(nil, @x) -> ::(@x, nil)
   findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys))
   findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys))
   minSort(@l) -> minSort#1(findMin(@l))
   minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs))
   minSort#1(nil) -> nil

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) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(4)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(z0)) -> #GT
   #compare(#0, #pos(z0)) -> #LT
   #compare(#0, #s(z0)) -> #LT
   #compare(#neg(z0), #0) -> #LT
   #compare(#neg(z0), #neg(z1)) -> #compare(z1, z0)
   #compare(#neg(z0), #pos(z1)) -> #LT
   #compare(#pos(z0), #0) -> #GT
   #compare(#pos(z0), #neg(z1)) -> #GT
   #compare(#pos(z0), #pos(z1)) -> #compare(z0, z1)
   #compare(#s(z0), #0) -> #GT
   #compare(#s(z0), #s(z1)) -> #compare(z0, z1)
   #less(z0, z1) -> #cklt(#compare(z0, z1))
   findMin(z0) -> findMin#1(z0)
   findMin#1(::(z0, z1)) -> findMin#2(findMin(z1), z0)
   findMin#1(nil) -> nil
   findMin#2(::(z0, z1), z2) -> findMin#3(#less(z2, z0), z2, z0, z1)
   findMin#2(nil, z0) -> ::(z0, nil)
   findMin#3(#false, z0, z1, z2) -> ::(z1, ::(z0, z2))
   findMin#3(#true, z0, z1, z2) -> ::(z0, ::(z1, z2))
   minSort(z0) -> minSort#1(findMin(z0))
   minSort#1(::(z0, z1)) -> ::(z0, minSort(z1))
   minSort#1(nil) -> nil
Tuples:
   #CKLT(#EQ) -> c
   #CKLT(#GT) -> c1
   #CKLT(#LT) -> c2
   #COMPARE(#0, #0) -> c3
   #COMPARE(#0, #neg(z0)) -> c4
   #COMPARE(#0, #pos(z0)) -> c5
   #COMPARE(#0, #s(z0)) -> c6
   #COMPARE(#neg(z0), #0) -> c7
   #COMPARE(#neg(z0), #neg(z1)) -> c8(#COMPARE(z1, z0))
   #COMPARE(#neg(z0), #pos(z1)) -> c9
   #COMPARE(#pos(z0), #0) -> c10
   #COMPARE(#pos(z0), #neg(z1)) -> c11
   #COMPARE(#pos(z0), #pos(z1)) -> c12(#COMPARE(z0, z1))
   #COMPARE(#s(z0), #0) -> c13
   #COMPARE(#s(z0), #s(z1)) -> c14(#COMPARE(z0, z1))
   #LESS(z0, z1) -> c15(#CKLT(#compare(z0, z1)), #COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   FINDMIN#1(nil) -> c18
   FINDMIN#2(::(z0, z1), z2) -> c19(FINDMIN#3(#less(z2, z0), z2, z0, z1), #LESS(z2, z0))
   FINDMIN#2(nil, z0) -> c20
   FINDMIN#3(#false, z0, z1, z2) -> c21
   FINDMIN#3(#true, z0, z1, z2) -> c22
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   MINSORT#1(nil) -> c25
S tuples:
   #LESS(z0, z1) -> c15(#CKLT(#compare(z0, z1)), #COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   FINDMIN#1(nil) -> c18
   FINDMIN#2(::(z0, z1), z2) -> c19(FINDMIN#3(#less(z2, z0), z2, z0, z1), #LESS(z2, z0))
   FINDMIN#2(nil, z0) -> c20
   FINDMIN#3(#false, z0, z1, z2) -> c21
   FINDMIN#3(#true, z0, z1, z2) -> c22
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   MINSORT#1(nil) -> c25
K tuples:none
Defined Rule Symbols:   #less_2, findMin_1, findMin#1_1, findMin#2_2, findMin#3_4, minSort_1, minSort#1_1, #cklt_1, #compare_2

Defined Pair Symbols:   #CKLT_1, #COMPARE_2, #LESS_2, FINDMIN_1, FINDMIN#1_1, FINDMIN#2_2, FINDMIN#3_4, MINSORT_1, MINSORT#1_1

Compound Symbols:   c, c1, c2, c3, c4, c5, c6, c7, c8_1, c9, c10, c11, c12_1, c13, c14_1, c15_2, c16_1, c17_2, c18, c19_2, c20, c21, c22, c23_2, c24_1, c25


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

(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 17 trailing nodes:
   #CKLT(#EQ) -> c
   MINSORT#1(nil) -> c25
   FINDMIN#2(nil, z0) -> c20
   #CKLT(#GT) -> c1
   #COMPARE(#pos(z0), #neg(z1)) -> c11
   #COMPARE(#0, #s(z0)) -> c6
   #CKLT(#LT) -> c2
   #COMPARE(#0, #pos(z0)) -> c5
   #COMPARE(#0, #0) -> c3
   #COMPARE(#neg(z0), #pos(z1)) -> c9
   #COMPARE(#s(z0), #0) -> c13
   #COMPARE(#0, #neg(z0)) -> c4
   #COMPARE(#pos(z0), #0) -> c10
   FINDMIN#1(nil) -> c18
   #COMPARE(#neg(z0), #0) -> c7
   FINDMIN#3(#false, z0, z1, z2) -> c21
   FINDMIN#3(#true, z0, z1, z2) -> c22

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

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(z0)) -> #GT
   #compare(#0, #pos(z0)) -> #LT
   #compare(#0, #s(z0)) -> #LT
   #compare(#neg(z0), #0) -> #LT
   #compare(#neg(z0), #neg(z1)) -> #compare(z1, z0)
   #compare(#neg(z0), #pos(z1)) -> #LT
   #compare(#pos(z0), #0) -> #GT
   #compare(#pos(z0), #neg(z1)) -> #GT
   #compare(#pos(z0), #pos(z1)) -> #compare(z0, z1)
   #compare(#s(z0), #0) -> #GT
   #compare(#s(z0), #s(z1)) -> #compare(z0, z1)
   #less(z0, z1) -> #cklt(#compare(z0, z1))
   findMin(z0) -> findMin#1(z0)
   findMin#1(::(z0, z1)) -> findMin#2(findMin(z1), z0)
   findMin#1(nil) -> nil
   findMin#2(::(z0, z1), z2) -> findMin#3(#less(z2, z0), z2, z0, z1)
   findMin#2(nil, z0) -> ::(z0, nil)
   findMin#3(#false, z0, z1, z2) -> ::(z1, ::(z0, z2))
   findMin#3(#true, z0, z1, z2) -> ::(z0, ::(z1, z2))
   minSort(z0) -> minSort#1(findMin(z0))
   minSort#1(::(z0, z1)) -> ::(z0, minSort(z1))
   minSort#1(nil) -> nil
Tuples:
   #COMPARE(#neg(z0), #neg(z1)) -> c8(#COMPARE(z1, z0))
   #COMPARE(#pos(z0), #pos(z1)) -> c12(#COMPARE(z0, z1))
   #COMPARE(#s(z0), #s(z1)) -> c14(#COMPARE(z0, z1))
   #LESS(z0, z1) -> c15(#CKLT(#compare(z0, z1)), #COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(FINDMIN#3(#less(z2, z0), z2, z0, z1), #LESS(z2, z0))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
S tuples:
   #LESS(z0, z1) -> c15(#CKLT(#compare(z0, z1)), #COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(FINDMIN#3(#less(z2, z0), z2, z0, z1), #LESS(z2, z0))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
K tuples:none
Defined Rule Symbols:   #less_2, findMin_1, findMin#1_1, findMin#2_2, findMin#3_4, minSort_1, minSort#1_1, #cklt_1, #compare_2

Defined Pair Symbols:   #COMPARE_2, #LESS_2, FINDMIN_1, FINDMIN#1_1, FINDMIN#2_2, MINSORT_1, MINSORT#1_1

Compound Symbols:   c8_1, c12_1, c14_1, c15_2, c16_1, c17_2, c19_2, c23_2, c24_1


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

(7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
Removed 2 trailing tuple parts
----------------------------------------

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(z0)) -> #GT
   #compare(#0, #pos(z0)) -> #LT
   #compare(#0, #s(z0)) -> #LT
   #compare(#neg(z0), #0) -> #LT
   #compare(#neg(z0), #neg(z1)) -> #compare(z1, z0)
   #compare(#neg(z0), #pos(z1)) -> #LT
   #compare(#pos(z0), #0) -> #GT
   #compare(#pos(z0), #neg(z1)) -> #GT
   #compare(#pos(z0), #pos(z1)) -> #compare(z0, z1)
   #compare(#s(z0), #0) -> #GT
   #compare(#s(z0), #s(z1)) -> #compare(z0, z1)
   #less(z0, z1) -> #cklt(#compare(z0, z1))
   findMin(z0) -> findMin#1(z0)
   findMin#1(::(z0, z1)) -> findMin#2(findMin(z1), z0)
   findMin#1(nil) -> nil
   findMin#2(::(z0, z1), z2) -> findMin#3(#less(z2, z0), z2, z0, z1)
   findMin#2(nil, z0) -> ::(z0, nil)
   findMin#3(#false, z0, z1, z2) -> ::(z1, ::(z0, z2))
   findMin#3(#true, z0, z1, z2) -> ::(z0, ::(z1, z2))
   minSort(z0) -> minSort#1(findMin(z0))
   minSort#1(::(z0, z1)) -> ::(z0, minSort(z1))
   minSort#1(nil) -> nil
Tuples:
   #COMPARE(#neg(z0), #neg(z1)) -> c8(#COMPARE(z1, z0))
   #COMPARE(#pos(z0), #pos(z1)) -> c12(#COMPARE(z0, z1))
   #COMPARE(#s(z0), #s(z1)) -> c14(#COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
S tuples:
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
K tuples:none
Defined Rule Symbols:   #less_2, findMin_1, findMin#1_1, findMin#2_2, findMin#3_4, minSort_1, minSort#1_1, #cklt_1, #compare_2

Defined Pair Symbols:   #COMPARE_2, FINDMIN_1, FINDMIN#1_1, MINSORT_1, MINSORT#1_1, #LESS_2, FINDMIN#2_2

Compound Symbols:   c8_1, c12_1, c14_1, c16_1, c17_2, c23_2, c24_1, c15_1, c19_1


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

(9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   minSort(z0) -> minSort#1(findMin(z0))
   minSort#1(::(z0, z1)) -> ::(z0, minSort(z1))
   minSort#1(nil) -> nil

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

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   findMin(z0) -> findMin#1(z0)
   findMin#1(::(z0, z1)) -> findMin#2(findMin(z1), z0)
   findMin#1(nil) -> nil
   findMin#2(::(z0, z1), z2) -> findMin#3(#less(z2, z0), z2, z0, z1)
   findMin#2(nil, z0) -> ::(z0, nil)
   findMin#3(#false, z0, z1, z2) -> ::(z1, ::(z0, z2))
   findMin#3(#true, z0, z1, z2) -> ::(z0, ::(z1, z2))
   #less(z0, z1) -> #cklt(#compare(z0, z1))
   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(z0)) -> #GT
   #compare(#0, #pos(z0)) -> #LT
   #compare(#0, #s(z0)) -> #LT
   #compare(#neg(z0), #0) -> #LT
   #compare(#neg(z0), #neg(z1)) -> #compare(z1, z0)
   #compare(#neg(z0), #pos(z1)) -> #LT
   #compare(#pos(z0), #0) -> #GT
   #compare(#pos(z0), #neg(z1)) -> #GT
   #compare(#pos(z0), #pos(z1)) -> #compare(z0, z1)
   #compare(#s(z0), #0) -> #GT
   #compare(#s(z0), #s(z1)) -> #compare(z0, z1)
Tuples:
   #COMPARE(#neg(z0), #neg(z1)) -> c8(#COMPARE(z1, z0))
   #COMPARE(#pos(z0), #pos(z1)) -> c12(#COMPARE(z0, z1))
   #COMPARE(#s(z0), #s(z1)) -> c14(#COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
S tuples:
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
K tuples:none
Defined Rule Symbols:   findMin_1, findMin#1_1, findMin#2_2, findMin#3_4, #less_2, #cklt_1, #compare_2

Defined Pair Symbols:   #COMPARE_2, FINDMIN_1, FINDMIN#1_1, MINSORT_1, MINSORT#1_1, #LESS_2, FINDMIN#2_2

Compound Symbols:   c8_1, c12_1, c14_1, c16_1, c17_2, c23_2, c24_1, c15_1, c19_1


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

(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
We considered the (Usable) Rules:
   findMin#2(nil, z0) -> ::(z0, nil)
   #compare(#0, #neg(z0)) -> #GT
   findMin#1(nil) -> nil
   findMin#3(#true, z0, z1, z2) -> ::(z0, ::(z1, z2))
   findMin#2(::(z0, z1), z2) -> findMin#3(#less(z2, z0), z2, z0, z1)
   findMin#3(#false, z0, z1, z2) -> ::(z1, ::(z0, z2))
   #compare(#0, #pos(z0)) -> #LT
   findMin(z0) -> findMin#1(z0)
   #compare(#0, #s(z0)) -> #LT
   #compare(#pos(z0), #0) -> #GT
   #compare(#neg(z0), #neg(z1)) -> #compare(z1, z0)
   #cklt(#GT) -> #false
   #compare(#s(z0), #s(z1)) -> #compare(z0, z1)
   #compare(#0, #0) -> #EQ
   #compare(#s(z0), #0) -> #GT
   #compare(#neg(z0), #pos(z1)) -> #LT
   #compare(#neg(z0), #0) -> #LT
   #cklt(#EQ) -> #false
   #compare(#pos(z0), #pos(z1)) -> #compare(z0, z1)
   #compare(#pos(z0), #neg(z1)) -> #GT
   findMin#1(::(z0, z1)) -> findMin#2(findMin(z1), z0)
   #less(z0, z1) -> #cklt(#compare(z0, z1))
   #cklt(#LT) -> #true
And the Tuples:
   #COMPARE(#neg(z0), #neg(z1)) -> c8(#COMPARE(z1, z0))
   #COMPARE(#pos(z0), #pos(z1)) -> c12(#COMPARE(z0, z1))
   #COMPARE(#s(z0), #s(z1)) -> c14(#COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(#0) = [1]
   POL(#COMPARE(x_1, x_2)) = 0
   POL(#EQ) = 0
   POL(#GT) = 0
   POL(#LESS(x_1, x_2)) = 0
   POL(#LT) = 0
   POL(#cklt(x_1)) = [1] + x_1
   POL(#compare(x_1, x_2)) = 0
   POL(#false) = [1]
   POL(#less(x_1, x_2)) = [1]
   POL(#neg(x_1)) = [1] + x_1
   POL(#pos(x_1)) = [1] + x_1
   POL(#s(x_1)) = [1] + x_1
   POL(#true) = [1]
   POL(::(x_1, x_2)) = [1] + x_1 + x_2
   POL(FINDMIN(x_1)) = 0
   POL(FINDMIN#1(x_1)) = 0
   POL(FINDMIN#2(x_1, x_2)) = 0
   POL(MINSORT(x_1)) = x_1
   POL(MINSORT#1(x_1)) = x_1
   POL(c12(x_1)) = x_1
   POL(c14(x_1)) = x_1
   POL(c15(x_1)) = x_1
   POL(c16(x_1)) = x_1
   POL(c17(x_1, x_2)) = x_1 + x_2
   POL(c19(x_1)) = x_1
   POL(c23(x_1, x_2)) = x_1 + x_2
   POL(c24(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(findMin(x_1)) = x_1
   POL(findMin#1(x_1)) = x_1
   POL(findMin#2(x_1, x_2)) = [1] + x_1 + x_2
   POL(findMin#3(x_1, x_2, x_3, x_4)) = [1] + x_1 + x_2 + x_3 + x_4
   POL(nil) = [1]

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

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   findMin(z0) -> findMin#1(z0)
   findMin#1(::(z0, z1)) -> findMin#2(findMin(z1), z0)
   findMin#1(nil) -> nil
   findMin#2(::(z0, z1), z2) -> findMin#3(#less(z2, z0), z2, z0, z1)
   findMin#2(nil, z0) -> ::(z0, nil)
   findMin#3(#false, z0, z1, z2) -> ::(z1, ::(z0, z2))
   findMin#3(#true, z0, z1, z2) -> ::(z0, ::(z1, z2))
   #less(z0, z1) -> #cklt(#compare(z0, z1))
   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(z0)) -> #GT
   #compare(#0, #pos(z0)) -> #LT
   #compare(#0, #s(z0)) -> #LT
   #compare(#neg(z0), #0) -> #LT
   #compare(#neg(z0), #neg(z1)) -> #compare(z1, z0)
   #compare(#neg(z0), #pos(z1)) -> #LT
   #compare(#pos(z0), #0) -> #GT
   #compare(#pos(z0), #neg(z1)) -> #GT
   #compare(#pos(z0), #pos(z1)) -> #compare(z0, z1)
   #compare(#s(z0), #0) -> #GT
   #compare(#s(z0), #s(z1)) -> #compare(z0, z1)
Tuples:
   #COMPARE(#neg(z0), #neg(z1)) -> c8(#COMPARE(z1, z0))
   #COMPARE(#pos(z0), #pos(z1)) -> c12(#COMPARE(z0, z1))
   #COMPARE(#s(z0), #s(z1)) -> c14(#COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
S tuples:
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
K tuples:
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
Defined Rule Symbols:   findMin_1, findMin#1_1, findMin#2_2, findMin#3_4, #less_2, #cklt_1, #compare_2

Defined Pair Symbols:   #COMPARE_2, FINDMIN_1, FINDMIN#1_1, MINSORT_1, MINSORT#1_1, #LESS_2, FINDMIN#2_2

Compound Symbols:   c8_1, c12_1, c14_1, c16_1, c17_2, c23_2, c24_1, c15_1, c19_1


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

(13) CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
The following tuples could be moved from S to K by knowledge propagation:
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))

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

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   findMin(z0) -> findMin#1(z0)
   findMin#1(::(z0, z1)) -> findMin#2(findMin(z1), z0)
   findMin#1(nil) -> nil
   findMin#2(::(z0, z1), z2) -> findMin#3(#less(z2, z0), z2, z0, z1)
   findMin#2(nil, z0) -> ::(z0, nil)
   findMin#3(#false, z0, z1, z2) -> ::(z1, ::(z0, z2))
   findMin#3(#true, z0, z1, z2) -> ::(z0, ::(z1, z2))
   #less(z0, z1) -> #cklt(#compare(z0, z1))
   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(z0)) -> #GT
   #compare(#0, #pos(z0)) -> #LT
   #compare(#0, #s(z0)) -> #LT
   #compare(#neg(z0), #0) -> #LT
   #compare(#neg(z0), #neg(z1)) -> #compare(z1, z0)
   #compare(#neg(z0), #pos(z1)) -> #LT
   #compare(#pos(z0), #0) -> #GT
   #compare(#pos(z0), #neg(z1)) -> #GT
   #compare(#pos(z0), #pos(z1)) -> #compare(z0, z1)
   #compare(#s(z0), #0) -> #GT
   #compare(#s(z0), #s(z1)) -> #compare(z0, z1)
Tuples:
   #COMPARE(#neg(z0), #neg(z1)) -> c8(#COMPARE(z1, z0))
   #COMPARE(#pos(z0), #pos(z1)) -> c12(#COMPARE(z0, z1))
   #COMPARE(#s(z0), #s(z1)) -> c14(#COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
S tuples:
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
K tuples:
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
Defined Rule Symbols:   findMin_1, findMin#1_1, findMin#2_2, findMin#3_4, #less_2, #cklt_1, #compare_2

Defined Pair Symbols:   #COMPARE_2, FINDMIN_1, FINDMIN#1_1, MINSORT_1, MINSORT#1_1, #LESS_2, FINDMIN#2_2

Compound Symbols:   c8_1, c12_1, c14_1, c16_1, c17_2, c23_2, c24_1, c15_1, c19_1


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

(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
We considered the (Usable) Rules:
   findMin#2(nil, z0) -> ::(z0, nil)
   findMin#1(nil) -> nil
   findMin#3(#true, z0, z1, z2) -> ::(z0, ::(z1, z2))
   findMin#2(::(z0, z1), z2) -> findMin#3(#less(z2, z0), z2, z0, z1)
   findMin#3(#false, z0, z1, z2) -> ::(z1, ::(z0, z2))
   findMin(z0) -> findMin#1(z0)
   findMin#1(::(z0, z1)) -> findMin#2(findMin(z1), z0)
And the Tuples:
   #COMPARE(#neg(z0), #neg(z1)) -> c8(#COMPARE(z1, z0))
   #COMPARE(#pos(z0), #pos(z1)) -> c12(#COMPARE(z0, z1))
   #COMPARE(#s(z0), #s(z1)) -> c14(#COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(#0) = 0
   POL(#COMPARE(x_1, x_2)) = 0
   POL(#EQ) = 0
   POL(#GT) = 0
   POL(#LESS(x_1, x_2)) = 0
   POL(#LT) = 0
   POL(#cklt(x_1)) = [1]
   POL(#compare(x_1, x_2)) = 0
   POL(#false) = 0
   POL(#less(x_1, x_2)) = 0
   POL(#neg(x_1)) = 0
   POL(#pos(x_1)) = 0
   POL(#s(x_1)) = 0
   POL(#true) = 0
   POL(::(x_1, x_2)) = [1] + x_2
   POL(FINDMIN(x_1)) = x_1
   POL(FINDMIN#1(x_1)) = x_1
   POL(FINDMIN#2(x_1, x_2)) = 0
   POL(MINSORT(x_1)) = [2] + x_1 + [2]x_1^2
   POL(MINSORT#1(x_1)) = [2]x_1^2
   POL(c12(x_1)) = x_1
   POL(c14(x_1)) = x_1
   POL(c15(x_1)) = x_1
   POL(c16(x_1)) = x_1
   POL(c17(x_1, x_2)) = x_1 + x_2
   POL(c19(x_1)) = x_1
   POL(c23(x_1, x_2)) = x_1 + x_2
   POL(c24(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(findMin(x_1)) = x_1
   POL(findMin#1(x_1)) = x_1
   POL(findMin#2(x_1, x_2)) = [1] + x_1
   POL(findMin#3(x_1, x_2, x_3, x_4)) = [2] + x_4
   POL(nil) = 0

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

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   findMin(z0) -> findMin#1(z0)
   findMin#1(::(z0, z1)) -> findMin#2(findMin(z1), z0)
   findMin#1(nil) -> nil
   findMin#2(::(z0, z1), z2) -> findMin#3(#less(z2, z0), z2, z0, z1)
   findMin#2(nil, z0) -> ::(z0, nil)
   findMin#3(#false, z0, z1, z2) -> ::(z1, ::(z0, z2))
   findMin#3(#true, z0, z1, z2) -> ::(z0, ::(z1, z2))
   #less(z0, z1) -> #cklt(#compare(z0, z1))
   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(z0)) -> #GT
   #compare(#0, #pos(z0)) -> #LT
   #compare(#0, #s(z0)) -> #LT
   #compare(#neg(z0), #0) -> #LT
   #compare(#neg(z0), #neg(z1)) -> #compare(z1, z0)
   #compare(#neg(z0), #pos(z1)) -> #LT
   #compare(#pos(z0), #0) -> #GT
   #compare(#pos(z0), #neg(z1)) -> #GT
   #compare(#pos(z0), #pos(z1)) -> #compare(z0, z1)
   #compare(#s(z0), #0) -> #GT
   #compare(#s(z0), #s(z1)) -> #compare(z0, z1)
Tuples:
   #COMPARE(#neg(z0), #neg(z1)) -> c8(#COMPARE(z1, z0))
   #COMPARE(#pos(z0), #pos(z1)) -> c12(#COMPARE(z0, z1))
   #COMPARE(#s(z0), #s(z1)) -> c14(#COMPARE(z0, z1))
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
S tuples:
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
K tuples:
   MINSORT#1(::(z0, z1)) -> c24(MINSORT(z1))
   MINSORT(z0) -> c23(MINSORT#1(findMin(z0)), FINDMIN(z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
Defined Rule Symbols:   findMin_1, findMin#1_1, findMin#2_2, findMin#3_4, #less_2, #cklt_1, #compare_2

Defined Pair Symbols:   #COMPARE_2, FINDMIN_1, FINDMIN#1_1, MINSORT_1, MINSORT#1_1, #LESS_2, FINDMIN#2_2

Compound Symbols:   c8_1, c12_1, c14_1, c16_1, c17_2, c23_2, c24_1, c15_1, c19_1


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

(17) CdtKnowledgeProof (FINISHED)
The following tuples could be moved from S to K by knowledge propagation:
   FINDMIN(z0) -> c16(FINDMIN#1(z0))
   FINDMIN#2(::(z0, z1), z2) -> c19(#LESS(z2, z0))
   FINDMIN#1(::(z0, z1)) -> c17(FINDMIN#2(findMin(z1), z0), FINDMIN(z1))
   #LESS(z0, z1) -> c15(#COMPARE(z0, z1))
Now S is empty
----------------------------------------

(18)
BOUNDS(1, 1)

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

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

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

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


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   findMin(@l) -> findMin#1(@l)
   findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x)
   findMin#1(nil) -> nil
   findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys)
   findMin#2(nil, @x) -> ::(@x, nil)
   findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys))
   findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys))
   minSort(@l) -> minSort#1(findMin(@l))
   minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs))
   minSort#1(nil) -> nil

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
----------------------------------------

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

The rewrite sequence

findMin#1(::(@x, @xs)) ->^+ findMin#2(findMin#1(@xs), @x)

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

The pumping substitution is [@xs / ::(@x, @xs)].

The result substitution is [ ].




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

(22)
Complex Obligation (BEST)

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

(23)
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, n^2).


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   findMin(@l) -> findMin#1(@l)
   findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x)
   findMin#1(nil) -> nil
   findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys)
   findMin#2(nil, @x) -> ::(@x, nil)
   findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys))
   findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys))
   minSort(@l) -> minSort#1(findMin(@l))
   minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs))
   minSort#1(nil) -> nil

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
----------------------------------------

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

(25)
BOUNDS(n^1, INF)

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

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

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


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   findMin(@l) -> findMin#1(@l)
   findMin#1(::(@x, @xs)) -> findMin#2(findMin(@xs), @x)
   findMin#1(nil) -> nil
   findMin#2(::(@y, @ys), @x) -> findMin#3(#less(@x, @y), @x, @y, @ys)
   findMin#2(nil, @x) -> ::(@x, nil)
   findMin#3(#false, @x, @y, @ys) -> ::(@y, ::(@x, @ys))
   findMin#3(#true, @x, @y, @ys) -> ::(@x, ::(@y, @ys))
   minSort(@l) -> minSort#1(findMin(@l))
   minSort#1(::(@x, @xs)) -> ::(@x, minSort(@xs))
   minSort#1(nil) -> nil

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