On regularity and the word problem for free idempotent generated semigroups
Igor Dolinka, Robert D. Gray, Nik Ruškuc · Proceedings of the London Mathematical Society · 2017
The category of all idempotent generated semigroups with a prescribed structure E of their idempotents E (called the biordered set) has an initial object called the free idempotent generated semigroup over E, defined by a presentation over alphabet E and denoted by IG ( E ) . Recently, much effort has been put into investigating the structure of semigroups of the form IG ( E ) , especially regarding their maximal subgroups. In this paper, we take these investigations in a new direction by considering the word problem for IG ( E ) . We prove two principal results, one positive and one negative. We show that, for a finite biordered set E, it is decidable whether a given word w ∈ E ∗ represents a regular element; if in addition one assumes that all maximal subgroups of IG ( E ) have decidable word problems, then the word problem in IG ( E ) restricted to regular words is decidable. On the other hand, we exhibit a biorder E arising from a finite idempotent semigroup S, such that the word problem for IG ( E ) is undecidable, even though all the maximal subgroups have decidable word problems. This is achieved by relating the word problem of IG ( E ) to the subgroup membership problem in finitely presented groups.