Termination Proof using AProVE

Term Rewriting System R:
[x, y, v, w, z]
sort(nil) -> nil
sort(cons(x, y)) -> insert(x, sort(y))
insert(x, nil) -> cons(x, nil)
insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) -> cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) -> cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z)

Termination of R to be shown.

     ↳Dependency Pair Analysis

R contains the following Dependency Pairs:

SORT(cons(x, y)) -> INSERT(x, sort(y))
SORT(cons(x, y)) -> SORT(y)
INSERT(x, cons(v, w)) -> CHOOSE(x, cons(v, w), x, v)
CHOOSE(x, cons(v, w), 0, s(z)) -> INSERT(x, w)
CHOOSE(x, cons(v, w), s(y), s(z)) -> CHOOSE(x, cons(v, w), y, z)

Furthermore, R contains two SCCs.

     ↳DPs

       →DP Problem 1

         ↳Remaining Obligation(s)

       →DP Problem 2

         ↳Remaining Obligation(s)

The following remains to be proven:

Dependency Pairs:
CHOOSE(x, cons(v, w), s(y), s(z)) -> CHOOSE(x, cons(v, w), y, z)
CHOOSE(x, cons(v, w), 0, s(z)) -> INSERT(x, w)
INSERT(x, cons(v, w)) -> CHOOSE(x, cons(v, w), x, v)

Rules:

sort(nil) -> nil
sort(cons(x, y)) -> insert(x, sort(y))
insert(x, nil) -> cons(x, nil)
insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) -> cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) -> cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z)
Dependency Pair:
SORT(cons(x, y)) -> SORT(y)

Rules:

sort(nil) -> nil
sort(cons(x, y)) -> insert(x, sort(y))
insert(x, nil) -> cons(x, nil)
insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) -> cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) -> cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z)

     ↳DPs

       →DP Problem 1

         ↳Remaining Obligation(s)

       →DP Problem 2

         ↳Remaining Obligation(s)

The following remains to be proven:

Dependency Pairs:
CHOOSE(x, cons(v, w), s(y), s(z)) -> CHOOSE(x, cons(v, w), y, z)
CHOOSE(x, cons(v, w), 0, s(z)) -> INSERT(x, w)
INSERT(x, cons(v, w)) -> CHOOSE(x, cons(v, w), x, v)

Rules:

sort(nil) -> nil
sort(cons(x, y)) -> insert(x, sort(y))
insert(x, nil) -> cons(x, nil)
insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) -> cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) -> cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z)
Dependency Pair:
SORT(cons(x, y)) -> SORT(y)

Rules:

sort(nil) -> nil
sort(cons(x, y)) -> insert(x, sort(y))
insert(x, nil) -> cons(x, nil)
insert(x, cons(v, w)) -> choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) -> cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) -> cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) -> choose(x, cons(v, w), y, z)

Termination of R could not be shown.
Duration:
0:00 minutes