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: Polynomial ordering with Polynomial interpretation:
  POL(0)=  0  
  POL(pred(x1))=  x1  
  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)
pred(x1) -> pred(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: Polynomial ordering with Polynomial interpretation:
  POL(QUOT(x1, x2))=  1 + x1 + x2  
  POL(0)=  0  
  POL(pred(x1))=  x1  
  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
pred(x1) -> pred(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