YES
0 QTRS
↳1 Overlay + Local Confluence (⇔, 4 ms)
↳2 QTRS
↳3 DependencyPairsProof (⇔, 0 ms)
↳4 QDP
↳5 DependencyGraphProof (⇔, 0 ms)
↳6 AND
↳7 QDP
↳8 UsableRulesProof (⇔, 0 ms)
↳9 QDP
↳10 QReductionProof (⇔, 0 ms)
↳11 QDP
↳12 QDPSizeChangeProof (⇔, 0 ms)
↳13 YES
↳14 QDP
↳15 UsableRulesProof (⇔, 0 ms)
↳16 QDP
↳17 QReductionProof (⇔, 0 ms)
↳18 QDP
↳19 QDPSizeChangeProof (⇔, 0 ms)
↳20 YES
↳21 QDP
↳22 UsableRulesProof (⇔, 0 ms)
↳23 QDP
↳24 QReductionProof (⇔, 0 ms)
↳25 QDP
↳26 QDPQMonotonicMRRProof (⇔, 18 ms)
↳27 QDP
↳28 TransformationProof (⇔, 0 ms)
↳29 QDP
↳30 DependencyGraphProof (⇔, 0 ms)
↳31 QDP
↳32 TransformationProof (⇔, 0 ms)
↳33 QDP
↳34 DependencyGraphProof (⇔, 0 ms)
↳35 TRUE
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
minus(x, 0) → x
minus(0, x) → 0
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, x, y) → gcd(minus(x, y), y)
if_gcd(false, x, y) → gcd(minus(y, x), x)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
minus(x, 0) → x
minus(0, x) → 0
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, x, y) → gcd(minus(x, y), y)
if_gcd(false, x, y) → gcd(minus(y, x), x)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, 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, x, y) → GCD(minus(x, y), y)
IF_GCD(true, x, y) → MINUS(x, y)
IF_GCD(false, x, y) → GCD(minus(y, x), x)
IF_GCD(false, x, 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(0, x) → 0
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, x, y) → gcd(minus(x, y), y)
if_gcd(false, x, y) → gcd(minus(y, x), x)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, 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(0, x) → 0
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, x, y) → gcd(minus(x, y), y)
if_gcd(false, x, y) → gcd(minus(y, x), x)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, 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(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, x1)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, 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(0, x) → 0
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, x, y) → gcd(minus(x, y), y)
if_gcd(false, x, y) → gcd(minus(y, x), x)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, 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(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, x1)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, 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, x, y) → GCD(minus(x, y), y)
IF_GCD(false, x, y) → GCD(minus(y, x), x)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
minus(x, 0) → x
minus(0, x) → 0
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, x, y) → gcd(minus(x, y), y)
if_gcd(false, x, y) → gcd(minus(y, x), x)
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
minus(x0, 0)
minus(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, x1)
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
IF_GCD(true, x, y) → GCD(minus(x, y), y)
IF_GCD(false, x, y) → GCD(minus(y, x), x)
minus(x, 0) → x
minus(0, x) → 0
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(0, x0)
minus(s(x0), s(x1))
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, x1)
gcd(0, x0)
gcd(s(x0), 0)
gcd(s(x0), s(x1))
if_gcd(true, x0, x1)
if_gcd(false, x0, x1)
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
IF_GCD(true, x, y) → GCD(minus(x, y), y)
IF_GCD(false, x, y) → GCD(minus(y, x), x)
minus(x, 0) → x
minus(0, x) → 0
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(0, x0)
minus(s(x0), s(x1))
minus(s(x), s(y)) → minus(x, y)
POL(0) = 0
POL(GCD(x1, x2)) = 2·x1 + 2·x2
POL(IF_GCD(x1, x2, x3)) = 2·x2 + 2·x3
POL(false) = 0
POL(le(x1, x2)) = 0
POL(minus(x1, x2)) = x1
POL(s(x1)) = 1 + x1
POL(true) = 0
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
IF_GCD(true, x, y) → GCD(minus(x, y), y)
IF_GCD(false, x, y) → GCD(minus(y, x), x)
minus(x, 0) → x
minus(0, x) → 0
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(0, x0)
minus(s(x0), s(x1))
IF_GCD(true, x0, 0) → GCD(x0, 0) → IF_GCD(true, x0, 0) → GCD(x0, 0)
IF_GCD(true, 0, x0) → GCD(0, x0) → IF_GCD(true, 0, x0) → GCD(0, x0)
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
IF_GCD(false, x, y) → GCD(minus(y, x), x)
IF_GCD(true, x0, 0) → GCD(x0, 0)
IF_GCD(true, 0, x0) → GCD(0, x0)
minus(x, 0) → x
minus(0, x) → 0
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(0, x0)
minus(s(x0), s(x1))
IF_GCD(false, x, y) → GCD(minus(y, x), x)
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
minus(x, 0) → x
minus(0, x) → 0
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(0, x0)
minus(s(x0), s(x1))
IF_GCD(false, 0, x0) → GCD(x0, 0) → IF_GCD(false, 0, x0) → GCD(x0, 0)
IF_GCD(false, x0, 0) → GCD(0, x0) → IF_GCD(false, x0, 0) → GCD(0, x0)
GCD(s(x), s(y)) → IF_GCD(le(y, x), s(x), s(y))
IF_GCD(false, 0, x0) → GCD(x0, 0)
IF_GCD(false, x0, 0) → GCD(0, x0)
minus(x, 0) → x
minus(0, x) → 0
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(0, x0)
minus(s(x0), s(x1))