Term Rewriting System R:
[x, y]
pred(s(x)) -> x
minus(x, 0) -> x
minus(x, s(y)) -> pred(minus(x, y))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))

Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

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

Furthermore, R contains two SCCs.


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


Dependency Pair:

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


Rules:


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





The following dependency pair can be strictly oriented:

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


The following rules can be oriented:

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


Used ordering: Lexicographic Path Order with Non-Strict Precedence with Quasi Precedence:
quot > s

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


   R
DPs
       →DP Problem 1
AFS
           →DP Problem 3
Dependency Graph
       →DP Problem 2
AFS


Dependency Pair:


Rules:


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





Using the Dependency Graph resulted in no new DP problems.


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


Dependency Pair:

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


Rules:


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





The following dependency pair can be strictly oriented:

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


The following rules can be oriented:

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


Used ordering: Lexicographic Path Order with Non-Strict Precedence with Quasi Precedence:
quot > s

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


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
           →DP Problem 4
Dependency Graph


Dependency Pair:


Rules:


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





Using the Dependency Graph resulted in no new DP problems.

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