Termination w.r.t. Q of the following Term Rewriting System could be proven:
Q restricted rewrite system:
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
quot(x, y) → if_quot(minus(x, y), y, le(y, 0), le(y, x))
if_quot(x, y, true, z) → divByZeroError
if_quot(x, y, false, true) → s(quot(x, y))
if_quot(x, y, false, false) → 0
Q is empty.
↳ QTRS
↳ Overlay + Local Confluence
Q restricted rewrite system:
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
quot(x, y) → if_quot(minus(x, y), y, le(y, 0), le(y, x))
if_quot(x, y, true, z) → divByZeroError
if_quot(x, y, false, true) → s(quot(x, y))
if_quot(x, y, false, false) → 0
Q is empty.
The TRS is overlay and locally confluent. By [19] we can switch to innermost.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
Q restricted rewrite system:
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
quot(x, y) → if_quot(minus(x, y), y, le(y, 0), le(y, x))
if_quot(x, y, true, z) → divByZeroError
if_quot(x, y, false, true) → s(quot(x, y))
if_quot(x, y, false, false) → 0
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
Using Dependency Pairs [1,15] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:
QUOT(x, y) → MINUS(x, y)
QUOT(x, y) → LE(y, x)
MINUS(s(x), s(y)) → MINUS(x, y)
QUOT(x, y) → IF_QUOT(minus(x, y), y, le(y, 0), le(y, x))
LE(s(x), s(y)) → LE(x, y)
IF_QUOT(x, y, false, true) → QUOT(x, y)
QUOT(x, y) → LE(y, 0)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
quot(x, y) → if_quot(minus(x, y), y, le(y, 0), le(y, x))
if_quot(x, y, true, z) → divByZeroError
if_quot(x, y, false, true) → s(quot(x, y))
if_quot(x, y, false, false) → 0
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
We have to consider all minimal (P,Q,R)-chains.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
Q DP problem:
The TRS P consists of the following rules:
QUOT(x, y) → MINUS(x, y)
QUOT(x, y) → LE(y, x)
MINUS(s(x), s(y)) → MINUS(x, y)
QUOT(x, y) → IF_QUOT(minus(x, y), y, le(y, 0), le(y, x))
LE(s(x), s(y)) → LE(x, y)
IF_QUOT(x, y, false, true) → QUOT(x, y)
QUOT(x, y) → LE(y, 0)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
quot(x, y) → if_quot(minus(x, y), y, le(y, 0), le(y, x))
if_quot(x, y, true, z) → divByZeroError
if_quot(x, y, false, true) → s(quot(x, y))
if_quot(x, y, false, false) → 0
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 3 SCCs with 3 less nodes.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
LE(s(x), s(y)) → LE(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
quot(x, y) → if_quot(minus(x, y), y, le(y, 0), le(y, x))
if_quot(x, y, true, z) → divByZeroError
if_quot(x, y, false, true) → s(quot(x, y))
if_quot(x, y, false, false) → 0
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
We have to consider all minimal (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
LE(s(x), s(y)) → LE(x, y)
R is empty.
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
LE(s(x), s(y)) → LE(x, y)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- LE(s(x), s(y)) → LE(x, y)
The graph contains the following edges 1 > 1, 2 > 2
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
MINUS(s(x), s(y)) → MINUS(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
quot(x, y) → if_quot(minus(x, y), y, le(y, 0), le(y, x))
if_quot(x, y, true, z) → divByZeroError
if_quot(x, y, false, true) → s(quot(x, y))
if_quot(x, y, false, false) → 0
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
We have to consider all minimal (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
MINUS(s(x), s(y)) → MINUS(x, y)
R is empty.
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
MINUS(s(x), s(y)) → MINUS(x, y)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- MINUS(s(x), s(y)) → MINUS(x, y)
The graph contains the following edges 1 > 1, 2 > 2
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
Q DP problem:
The TRS P consists of the following rules:
QUOT(x, y) → IF_QUOT(minus(x, y), y, le(y, 0), le(y, x))
IF_QUOT(x, y, false, true) → QUOT(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
quot(x, y) → if_quot(minus(x, y), y, le(y, 0), le(y, x))
if_quot(x, y, true, z) → divByZeroError
if_quot(x, y, false, true) → s(quot(x, y))
if_quot(x, y, false, false) → 0
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
We have to consider all minimal (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
Q DP problem:
The TRS P consists of the following rules:
QUOT(x, y) → IF_QUOT(minus(x, y), y, le(y, 0), le(y, x))
IF_QUOT(x, y, false, true) → QUOT(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.
quot(x0, x1)
if_quot(x0, x1, true, x2)
if_quot(x0, x1, false, true)
if_quot(x0, x1, false, false)
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
Q DP problem:
The TRS P consists of the following rules:
QUOT(x, y) → IF_QUOT(minus(x, y), y, le(y, 0), le(y, x))
IF_QUOT(x, y, false, true) → QUOT(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
By narrowing [15] the rule QUOT(x, y) → IF_QUOT(minus(x, y), y, le(y, 0), le(y, x)) at position [2] we obtained the following new rules:
QUOT(y0, s(x0)) → IF_QUOT(minus(y0, s(x0)), s(x0), false, le(s(x0), y0))
QUOT(y0, 0) → IF_QUOT(minus(y0, 0), 0, true, le(0, y0))
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
Q DP problem:
The TRS P consists of the following rules:
QUOT(y0, 0) → IF_QUOT(minus(y0, 0), 0, true, le(0, y0))
QUOT(y0, s(x0)) → IF_QUOT(minus(y0, s(x0)), s(x0), false, le(s(x0), y0))
IF_QUOT(x, y, false, true) → QUOT(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 1 less node.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
Q DP problem:
The TRS P consists of the following rules:
QUOT(y0, s(x0)) → IF_QUOT(minus(y0, s(x0)), s(x0), false, le(s(x0), y0))
IF_QUOT(x, y, false, true) → QUOT(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
By narrowing [15] the rule QUOT(y0, s(x0)) → IF_QUOT(minus(y0, s(x0)), s(x0), false, le(s(x0), y0)) at position [3] we obtained the following new rules:
QUOT(0, s(x0)) → IF_QUOT(minus(0, s(x0)), s(x0), false, false)
QUOT(s(x1), s(x0)) → IF_QUOT(minus(s(x1), s(x0)), s(x0), false, le(x0, x1))
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
Q DP problem:
The TRS P consists of the following rules:
QUOT(0, s(x0)) → IF_QUOT(minus(0, s(x0)), s(x0), false, false)
QUOT(s(x1), s(x0)) → IF_QUOT(minus(s(x1), s(x0)), s(x0), false, le(x0, x1))
IF_QUOT(x, y, false, true) → QUOT(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 1 less node.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
Q DP problem:
The TRS P consists of the following rules:
QUOT(s(x1), s(x0)) → IF_QUOT(minus(s(x1), s(x0)), s(x0), false, le(x0, x1))
IF_QUOT(x, y, false, true) → QUOT(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
By narrowing [15] the rule QUOT(s(x1), s(x0)) → IF_QUOT(minus(s(x1), s(x0)), s(x0), false, le(x0, x1)) at position [0] we obtained the following new rules:
QUOT(s(x0), s(x1)) → IF_QUOT(minus(x0, x1), s(x1), false, le(x1, x0))
QUOT(s(y0), s(y0)) → IF_QUOT(0, s(y0), false, le(y0, y0))
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ Instantiation
Q DP problem:
The TRS P consists of the following rules:
QUOT(s(x0), s(x1)) → IF_QUOT(minus(x0, x1), s(x1), false, le(x1, x0))
QUOT(s(y0), s(y0)) → IF_QUOT(0, s(y0), false, le(y0, y0))
IF_QUOT(x, y, false, true) → QUOT(x, y)
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
By instantiating [15] the rule IF_QUOT(x, y, false, true) → QUOT(x, y) we obtained the following new rules:
IF_QUOT(0, s(z0), false, true) → QUOT(0, s(z0))
IF_QUOT(y_0, s(z1), false, true) → QUOT(y_0, s(z1))
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ Instantiation
↳ QDP
↳ DependencyGraphProof
Q DP problem:
The TRS P consists of the following rules:
IF_QUOT(0, s(z0), false, true) → QUOT(0, s(z0))
IF_QUOT(y_0, s(z1), false, true) → QUOT(y_0, s(z1))
QUOT(s(x0), s(x1)) → IF_QUOT(minus(x0, x1), s(x1), false, le(x1, x0))
QUOT(s(y0), s(y0)) → IF_QUOT(0, s(y0), false, le(y0, y0))
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 1 less node.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ Instantiation
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ ForwardInstantiation
Q DP problem:
The TRS P consists of the following rules:
IF_QUOT(y_0, s(z1), false, true) → QUOT(y_0, s(z1))
QUOT(s(x0), s(x1)) → IF_QUOT(minus(x0, x1), s(x1), false, le(x1, x0))
QUOT(s(y0), s(y0)) → IF_QUOT(0, s(y0), false, le(y0, y0))
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
By forward instantiating [14] the rule IF_QUOT(y_0, s(z1), false, true) → QUOT(y_0, s(z1)) we obtained the following new rules:
IF_QUOT(s(y_0), s(x1), false, true) → QUOT(s(y_0), s(x1))
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ Instantiation
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ ForwardInstantiation
↳ QDP
↳ DependencyGraphProof
Q DP problem:
The TRS P consists of the following rules:
QUOT(s(x0), s(x1)) → IF_QUOT(minus(x0, x1), s(x1), false, le(x1, x0))
IF_QUOT(s(y_0), s(x1), false, true) → QUOT(s(y_0), s(x1))
QUOT(s(y0), s(y0)) → IF_QUOT(0, s(y0), false, le(y0, y0))
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 1 less node.
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ Instantiation
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ ForwardInstantiation
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ QDPOrderProof
Q DP problem:
The TRS P consists of the following rules:
QUOT(s(x0), s(x1)) → IF_QUOT(minus(x0, x1), s(x1), false, le(x1, x0))
IF_QUOT(s(y_0), s(x1), false, true) → QUOT(s(y_0), s(x1))
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].
The following pairs can be oriented strictly and are deleted.
QUOT(s(x0), s(x1)) → IF_QUOT(minus(x0, x1), s(x1), false, le(x1, x0))
The remaining pairs can at least be oriented weakly.
IF_QUOT(s(y_0), s(x1), false, true) → QUOT(s(y_0), s(x1))
Used ordering: Matrix interpretation [3]:
Non-tuple symbols:
| M( minus(x1, x2) ) = | | + | | · | x1 | + | | · | x2 |
| M( le(x1, x2) ) = | | + | | · | x1 | + | | · | x2 |
Tuple symbols:
| M( QUOT(x1, x2) ) = | 0 | + | | · | x1 | + | | · | x2 |
| M( IF_QUOT(x1, ..., x4) ) = | 0 | + | | · | x1 | + | | · | x2 | + | | · | x3 | + | | · | x4 |
Matrix type:
We used a basic matrix type which is not further parametrizeable.
As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order.
The following usable rules [17] were oriented:
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
minus(s(x), s(y)) → minus(x, y)
↳ QTRS
↳ Overlay + Local Confluence
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ UsableRulesProof
↳ QDP
↳ QReductionProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ Narrowing
↳ QDP
↳ Instantiation
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ ForwardInstantiation
↳ QDP
↳ DependencyGraphProof
↳ QDP
↳ QDPOrderProof
↳ QDP
↳ DependencyGraphProof
Q DP problem:
The TRS P consists of the following rules:
IF_QUOT(s(y_0), s(x1), false, true) → QUOT(s(y_0), s(x1))
The TRS R consists of the following rules:
minus(x, x) → 0
minus(0, x) → 0
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
minus(x0, x0)
minus(0, x0)
minus(x0, 0)
minus(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 0 SCCs with 1 less node.