Termination Proof using AProVE

Term Rewriting System R:
[x, y, n, m]
app'(app'(minus, x), 0) -> x
app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) -> 0
app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) -> true
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(app, nil), y) -> y
app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) -> nil
app'(app'(low, n), app'(app'(add, m), x)) -> app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> app'(app'(low, n), x)
app'(app'(high, n), nil) -> nil
app'(app'(high, n), app'(app'(add, m), x)) -> app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) -> nil
app'(quicksort, app'(app'(add, n), x)) -> app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))

Termination of R to be shown.

     ↳Overlay and local confluence Check

The TRS is overlay and locally confluent (all critical pairs are trivially joinable).Hence, we can switch to innermost.

     ↳OC

       →TRS2

         ↳Dependency Pair Analysis

R contains the following Dependency Pairs:

APP'(app'(minus, app'(s, x)), app'(s, y)) -> APP'(app'(minus, x), y)
APP'(app'(minus, app'(s, x)), app'(s, y)) -> APP'(minus, x)
APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(app'(quot, app'(app'(minus, x), y)), app'(s, y))
APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(quot, app'(app'(minus, x), y))
APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(app'(minus, x), y)
APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(minus, x)
APP'(app'(le, app'(s, x)), app'(s, y)) -> APP'(app'(le, x), y)
APP'(app'(le, app'(s, x)), app'(s, y)) -> APP'(le, x)
APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app'(add, n), app'(app'(app, x), y))
APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app'(app, x), y)
APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app, x)
APP'(app'(low, n), app'(app'(add, m), x)) -> APP'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
APP'(app'(low, n), app'(app'(add, m), x)) -> APP'(app'(if_low, app'(app'(le, m), n)), n)
APP'(app'(low, n), app'(app'(add, m), x)) -> APP'(if_low, app'(app'(le, m), n))
APP'(app'(low, n), app'(app'(add, m), x)) -> APP'(app'(le, m), n)
APP'(app'(low, n), app'(app'(add, m), x)) -> APP'(le, m)
APP'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> APP'(app'(add, m), app'(app'(low, n), x))
APP'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> APP'(app'(low, n), x)
APP'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> APP'(low, n)
APP'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> APP'(app'(low, n), x)
APP'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> APP'(low, n)
APP'(app'(high, n), app'(app'(add, m), x)) -> APP'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
APP'(app'(high, n), app'(app'(add, m), x)) -> APP'(app'(if_high, app'(app'(le, m), n)), n)
APP'(app'(high, n), app'(app'(add, m), x)) -> APP'(if_high, app'(app'(le, m), n))
APP'(app'(high, n), app'(app'(add, m), x)) -> APP'(app'(le, m), n)
APP'(app'(high, n), app'(app'(add, m), x)) -> APP'(le, m)
APP'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> APP'(app'(high, n), x)
APP'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> APP'(high, n)
APP'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> APP'(app'(add, m), app'(app'(high, n), x))
APP'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> APP'(app'(high, n), x)
APP'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> APP'(high, n)
APP'(quicksort, app'(app'(add, n), x)) -> APP'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
APP'(quicksort, app'(app'(add, n), x)) -> APP'(app, app'(quicksort, app'(app'(low, n), x)))
APP'(quicksort, app'(app'(add, n), x)) -> APP'(quicksort, app'(app'(low, n), x))
APP'(quicksort, app'(app'(add, n), x)) -> APP'(app'(low, n), x)
APP'(quicksort, app'(app'(add, n), x)) -> APP'(low, n)
APP'(quicksort, app'(app'(add, n), x)) -> APP'(app'(add, n), app'(quicksort, app'(app'(high, n), x)))
APP'(quicksort, app'(app'(add, n), x)) -> APP'(quicksort, app'(app'(high, n), x))
APP'(quicksort, app'(app'(add, n), x)) -> APP'(app'(high, n), x)
APP'(quicksort, app'(app'(add, n), x)) -> APP'(high, n)

Furthermore, R contains seven SCCs.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳Usable Rules (Innermost)

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

APP'(app'(minus, app'(s, x)), app'(s, y)) -> APP'(app'(minus, x), y)

Rules:

app'(app'(minus, x), 0) -> x
app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) -> 0
app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) -> true
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(app, nil), y) -> y
app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) -> nil
app'(app'(low, n), app'(app'(add, m), x)) -> app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> app'(app'(low, n), x)
app'(app'(high, n), nil) -> nil
app'(app'(high, n), app'(app'(add, m), x)) -> app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) -> nil
app'(quicksort, app'(app'(add, n), x)) -> app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))

Strategy:

innermost

As we are in the innermost case, we can delete all 19 non-usable-rules.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

...

               →DP Problem 8

                 ↳A-Transformation

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

APP'(app'(minus, app'(s, x)), app'(s, y)) -> APP'(app'(minus, x), y)

Rule:

none

Strategy:

innermost

We have an applicative DP problem with proper arity. Thus we can use the A-Transformation to obtain one new DP problem which consists of the A-transformed TRSs.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

...

               →DP Problem 9

                 ↳Size-Change Principle

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

MINUS(s(x), s(y)) -> MINUS(x, y)

Rule:

none

Strategy:

innermost

We number the DPs as follows:

MINUS(s(x), s(y)) -> MINUS(x, y)

and get the following Size-Change Graph(s):

{1}	,	{1}
1	>	1
2	>	2

which lead(s) to this/these maximal multigraph(s):

{1}	,	{1}
1	>	1
2	>	2

D_P: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.

trivial

with Argument Filtering System:

s(x₁) -> s(x₁)

We obtain no new DP problems.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳Usable Rules (Innermost)

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

APP'(app'(le, app'(s, x)), app'(s, y)) -> APP'(app'(le, x), y)

