On deciding whether a monoid is a free monoid or is a group (Q1075439): Difference between revisions

Monoids which are described by a given finite presentation (\(\Sigma\) ;R), i.e. \(\Sigma\) is a finite alphabet and R is a finite string-rewriting system on \(\Sigma\), are considered. It is shown that the problem whether or not such a monoid is a free one or a group are undecidable in general. However it is shown that both these problems are effectively reducible to a very restricted form of the uniform word problem. So whenever for some class of presentations this restricted form of the uniform word problem is decidable then the above decision problems become decidable. It is proved that this holds in particular for the class of all presentations involving finite complete string-rewriting systems.