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

Termination of R to be shown.

R
Dependency Pair Analysis

R contains the following Dependency Pairs:

MINUS(s(x), s(y)) -> MINUS(x, y)
MINUS(minus(x, y), z) -> MINUS(x, plus(y, z))
MINUS(minus(x, y), z) -> PLUS(y, z)
QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y))
QUOT(s(x), s(y)) -> MINUS(x, y)
PLUS(s(x), y) -> PLUS(x, y)

Furthermore, R contains three SCCs.

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

Dependency Pair:

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

Rules:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))

The following dependency pair can be strictly oriented:

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

The following rules can be oriented:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))

Used ordering: Polynomial ordering with Polynomial interpretation:
 POL(PLUS(x1, x2)) =  1 + x1 + x2 POL(plus(x1, x2)) =  x1 + x2 POL(0) =  0 POL(quot(x1, x2)) =  x1 + x2 POL(s(x1)) =  1 + x1

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

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

Dependency Pair:

Rules:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))

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

Dependency Pairs:

MINUS(minus(x, y), z) -> MINUS(x, plus(y, z))
MINUS(s(x), s(y)) -> MINUS(x, y)

Rules:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))

The following dependency pair can be strictly oriented:

MINUS(minus(x, y), z) -> MINUS(x, plus(y, z))

The following rules can be oriented:

plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))

Used ordering: Polynomial ordering with Polynomial interpretation:
 POL(plus(x1, x2)) =  x1 + x2 POL(0) =  0 POL(MINUS(x1, x2)) =  x1 + x2 POL(minus(x1, x2)) =  1 + x1 + x2 POL(s(x1)) =  x1

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

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

Dependency Pair:

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

Rules:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))

The following dependency pair can be strictly oriented:

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

The following rules can be oriented:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))

Used ordering: Polynomial ordering with Polynomial interpretation:
 POL(plus(x1, x2)) =  x1 + x2 POL(0) =  0 POL(MINUS(x1, x2)) =  1 + x1 + x2 POL(quot(x1, x2)) =  x1 + x2 POL(s(x1)) =  1 + x1

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

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

Dependency Pair:

Rules:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))

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

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)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, 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(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))

Used ordering: Polynomial ordering with Polynomial interpretation:
 POL(QUOT(x1, x2)) =  1 + x1 + x2 POL(plus(x1, x2)) =  x1 + x2 POL(0) =  0 POL(quot(x1, x2)) =  x1 + x2 POL(s(x1)) =  1 + x1

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

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

Dependency Pair:

Rules:

minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
minus(minus(x, y), z) -> minus(x, plus(y, z))
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))

Using the Dependency Graph resulted in no new DP problems.

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