Rules:

app'(app'(minus, x), 0) -> x
app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) -> 0
app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) -> true
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(app, nil), y) -> y
app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) -> nil
app'(app'(low, n), app'(app'(add, m), x)) -> app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> app'(app'(low, n), x)
app'(app'(high, n), nil) -> nil
app'(app'(high, n), app'(app'(add, m), x)) -> app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) -> nil
app'(quicksort, app'(app'(add, n), x)) -> app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))

Strategy:

innermost

As we are in the innermost case, we can delete all 19 non-usable-rules.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

...

               →DP Problem 10

                 ↳A-Transformation

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

APP'(app'(le, app'(s, x)), app'(s, y)) -> APP'(app'(le, x), y)

Rule:

none

Strategy:

innermost

We have an applicative DP problem with proper arity. Thus we can use the A-Transformation to obtain one new DP problem which consists of the A-transformed TRSs.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

...

               →DP Problem 11

                 ↳Size-Change Principle

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

LE(s(x), s(y)) -> LE(x, y)

Rule:

none

Strategy:

innermost

We number the DPs as follows:

LE(s(x), s(y)) -> LE(x, y)

and get the following Size-Change Graph(s):

{1}	,	{1}
1	>	1
2	>	2

which lead(s) to this/these maximal multigraph(s):

{1}	,	{1}
1	>	1
2	>	2

D_P: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.

trivial

with Argument Filtering System:

s(x₁) -> s(x₁)

We obtain no new DP problems.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳Usable Rules (Innermost)

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app'(app, x), y)

Rules:

