# Bergman's Diamond Lemma: do these rules lead to a normal form?

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.

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. :)