Term Rewriting System R:
[Y, X, N, L, M]
le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))

Innermost Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

LE(s(X), s(Y)) -> LE(X, Y)
APP(cons(N, L), Y) -> APP(L, Y)
LOW(N, cons(M, L)) -> IFLOW(le(M, N), N, cons(M, L))
LOW(N, cons(M, L)) -> LE(M, N)
IFLOW(true, N, cons(M, L)) -> LOW(N, L)
IFLOW(false, N, cons(M, L)) -> LOW(N, L)
HIGH(N, cons(M, L)) -> IFHIGH(le(M, N), N, cons(M, L))
HIGH(N, cons(M, L)) -> LE(M, N)
IFHIGH(true, N, cons(M, L)) -> HIGH(N, L)
IFHIGH(false, N, cons(M, L)) -> HIGH(N, L)
QUICKSORT(cons(N, L)) -> APP(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))
QUICKSORT(cons(N, L)) -> QUICKSORT(low(N, L))
QUICKSORT(cons(N, L)) -> LOW(N, L)
QUICKSORT(cons(N, L)) -> QUICKSORT(high(N, L))
QUICKSORT(cons(N, L)) -> HIGH(N, L)

Furthermore, R contains five SCCs.


   R
DPs
       →DP Problem 1
Argument Filtering and Ordering
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
AFS


Dependency Pair:

LE(s(X), s(Y)) -> LE(X, Y)


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




The following dependency pair can be strictly oriented:

LE(s(X), s(Y)) -> LE(X, Y)


There are no usable rules for innermost that need to be oriented.
Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(LE(x1, x2))=  x1 + x2  
  POL(s(x1))=  1 + x1  

resulting in one new DP problem.
Used Argument Filtering System:
LE(x1, x2) -> LE(x1, x2)
s(x1) -> s(x1)


   R
DPs
       →DP Problem 1
AFS
           →DP Problem 6
Dependency Graph
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
AFS


Dependency Pair:


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
Argument Filtering and Ordering
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
AFS


Dependency Pair:

APP(cons(N, L), Y) -> APP(L, Y)


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




The following dependency pair can be strictly oriented:

APP(cons(N, L), Y) -> APP(L, Y)


There are no usable rules for innermost that need to be oriented.
Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(cons(x1, x2))=  1 + x1 + x2  
  POL(APP(x1, x2))=  x1 + x2  

resulting in one new DP problem.
Used Argument Filtering System:
APP(x1, x2) -> APP(x1, x2)
cons(x1, x2) -> cons(x1, x2)


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
           →DP Problem 7
Dependency Graph
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
AFS


Dependency Pair:


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
Argument Filtering and Ordering
       →DP Problem 4
AFS
       →DP Problem 5
AFS


Dependency Pairs:

IFLOW(false, N, cons(M, L)) -> LOW(N, L)
IFLOW(true, N, cons(M, L)) -> LOW(N, L)
LOW(N, cons(M, L)) -> IFLOW(le(M, N), N, cons(M, L))


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

IFLOW(false, N, cons(M, L)) -> LOW(N, L)
IFLOW(true, N, cons(M, L)) -> LOW(N, L)


The following usable rules for innermost can be oriented:

le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(LOW(x1, x2))=  x1 + x2  
  POL(cons(x1, x2))=  1 + x1 + x2  
  POL(false)=  0  
  POL(true)=  0  
  POL(IFLOW(x1, x2, x3))=  x1 + x2 + x3  
  POL(le)=  0  

resulting in one new DP problem.
Used Argument Filtering System:
IFLOW(x1, x2, x3) -> IFLOW(x1, x2, x3)
LOW(x1, x2) -> LOW(x1, x2)
cons(x1, x2) -> cons(x1, x2)
le(x1, x2) -> le


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
AFS
           →DP Problem 8
Dependency Graph
       →DP Problem 4
AFS
       →DP Problem 5
AFS


Dependency Pair:

LOW(N, cons(M, L)) -> IFLOW(le(M, N), N, cons(M, L))


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
Argument Filtering and Ordering
       →DP Problem 5
AFS


Dependency Pairs:

IFHIGH(false, N, cons(M, L)) -> HIGH(N, L)
IFHIGH(true, N, cons(M, L)) -> HIGH(N, L)
HIGH(N, cons(M, L)) -> IFHIGH(le(M, N), N, cons(M, L))


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




The following dependency pair can be strictly oriented:

HIGH(N, cons(M, L)) -> IFHIGH(le(M, N), N, cons(M, L))


The following usable rules for innermost can be oriented:

le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(IFHIGH(x1, x2, x3))=  x1 + x2 + x3  
  POL(cons(x1, x2))=  1 + x1 + x2  
  POL(false)=  0  
  POL(HIGH(x1, x2))=  1 + x1 + x2  
  POL(true)=  0  
  POL(le)=  0  

resulting in one new DP problem.
Used Argument Filtering System:
HIGH(x1, x2) -> HIGH(x1, x2)
IFHIGH(x1, x2, x3) -> IFHIGH(x1, x2, x3)
cons(x1, x2) -> cons(x1, x2)
le(x1, x2) -> le


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
AFS
           →DP Problem 9
Dependency Graph
       →DP Problem 5
AFS


Dependency Pairs:

IFHIGH(false, N, cons(M, L)) -> HIGH(N, L)
IFHIGH(true, N, cons(M, L)) -> HIGH(N, L)


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
Argument Filtering and Ordering


Dependency Pairs:

QUICKSORT(cons(N, L)) -> QUICKSORT(high(N, L))
QUICKSORT(cons(N, L)) -> QUICKSORT(low(N, L))


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

QUICKSORT(cons(N, L)) -> QUICKSORT(high(N, L))
QUICKSORT(cons(N, L)) -> QUICKSORT(low(N, L))


The following usable rules for innermost can be oriented:

high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(QUICKSORT(x1))=  1 + x1  
  POL(iflow(x1, x2, x3))=  x1 + x2 + x3  
  POL(cons(x1, x2))=  1 + x1 + x2  
  POL(false)=  0  
  POL(high(x1, x2))=  x1 + x2  
  POL(low(x1, x2))=  x1 + x2  
  POL(nil)=  0  
  POL(true)=  0  
  POL(ifhigh(x1, x2, x3))=  x1 + x2 + x3  
  POL(le)=  0  

resulting in one new DP problem.
Used Argument Filtering System:
QUICKSORT(x1) -> QUICKSORT(x1)
cons(x1, x2) -> cons(x1, x2)
high(x1, x2) -> high(x1, x2)
low(x1, x2) -> low(x1, x2)
ifhigh(x1, x2, x3) -> ifhigh(x1, x2, x3)
le(x1, x2) -> le
iflow(x1, x2, x3) -> iflow(x1, x2, x3)


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
AFS
           →DP Problem 10
Dependency Graph


Dependency Pair:


Rules:


le(0, Y) -> true
le(s(X), 0) -> false
le(s(X), s(Y)) -> le(X, Y)
app(nil, Y) -> Y
app(cons(N, L), Y) -> cons(N, app(L, Y))
low(N, nil) -> nil
low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
iflow(false, N, cons(M, L)) -> low(N, L)
high(N, nil) -> nil
high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
ifhigh(true, N, cons(M, L)) -> high(N, L)
ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
quicksort(nil) -> nil
quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.

Innermost Termination of R successfully shown.
Duration:
0:00 minutes