app'(app'(minus, x), 0) -> x
app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) -> 0
app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) -> true
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(app, nil), y) -> y
app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) -> nil
app'(app'(low, n), app'(app'(add, m), x)) -> app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> app'(app'(low, n), x)
app'(app'(high, n), nil) -> nil
app'(app'(high, n), app'(app'(add, m), x)) -> app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) -> nil
app'(quicksort, app'(app'(add, n), x)) -> app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))

Strategy:

innermost

As we are in the innermost case, we can delete all 19 non-usable-rules.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

...

               →DP Problem 12

                 ↳A-Transformation

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app'(app, x), y)

Rule:

none

Strategy:

innermost

We have an applicative DP problem with proper arity. Thus we can use the A-Transformation to obtain one new DP problem which consists of the A-transformed TRSs.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

...

               →DP Problem 13

                 ↳Size-Change Principle

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

APP(add(n, x), y) -> APP(x, y)

Rule:

none

Strategy:

innermost

We number the DPs as follows:

APP(add(n, x), y) -> APP(x, y)

and get the following Size-Change Graph(s):

{1}	,	{1}
1	>	1
2	=	2

which lead(s) to this/these maximal multigraph(s):

{1}	,	{1}
1	>	1
2	=	2

D_P: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.

trivial

with Argument Filtering System:

add(x₁, x₂) -> add(x₁, x₂)

We obtain no new DP problems.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳Usable Rules (Innermost)

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(app'(quot, app'(app'(minus, x), y)), app'(s, y))

Rules:

app'(app'(minus, x), 0) -> x
app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) -> 0
app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) -> true
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(app, nil), y) -> y
app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) -> nil
app'(app'(low, n), app'(app'(add, m), x)) -> app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> app'(app'(low, n), x)
app'(app'(high, n), nil) -> nil
app'(app'(high, n), app'(app'(add, m), x)) -> app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) -> nil
app'(quicksort, app'(app'(add, n), x)) -> app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))

Strategy:

innermost

As we are in the innermost case, we can delete all 17 non-usable-rules.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

...

               →DP Problem 14

                 ↳A-Transformation

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(app'(quot, app'(app'(minus, x), y)), app'(s, y))

Rules:

app'(app'(minus, x), 0) -> x
app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y)

Strategy:

innermost

We have an applicative DP problem with proper arity. Thus we can use the A-Transformation to obtain one new DP problem which consists of the A-transformed TRSs.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

...

               →DP Problem 15

                 ↳Negative Polynomial Order

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y))

Rules:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)

Strategy:

innermost

The following Dependency Pair can be strictly oriented using the given order.

QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y))

Moreover, the following usable rules (regarding the implicit AFS) are oriented.

minus(s(x), s(y)) -> minus(x, y)
minus(x, 0) -> x

Used ordering:
Polynomial Order with Interpretation:

POL( QUOT(x₁, x₂) ) = x₁

POL( s(x₁) ) = x₁ + 1

POL( minus(x₁, x₂) ) = x₁

This results in one new DP problem.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

...

               →DP Problem 16

                 ↳Dependency Graph

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pair:

Rules:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)

Strategy:

innermost

Using the Dependency Graph resulted in no new DP problems.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳Usable Rules (Innermost)

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pairs:

APP'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> APP'(app'(low, n), x)
APP'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> APP'(app'(low, n), x)
APP'(app'(low, n), app'(app'(add, m), x)) -> APP'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))

Rules:

app'(app'(minus, x), 0) -> x
app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) -> 0
app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) -> true
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(app, nil), y) -> y
app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) -> nil
app'(app'(low, n), app'(app'(add, m), x)) -> app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> app'(app'(low, n), x)
app'(app'(high, n), nil) -> nil
app'(app'(high, n), app'(app'(add, m), x)) -> app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) -> nil
app'(quicksort, app'(app'(add, n), x)) -> app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))

Strategy:

innermost

As we are in the innermost case, we can delete all 16 non-usable-rules.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

...

               →DP Problem 17

                 ↳A-Transformation

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pairs:

Rules:

app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, 0), y) -> true

Strategy:

innermost

We have an applicative DP problem with proper arity. Thus we can use the A-Transformation to obtain one new DP problem which consists of the A-transformed TRSs.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

...

               →DP Problem 18

                 ↳Size-Change Principle

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

Dependency Pairs:

IF_LOW(false, n, add(m, x)) -> LOW(n, x)
IF_LOW(true, n, add(m, x)) -> LOW(n, x)
LOW(n, add(m, x)) -> IF_LOW(le(m, n), n, add(m, x))

Rules:

le(s(x), s(y)) -> le(x, y)
le(s(x), 0) -> false
le(0, y) -> true

Strategy:

innermost

We number the DPs as follows:

