YES
0 QTRS
↳1 DependencyPairsProof (⇔, 0 ms)
↳2 QDP
↳3 QDPOrderProof (⇔, 2610 ms)
↳4 QDP
↳5 DependencyGraphProof (⇔, 0 ms)
↳6 AND
↳7 QDP
↳8 QDPSizeChangeProof (⇔, 0 ms)
↳9 YES
↳10 QDP
↳11 QDPSizeChangeProof (⇔, 0 ms)
↳12 YES
circ(cons(a, s), t) → cons(msubst(a, t), circ(s, t))
circ(cons(lift, s), cons(a, t)) → cons(a, circ(s, t))
circ(cons(lift, s), cons(lift, t)) → cons(lift, circ(s, t))
circ(circ(s, t), u) → circ(s, circ(t, u))
circ(s, id) → s
circ(id, s) → s
circ(cons(lift, s), circ(cons(lift, t), u)) → circ(cons(lift, circ(s, t)), u)
subst(a, id) → a
msubst(a, id) → a
msubst(msubst(a, s), t) → msubst(a, circ(s, t))
CIRC(cons(a, s), t) → MSUBST(a, t)
CIRC(cons(a, s), t) → CIRC(s, t)
CIRC(cons(lift, s), cons(a, t)) → CIRC(s, t)
CIRC(cons(lift, s), cons(lift, t)) → CIRC(s, t)
CIRC(circ(s, t), u) → CIRC(s, circ(t, u))
CIRC(circ(s, t), u) → CIRC(t, u)
CIRC(cons(lift, s), circ(cons(lift, t), u)) → CIRC(cons(lift, circ(s, t)), u)
CIRC(cons(lift, s), circ(cons(lift, t), u)) → CIRC(s, t)
MSUBST(msubst(a, s), t) → MSUBST(a, circ(s, t))
MSUBST(msubst(a, s), t) → CIRC(s, t)
circ(cons(a, s), t) → cons(msubst(a, t), circ(s, t))
circ(cons(lift, s), cons(a, t)) → cons(a, circ(s, t))
circ(cons(lift, s), cons(lift, t)) → cons(lift, circ(s, t))
circ(circ(s, t), u) → circ(s, circ(t, u))
circ(s, id) → s
circ(id, s) → s
circ(cons(lift, s), circ(cons(lift, t), u)) → circ(cons(lift, circ(s, t)), u)
subst(a, id) → a
msubst(a, id) → a
msubst(msubst(a, s), t) → msubst(a, circ(s, t))
The following pairs can be oriented strictly and are deleted.
The remaining pairs can at least be oriented weakly.
CIRC(cons(a, s), t) → MSUBST(a, t)
CIRC(cons(a, s), t) → CIRC(s, t)
CIRC(cons(lift, s), cons(a, t)) → CIRC(s, t)
CIRC(cons(lift, s), cons(lift, t)) → CIRC(s, t)
CIRC(cons(lift, s), circ(cons(lift, t), u)) → CIRC(cons(lift, circ(s, t)), u)
CIRC(cons(lift, s), circ(cons(lift, t), u)) → CIRC(s, t)
POL(CIRC(x1, x2)) = x1 + x2
POL(MSUBST(x1, x2)) = x1 + x2
POL(circ(x1, x2)) = x1 + x2
POL(cons(x1, x2)) = 1 + max(x1, x2)
POL(id) = 1
POL(lift) = 1
POL(msubst(x1, x2)) = x1 + x2
circ(cons(a, s), t) → cons(msubst(a, t), circ(s, t))
circ(cons(lift, s), cons(a, t)) → cons(a, circ(s, t))
circ(cons(lift, s), cons(lift, t)) → cons(lift, circ(s, t))
circ(circ(s, t), u) → circ(s, circ(t, u))
circ(s, id) → s
circ(id, s) → s
circ(cons(lift, s), circ(cons(lift, t), u)) → circ(cons(lift, circ(s, t)), u)
msubst(msubst(a, s), t) → msubst(a, circ(s, t))
msubst(a, id) → a
CIRC(circ(s, t), u) → CIRC(s, circ(t, u))
CIRC(circ(s, t), u) → CIRC(t, u)
MSUBST(msubst(a, s), t) → MSUBST(a, circ(s, t))
MSUBST(msubst(a, s), t) → CIRC(s, t)
circ(cons(a, s), t) → cons(msubst(a, t), circ(s, t))
circ(cons(lift, s), cons(a, t)) → cons(a, circ(s, t))
circ(cons(lift, s), cons(lift, t)) → cons(lift, circ(s, t))
circ(circ(s, t), u) → circ(s, circ(t, u))
circ(s, id) → s
circ(id, s) → s
circ(cons(lift, s), circ(cons(lift, t), u)) → circ(cons(lift, circ(s, t)), u)
subst(a, id) → a
msubst(a, id) → a
msubst(msubst(a, s), t) → msubst(a, circ(s, t))
CIRC(circ(s, t), u) → CIRC(t, u)
CIRC(circ(s, t), u) → CIRC(s, circ(t, u))
circ(cons(a, s), t) → cons(msubst(a, t), circ(s, t))
circ(cons(lift, s), cons(a, t)) → cons(a, circ(s, t))
circ(cons(lift, s), cons(lift, t)) → cons(lift, circ(s, t))
circ(circ(s, t), u) → circ(s, circ(t, u))
circ(s, id) → s
circ(id, s) → s
circ(cons(lift, s), circ(cons(lift, t), u)) → circ(cons(lift, circ(s, t)), u)
subst(a, id) → a
msubst(a, id) → a
msubst(msubst(a, s), t) → msubst(a, circ(s, t))
From the DPs we obtained the following set of size-change graphs:
MSUBST(msubst(a, s), t) → MSUBST(a, circ(s, t))
circ(cons(a, s), t) → cons(msubst(a, t), circ(s, t))
circ(cons(lift, s), cons(a, t)) → cons(a, circ(s, t))
circ(cons(lift, s), cons(lift, t)) → cons(lift, circ(s, t))
circ(circ(s, t), u) → circ(s, circ(t, u))
circ(s, id) → s
circ(id, s) → s
circ(cons(lift, s), circ(cons(lift, t), u)) → circ(cons(lift, circ(s, t)), u)
subst(a, id) → a
msubst(a, id) → a
msubst(msubst(a, s), t) → msubst(a, circ(s, t))
From the DPs we obtained the following set of size-change graphs: