Suppose a semigroup (possibly infinite) presentation is given with generating set $S$ and relations $R$. I need to prove using Bergman's diamond lemma that the semigroup is non-zero i.e, I have to give normal forms of elements of the semigroup. Suppose I could guess the set of irreducible elements and I have also an order on the set of generators $S$. How do I prove that using the diamond lemma that this set is actually a set of reduced words ? How do I find all the ambiguities ?
Asked
Active
Viewed 133 times
1 Answers
3
In general, the word problem for a semigroup $T$ defined by a presentation $\langle\: S\:|\:R\:\rangle$ can be undecidable. This means that, in some cases, if you are given two words over the generators $S$, there is no algorithm to decide whether or not these words represent the same element of $T$. Hence, in such cases, there is no way to find normal forms for the elements of $T$ (if there was, then this would be an algorithm for deciding if two words were equal, just calculate the normal forms and check if they are equal).
If you have a specific presentation for which you want to find the normal forms, then it might be possible to answer your question, but without the details of the presentation, it is not.
James Mitchell
- 2,426