IF_LOW(false, n, add(m, x)) -> LOW(n, x)
IF_LOW(true, n, add(m, x)) -> LOW(n, x)
LOW(n, add(m, x)) -> IF_LOW(le(m, n), n, add(m, x))

and get the following Size-Change Graph(s):

{1, 2}	,	{1, 2}
2	=	1
3	>	2

{3}	,	{3}
1	=	2
2	=	3

which lead(s) to this/these maximal multigraph(s):

{3}	,	{1, 2}
1	=	1
2	>	2

{1, 2}	,	{3}
2	=	2
3	>	3

D_P: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.

trivial

with Argument Filtering System:

add(x₁, x₂) -> add(x₁, x₂)

We obtain no new DP problems.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳Usable Rules (Innermost)

           →DP Problem 7

             ↳UsableRules

Dependency Pairs:

APP'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> APP'(app'(high, n), x)
APP'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> APP'(app'(high, n), x)
APP'(app'(high, n), app'(app'(add, m), x)) -> APP'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))

Rules:

app'(app'(minus, x), 0) -> x
app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) -> 0
app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) -> true
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(app, nil), y) -> y
app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) -> nil
app'(app'(low, n), app'(app'(add, m), x)) -> app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> app'(app'(low, n), x)
app'(app'(high, n), nil) -> nil
app'(app'(high, n), app'(app'(add, m), x)) -> app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) -> nil
app'(quicksort, app'(app'(add, n), x)) -> app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))

Strategy:

innermost

As we are in the innermost case, we can delete all 16 non-usable-rules.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

...

               →DP Problem 19

                 ↳A-Transformation

           →DP Problem 7

             ↳UsableRules

Dependency Pairs:

Rules:

app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, 0), y) -> true

Strategy:

innermost

We have an applicative DP problem with proper arity. Thus we can use the A-Transformation to obtain one new DP problem which consists of the A-transformed TRSs.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

...

               →DP Problem 20

                 ↳Size-Change Principle

           →DP Problem 7

             ↳UsableRules

Dependency Pairs:

IF_HIGH(false, n, add(m, x)) -> HIGH(n, x)
IF_HIGH(true, n, add(m, x)) -> HIGH(n, x)
HIGH(n, add(m, x)) -> IF_HIGH(le(m, n), n, add(m, x))

Rules:

le(s(x), s(y)) -> le(x, y)
le(s(x), 0) -> false
le(0, y) -> true

Strategy:

innermost

We number the DPs as follows:

IF_HIGH(false, n, add(m, x)) -> HIGH(n, x)
IF_HIGH(true, n, add(m, x)) -> HIGH(n, x)
HIGH(n, add(m, x)) -> IF_HIGH(le(m, n), n, add(m, x))

and get the following Size-Change Graph(s):

{1, 2}	,	{1, 2}
2	=	1
3	>	2

{3}	,	{3}
1	=	2
2	=	3

which lead(s) to this/these maximal multigraph(s):

{3}	,	{1, 2}
1	=	1
2	>	2

{1, 2}	,	{3}
2	=	2
3	>	3

D_P: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.

trivial

with Argument Filtering System:

add(x₁, x₂) -> add(x₁, x₂)

We obtain no new DP problems.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳Usable Rules (Innermost)

Dependency Pairs:

APP'(quicksort, app'(app'(add, n), x)) -> APP'(quicksort, app'(app'(high, n), x))
APP'(quicksort, app'(app'(add, n), x)) -> APP'(quicksort, app'(app'(low, n), x))

Rules:

