Termination w.r.t. Q of the given QTRS could be proven:

0 QTRS
↳1 DependencyPairsProof (⇔)
↳2 QDP
↳3 DependencyGraphProof (⇔)
↳4 AND
  ↳5 QDP
    ↳6 QDPOrderProof (⇔)
    ↳7 QDP
    ↳8 PisEmptyProof (⇔)
    ↳9 TRUE
  ↳10 QDP
    ↳11 QDPOrderProof (⇔)
    ↳12 QDP
    ↳13 PisEmptyProof (⇔)
    ↳14 TRUE
  ↳15 QDP
    ↳16 QDPOrderProof (⇔)
    ↳17 QDP
    ↳18 PisEmptyProof (⇔)
    ↳19 TRUE

(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

Q is empty.

(1) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.

(2) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MINUS(n__0, Y) → 01
MINUS(n__s(X), n__s(Y)) → MINUS(activate(X), activate(Y))
MINUS(n__s(X), n__s(Y)) → ACTIVATE(X)
MINUS(n__s(X), n__s(Y)) → ACTIVATE(Y)
GEQ(n__s(X), n__s(Y)) → GEQ(activate(X), activate(Y))
GEQ(n__s(X), n__s(Y)) → ACTIVATE(X)
GEQ(n__s(X), n__s(Y)) → ACTIVATE(Y)
DIV(s(X), n__s(Y)) → IF(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
DIV(s(X), n__s(Y)) → GEQ(X, activate(Y))
DIV(s(X), n__s(Y)) → ACTIVATE(Y)
DIV(s(X), n__s(Y)) → DIV(minus(X, activate(Y)), n__s(activate(Y)))
DIV(s(X), n__s(Y)) → MINUS(X, activate(Y))
IF(true, X, Y) → ACTIVATE(X)
IF(false, X, Y) → ACTIVATE(Y)
ACTIVATE(n__0) → 01
ACTIVATE(n__s(X)) → S(X)

The TRS R consists of the following rules:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(3) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 13 less nodes.

(4) Complex Obligation (AND)

(5) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GEQ(n__s(X), n__s(Y)) → GEQ(activate(X), activate(Y))

The TRS R consists of the following rules:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(6) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


GEQ(n__s(X), n__s(Y)) → GEQ(activate(X), activate(Y))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
GEQ(x1, x2)  =  GEQ(x2)
n__s(x1)  =  n__s(x1)
activate(x1)  =  activate(x1)
minus(x1, x2)  =  minus(x1)
n__0  =  n__0
0  =  0
geq(x1, x2)  =  geq(x1, x2)
true  =  true
false  =  false
div(x1, x2)  =  div(x1)
s(x1)  =  s(x1)
if(x1, x2, x3)  =  if(x2, x3)

Recursive Path Order [RPO].
Precedence:
div1 > [ns1, geq2, s1] > GEQ1 > activate1 > minus1
div1 > [ns1, geq2, s1] > [n0, 0] > true > minus1
div1 > [ns1, geq2, s1] > false > activate1 > minus1
div1 > [ns1, geq2, s1] > if2 > activate1 > minus1


The following usable rules [FROCOS05] were oriented:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

(7) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(8) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(9) TRUE

(10) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MINUS(n__s(X), n__s(Y)) → MINUS(activate(X), activate(Y))

The TRS R consists of the following rules:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(11) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


MINUS(n__s(X), n__s(Y)) → MINUS(activate(X), activate(Y))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
MINUS(x1, x2)  =  MINUS(x2)
n__s(x1)  =  n__s(x1)
activate(x1)  =  activate(x1)
minus(x1, x2)  =  minus(x1)
n__0  =  n__0
0  =  0
geq(x1, x2)  =  geq(x1, x2)
true  =  true
false  =  false
div(x1, x2)  =  div(x1)
s(x1)  =  s(x1)
if(x1, x2, x3)  =  if(x2, x3)

Recursive Path Order [RPO].
Precedence:
div1 > [ns1, geq2, s1] > MINUS1 > activate1 > minus1
div1 > [ns1, geq2, s1] > [n0, 0] > true > minus1
div1 > [ns1, geq2, s1] > false > activate1 > minus1
div1 > [ns1, geq2, s1] > if2 > activate1 > minus1


The following usable rules [FROCOS05] were oriented:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

(12) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(13) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(14) TRUE

(15) Obligation:

Q DP problem:
The TRS P consists of the following rules:

DIV(s(X), n__s(Y)) → DIV(minus(X, activate(Y)), n__s(activate(Y)))

The TRS R consists of the following rules:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(16) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


DIV(s(X), n__s(Y)) → DIV(minus(X, activate(Y)), n__s(activate(Y)))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
DIV(x1, x2)  =  x1
s(x1)  =  s(x1)
n__s(x1)  =  n__s(x1)
minus(x1, x2)  =  minus
activate(x1)  =  activate(x1)
n__0  =  n__0
0  =  0
geq(x1, x2)  =  geq
true  =  true
false  =  false
div(x1, x2)  =  div(x1)
if(x1, x2, x3)  =  if(x2, x3)

Recursive Path Order [RPO].
Precedence:
div1 > [s1, activate1, if2] > minus > [n0, 0] > [ns1, true]
div1 > [s1, activate1, if2] > [geq, false] > [ns1, true]


The following usable rules [FROCOS05] were oriented:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

(17) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

minus(n__0, Y) → 0
minus(n__s(X), n__s(Y)) → minus(activate(X), activate(Y))
geq(X, n__0) → true
geq(n__0, n__s(Y)) → false
geq(n__s(X), n__s(Y)) → geq(activate(X), activate(Y))
div(0, n__s(Y)) → 0
div(s(X), n__s(Y)) → if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
0 → n__0
s(X) → n__s(X)
activate(n__0) → 0
activate(n__s(X)) → s(X)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(18) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(19) TRUE