
doi: 10.1007/bf00268077
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.
finite presentation, Generators, relations, and presentations of groups, Free semigroups, generators and relations, word problems, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), finite complete string- rewriting systems, uniform word problem
finite presentation, Generators, relations, and presentations of groups, Free semigroups, generators and relations, word problems, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), finite complete string- rewriting systems, uniform word problem
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 22 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