app'(app'(minus, x), 0) -> x
app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) -> 0
app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) -> true
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(app, nil), y) -> y
app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) -> nil
app'(app'(low, n), app'(app'(add, m), x)) -> app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> app'(app'(low, n), x)
app'(app'(high, n), nil) -> nil
app'(app'(high, n), app'(app'(add, m), x)) -> app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) -> nil
app'(quicksort, app'(app'(add, n), x)) -> app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))

Strategy:

innermost

As we are in the innermost case, we can delete all 8 non-usable-rules.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

...

               →DP Problem 21

                 ↳A-Transformation

Dependency Pairs:

APP'(quicksort, app'(app'(add, n), x)) -> APP'(quicksort, app'(app'(high, n), x))
APP'(quicksort, app'(app'(add, n), x)) -> APP'(quicksort, app'(app'(low, n), x))

Rules:

app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y)
app'(app'(high, n), app'(app'(add, m), x)) -> app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(high, n), nil) -> nil
app'(app'(le, app'(s, x)), 0) -> false
app'(app'(le, 0), y) -> true
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(high, n), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) -> app'(app'(high, n), x)
app'(app'(low, n), nil) -> nil
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(low, n), x))
app'(app'(low, n), app'(app'(add, m), x)) -> app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) -> app'(app'(low, n), x)

Strategy:

innermost

We have an applicative DP problem with proper arity. Thus we can use the A-Transformation to obtain one new DP problem which consists of the A-transformed TRSs.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

...

               →DP Problem 22

                 ↳Negative Polynomial Order

Dependency Pairs:

QUICKSORT(add(n, x)) -> QUICKSORT(high(n, x))
QUICKSORT(add(n, x)) -> QUICKSORT(low(n, x))

Rules:

le(s(x), s(y)) -> le(x, y)
le(s(x), 0) -> false
le(0, y) -> true
high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x))
high(n, nil) -> nil
if_high(false, n, add(m, x)) -> add(m, high(n, x))
if_high(true, n, add(m, x)) -> high(n, x)
low(n, nil) -> nil
low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x))
if_low(true, n, add(m, x)) -> add(m, low(n, x))
if_low(false, n, add(m, x)) -> low(n, x)

Strategy:

innermost

The following Dependency Pairs can be strictly oriented using the given order.

QUICKSORT(add(n, x)) -> QUICKSORT(high(n, x))
QUICKSORT(add(n, x)) -> QUICKSORT(low(n, x))

Moreover, the following usable rules (regarding the implicit AFS) are oriented.

le(s(x), s(y)) -> le(x, y)
if_high(true, n, add(m, x)) -> high(n, x)
le(0, y) -> true
if_high(false, n, add(m, x)) -> add(m, high(n, x))
high(n, nil) -> nil
le(s(x), 0) -> false
high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x))
low(n, nil) -> nil
if_low(false, n, add(m, x)) -> low(n, x)
if_low(true, n, add(m, x)) -> add(m, low(n, x))
low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x))

Used ordering:
Polynomial Order with Interpretation:

POL( QUICKSORT(x₁) ) = x₁

POL( add(x₁, x₂) ) = x₂ + 1

POL( high(x₁, x₂) ) = x₂

POL( low(x₁, x₂) ) = x₂

POL( le(x₁, x₂) ) = 0

POL( if_high(x₁, ..., x₃) ) = x₃

POL( true ) = 0

POL( nil ) = 0

POL( false ) = 0

POL( if_low(x₁, ..., x₃) ) = x₃

This results in one new DP problem.

     ↳OC

       →TRS2

         ↳DPs

           →DP Problem 1

             ↳UsableRules

           →DP Problem 2

             ↳UsableRules

           →DP Problem 3

             ↳UsableRules

           →DP Problem 4

             ↳UsableRules

           →DP Problem 5

             ↳UsableRules

           →DP Problem 6

             ↳UsableRules

           →DP Problem 7

             ↳UsableRules

...

               →DP Problem 23

                 ↳Dependency Graph

Dependency Pair:

Rules:

le(s(x), s(y)) -> le(x, y)
le(s(x), 0) -> false
le(0, y) -> true
high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x))
high(n, nil) -> nil
if_high(false, n, add(m, x)) -> add(m, high(n, x))
if_high(true, n, add(m, x)) -> high(n, x)
low(n, nil) -> nil
low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x))
if_low(true, n, add(m, x)) -> add(m, low(n, x))
if_low(false, n, add(m, x)) -> low(n, x)

Strategy:

innermost

Using the Dependency Graph resulted in no new DP problems.

Termination of R successfully shown.
Duration:
0:03 minutes