0 QTRS
↳1 Overlay + Local Confluence (⇔)
↳2 QTRS
↳3 DependencyPairsProof (⇔)
↳4 QDP
↳5 DependencyGraphProof (⇔)
↳6 AND
↳7 QDP
↳8 UsableRulesProof (⇔)
↳9 QDP
↳10 QReductionProof (⇔)
↳11 QDP
↳12 QDPSizeChangeProof (⇔)
↳13 TRUE
↳14 QDP
↳15 UsableRulesProof (⇔)
↳16 QDP
↳17 QReductionProof (⇔)
↳18 QDP
↳19 QDPSizeChangeProof (⇔)
↳20 TRUE
↳21 QDP
↳22 UsableRulesProof (⇔)
↳23 QDP
↳24 QReductionProof (⇔)
↳25 QDP
↳26 QDPOrderProof (⇔)
↳27 QDP
↳28 QDPOrderProof (⇔)
↳29 QDP
↳30 DependencyGraphProof (⇔)
↳31 TRUE
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
gcd(0, y) → y
gcd(s(x), 0) → s(x)
gcd(s(x), s(y)) → if_gcd(le(y, x), s(x), s(y))
if_gcd(true, s(x), s(y)) → gcd(minus(x, y), s(y))
if_gcd(false, s(x), s(y)) → gcd(minus(y, x), s(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
gcd(0, y) → y
gcd(s(x), 0) → s(x)
gcd(s(x), s(y)) → if_gcd(le(y, x), s(x), s(y))
if_gcd(true, s(x), s(y)) → gcd(minus(x, y), s(y))
if_gcd(false, s(x), s(y)) → gcd(minus(y, x), s(x))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
LE(s(x), s(y)) → LE(x, y)
MINUS(s(x), s(y)) → MINUS(x, y)
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
GCD(s(x), s(y)) → LE(y, x)
IF_GCD(true, s(x), s(y)) → GCD(minus(x, y), s(y))
IF_GCD(true, s(x), s(y)) → MINUS(x, y)
IF_GCD(false, s(x), s(y)) → GCD(minus(y, x), s(x))
IF_GCD(false, s(x), s(y)) → MINUS(y, x)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
gcd(0, y) → y
gcd(s(x), 0) → s(x)
gcd(s(x), s(y)) → if_gcd(le(y, x), s(x), s(y))
if_gcd(true, s(x), s(y)) → gcd(minus(x, y), s(y))
if_gcd(false, s(x), s(y)) → gcd(minus(y, x), s(x))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
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)
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
gcd(0, y) → y
gcd(s(x), 0) → s(x)
gcd(s(x), s(y)) → if_gcd(le(y, x), s(x), s(y))
if_gcd(true, s(x), s(y)) → gcd(minus(x, y), s(y))
if_gcd(false, s(x), s(y)) → gcd(minus(y, x), s(x))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
MINUS(s(x), s(y)) → MINUS(x, y)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
MINUS(s(x), s(y)) → MINUS(x, y)
From the DPs we obtained the following set of size-change graphs:
LE(s(x), s(y)) → LE(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
gcd(0, y) → y
gcd(s(x), 0) → s(x)
gcd(s(x), s(y)) → if_gcd(le(y, x), s(x), s(y))
if_gcd(true, s(x), s(y)) → gcd(minus(x, y), s(y))
if_gcd(false, s(x), s(y)) → gcd(minus(y, x), s(x))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
LE(s(x), s(y)) → LE(x, y)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
LE(s(x), s(y)) → LE(x, y)
From the DPs we obtained the following set of size-change graphs:
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
IF_GCD(true, s(x), s(y)) → GCD(minus(x, y), s(y))
IF_GCD(false, s(x), s(y)) → GCD(minus(y, x), s(x))
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)
gcd(0, y) → y
gcd(s(x), 0) → s(x)
gcd(s(x), s(y)) → if_gcd(le(y, x), s(x), s(y))
if_gcd(true, s(x), s(y)) → gcd(minus(x, y), s(y))
if_gcd(false, s(x), s(y)) → gcd(minus(y, x), s(x))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
IF_GCD(true, s(x), s(y)) → GCD(minus(x, y), s(y))
IF_GCD(false, s(x), s(y)) → GCD(minus(y, x), s(x))
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)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, s(x0), s(x1))
if_gcd(false, s(x0), s(x1))
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
IF_GCD(true, s(x), s(y)) → GCD(minus(x, y), s(y))
IF_GCD(false, s(x), s(y)) → GCD(minus(y, x), s(x))
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)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
The following pairs can be oriented strictly and are deleted.
The remaining pairs can at least be oriented weakly.
IF_GCD(true, s(x), s(y)) → GCD(minus(x, y), s(y))
POL(0) = 0
POL(GCD(x1, x2)) = 1 + x1 + x2
POL(IF_GCD(x1, x2, x3)) = x1 + x2 + x3
POL(false) = 0
POL(le(x1, x2)) = 1
POL(minus(x1, x2)) = x1
POL(s(x1)) = 1 + x1
POL(true) = 1
le(s(x), s(y)) → le(x, y)
le(s(x), 0) → false
le(0, y) → true
minus(s(x), s(y)) → minus(x, y)
minus(x, 0) → x
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
IF_GCD(false, s(x), s(y)) → GCD(minus(y, x), s(x))
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)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))
The following pairs can be oriented strictly and are deleted.
The remaining pairs can at least be oriented weakly.
IF_GCD(false, s(x), s(y)) → GCD(minus(y, x), s(x))
POL(0) = 0
POL(GCD(x1, x2)) = x1 + x2
POL(IF_GCD(x1, x2, x3)) = x2 + x3
POL(false) = 0
POL(le(x1, x2)) = 0
POL(minus(x1, x2)) = x1
POL(s(x1)) = 1 + x1
POL(true) = 0
minus(s(x), s(y)) → minus(x, y)
minus(x, 0) → x
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
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)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(s(x0), s(x1))