5
$\begingroup$

Last week I was recommended Bergman's Diamond Lemma in these comments. I read through the paper, and was working on an exercise in it on page 193:

Examine for termination each of the following singleton reduction-systems on $\mathbf{k}\langle x, y \rangle$: $\{(x^2y, yx)\}$, $\{(yx, x^2y)\}$, $\{(x^2y^2, yx)\}$, $\{(yx, x^2y^2)\}$.

I want to know if the reduction systems $\{(x^2y^2,yx)\}$ and $\{(yx,x^2y^2)\}$ lead to a normal form.

  • The rule $(x^2y^2,yx)$ is length reducing and has no overlap ambiguities, and so $(x^2y^2,yx)$ leads to a normal form.

  • On the other hand, the rule $(yx,x^2y^2)$ has no overlaps. In this case, consider the term $y^2x$. Under this reduction, we have the series of reductions \begin{gather*} y^2x \\ yx^2y^2 \\ x^2y^2xy^2\\ x^2yx^2y^2y^2\\ x^2x^2y^2xy^4\\ x^4yx^2y^2y^4\\ x^4yx^2y^6\\ x^4x^2y^2xy^6\\\vdots \end{gather*} and evidently this term does not reduce to a normal form as there is always some $x$ to the right of some $y$ after performing a reduction.

Did I understand these correctly? I wasn't sure about the second case, since I felt lucky that I chose such a monomial to reduce.

$\endgroup$
2
$\begingroup$

Yeah, you're right. And it's not just a lucky guess of word $y^2x$; it's the perfect example of a word that's not reduction-finite, so you know that the rule $\{(yx,x^2y^2)\}$ won't terminate for every word in $\mathbf{k}\langle x,y \rangle$, and so that rule doesn't give you a normal form. All you need is that one counterexample. :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.