A 2013 note of Victor Maltcev launched the semigroup analogue of the Boone–Higman programme: taking congruence-free semigroups as the counterpart of simple groups, he proved that every finite semigroup embeds in a finitely presented congruence-free monoid and asked how far this extends. This task asks: (A) does every finitely generated semigroup with soluble word problem embed into a finitely presented congruence-free semigroup or monoid; and, from the same note, (B) does every finitely presented semigroup embed into a finitely presented bisimple monoid, (C) into a finitely presented regular monoid — questions the source says in effect ask whether bisimplicity and regularity are Markov properties of finitely presented semigroups. All three strands remain open for the general finitely generated case with a finitely presented container, the cases settled classically being the finite case and the countable embeddings into congruence-free containers that are not finitely presented.

Background

A semigroup is a set with an associative binary operation, and a monoid is a semigroup with an identity element. A semigroup is finitely generated if it is generated by a finite set of elements and finitely presented if it is given by finitely many generators subject to finitely many defining relations, i.e. it is a quotient of a free semigroup by the congruence generated by finitely many pairs of words. The word problem for a finitely presented semigroup asks for an algorithm deciding whether two words over the generators represent the same element; the word problem is called soluble (decidable) if such an algorithm exists, and finitely presented semigroups and monoids may have unsolvable word problem. A congruence on a semigroup is an equivalence relation compatible with multiplication, so quotients correspond to congruences, and a semigroup is congruence-free if it admits only the two trivial congruences; for groups, congruence-free is the same as simple, which is why congruence-free semigroups serve as the semigroup analogue of simple groups. A semigroup is regular if for every element aa there is an element xx with axa=aaxa=a (every group is regular, taking x=a−1x=a^{-1}). Green's relations L\mathcal{L} and R\mathcal{R} relate two elements of a semigroup when they generate the same principal left, respectively right, ideal; Green's relation D\mathcal{D} is their join, that is, a D ba\,\mathcal{D}\,b if and only if there is an element cc with a L ca\,\mathcal{L}\,c and c R bc\,\mathcal{R}\,b; Green's relation H\mathcal{H} is L∩R\mathcal{L}\cap\mathcal{R}, and a semigroup with a single D\mathcal{D}-class is called bisimple. A property of semigroups is a Markov property (in the sense of the Adian–Rabin–Markov framework for finitely presented algebras) if it is enjoyed by at least one finitely presented semigroup and avoided by at least one finitely presented semigroup that embeds into no finitely presented semigroup with the property; a classical theorem of A. A. Markov (1947, for associative systems) states that every Markov property is algorithmically undecidable for finitely presented semigroups.

Boone and Higman proved in 1974 that a finitely generated group has soluble word problem if and only if it embeds into a simple subgroup of a finitely presented group, and asked the still-open Boone–Higman conjecture: does every finitely generated group with soluble word problem embed into a finitely presented simple group? For semigroups the landscape is different in two decisive ways. On one hand, Bruck–Reilly extensions — a classical construction that embeds a finitely generated (respectively finitely presented) semigroup into a simple finitely generated (respectively finitely presented) semigroup — already place any finitely presented semigroup inside a finitely presented simple semigroup, as recounted in Maltcev's note, so 'simple' is not the correct semigroup analogue: the target must be congruence-free. On the other hand, Byleen proved in 1990 that every countable semigroup embeds into a 2-generated congruence-free semigroup, so the embedding statement holds at the countable level, but the container is far from finitely presented; Byleen also proved in 1984 that every countable semigroup embeds into a 2-generated bisimple monoid. The tension between 'congruence-free' (or 'regular', or 'bisimple') and 'finitely presented' is exactly what is unresolved.

Maltcev's 2013 note began this programme: he proved that every finite semigroup embeds into a finitely presented congruence-free monoid, via an explicit finite complete rewriting presentation (a finite set of rewriting rules that terminates and gives every element a unique normal form, so that the word problem of the container is decidable), and posed two embedding questions — whether every finitely presented semigroup embeds into a finitely presented bisimple monoid, and whether every finitely presented semigroup embeds into a finitely presented regular monoid — remarking that these in effect ask whether bisimplicity and regularity are Markov properties, in the sense of the decision-problem study of Cain and Maltcev (2009). Companion papers of 2013–2015 constructed explicit families of finitely presented congruence-free monoids (a countable series of bisimple H\mathcal{H}-trivial ones, i.e. ones in which H\mathcal{H} is the identity relation; a simple non-bisimple one; a countable family of infinite ones), showing that such containers exist in some abundance, but no embedding theorem beyond the finite case is known.

Problem Statement

Determine whether finitely presented congruence-free, regular, and bisimple semigroups and monoids are universal containers in the Boone–Higman sense. Specifically, with 'embed' meaning injective homomorphism:

  1. (Semigroup Boone–Higman question, the declared programme of Maltcev's note) Does every finitely generated semigroup with soluble word problem embed into a finitely presented congruence-free semigroup, or into a finitely presented congruence-free monoid? (A finitely presented congruence-free monoid is itself a finitely presented congruence-free semigroup, so the monoid form is the stronger variant. This sub-question is settled by an affirmative answer in either form, or by a negative answer exhibiting a finitely generated semigroup with soluble word problem that embeds into neither container; a negative answer for the monoid form alone does not settle it.) The finite case is settled affirmatively (Maltcev 2013); every countable semigroup embeds into a 2-generated congruence-free semigroup (Byleen 1990), but that container is not finitely presented, and the question concerns the general finitely generated case with a finitely presented container.
  2. (Maltcev's Question 1.2) Does every finitely presented semigroup embed into a finitely presented bisimple monoid, i.e. a finitely presented monoid with a single Green D\mathcal{D}-class?
  3. (Maltcev's Question 1.3) Does every finitely presented semigroup embed into a finitely presented regular monoid, i.e. one in which every element aa admits an element xx with axa=aaxa=a?
  4. (Markov-property reading of Questions 1.2 and 1.3 in the source) The source states that Questions 1.2 and 1.3 in effect ask whether bisimplicity and regularity are Markov properties of finitely presented semigroups. Since finitely presented bisimple and regular monoids are known to exist (the companion constructions above), the positive-witness side of the Background definition is satisfied; the open content of this reading is whether there exists a finitely presented semigroup that embeds into no finitely presented semigroup with the property — which, together with the known positive witnesses, would make the property Markov and hence algorithmically undecidable. In the monoid-container form of Questions 1.2 and 1.3, a finitely presented semigroup that embeds into no finitely presented bisimple (respectively regular) monoid is such a witness directly for regularity (every finitely presented regular semigroup embeds in the finitely presented regular monoid obtained by adjoining an identity), while for bisimplicity the semigroup- and monoid-target obstructions need not coincide.

These four questions state one common objective from a single source: whether the algebraic Boone–Higman characterization of solvable word problems, and the related decision-theoretic (Markov property) questions, can be extended from groups to semigroups by exhibiting finitely presented congruence-free, regular, or bisimple containers, or by proving that no such universal containers exist. They are related rather than independent, though answering any one of them is a result in its own right: because every bisimple monoid is regular, an affirmative answer to question 2 settles question 3; the regularity content of question 4 is the negation of question 3; and the bisimplicity content of question 4 concerns the semigroup rather than the monoid container and need not coincide with question 2. Each of the embedding questions 1–3 is settled by a finitely presented container of the required kind exhibiting the embedding, or by a witness semigroup admitting no such embedding (for question 1, a finitely generated semigroup with soluble word problem embedding into neither congruence-free container; for questions 2 and 3, a finitely presented semigroup admitting none), and question 4 by deciding the Markov-property reading it states.

References

  1. Victor Maltcev, "Finite semigroups embed in finitely presented congruence-free monoids", Journal of Algebra 389 (2013) 1–5, DOI 10.1016/j.jalgebra.2013.05.015; arXiv:1301.5336. https://doi.org/10.1016/j.jalgebra.2013.05.015 and https://arxiv.org/abs/1301.5336
  2. W. W. Boone and G. Higman, "An algebraic characterization of groups with soluble word problem", Journal of the Australian Mathematical Society 18 (1974) 41–53, DOI 10.1017/s1446788700019108. https://doi.org/10.1017/s1446788700019108
  3. K. Byleen, "Embedding any countable semigroup in a 2-generated congruence-free semigroup", Semigroup Forum 41 (1990) 145–153, DOI 10.1007/bf02573385. https://doi.org/10.1007/bf02573385
  4. K. Byleen, "Embedding any countable semigroup in a 2-generated bisimple monoid", Glasgow Mathematical Journal 25 (1984) 153–161, DOI 10.1017/s0017089500005565. https://doi.org/10.1017/s0017089500005565
  5. Alan J. Cain and Victor Maltcev, "Decision problems for finitely presented and one-relation semigroups and monoids", International Journal of Algebra and Computation 19 (2009) 747–770, DOI 10.1142/s0218196709005366. https://doi.org/10.1142/s0218196709005366
  6. Victor Maltcev, "A countable series of bisimple H\mathcal{H}-trivial finitely presented congruence-free monoids", Semigroup Forum 88 (2014) 279–285; published online 2013. DOI 10.1007/s00233-013-9508-5; arXiv:1301.5343. https://doi.org/10.1007/s00233-013-9508-5 and https://arxiv.org/abs/1301.5343
  7. Alan J. Cain and Victor Maltcev, "A simple non-bisimple congruence-free finitely presented monoid", Semigroup Forum 90 (2015) 184–188; published online 2014. DOI 10.1007/s00233-014-9607-y; arXiv:1307.6580. https://doi.org/10.1007/s00233-014-9607-y and https://arxiv.org/abs/1307.6580
  8. F. Al-Kharousi, Alan J. Cain, Victor Maltcev and A. Umar, "A countable family of finitely presented infinite congruence-free monoids", Acta Scientiarum Mathematicarum (Szeged) 81 (2015) 437–445, DOI 10.14232/actasm-013-028-z; arXiv:1304.4687. https://doi.org/10.14232/actasm-013-028-z and https://arxiv.org/abs/1304.4687
  9. J. Belk, C. Bleak, F. Matucci and M. C. B. Zaremsky, "Progress around the Boone–Higman conjecture", EMS Surveys in Mathematical Sciences (published 2025; arXiv 2023), DOI 10.4171/emss/101; arXiv:2306.16356. https://doi.org/10.4171/emss/101 and https://arxiv.org/abs/2306.16356
  10. J. Belk, C. Bleak, F. Matucci and M. C. B. Zaremsky, "Hyperbolic groups satisfy the Boone–Higman conjecture", Duke Mathematical Journal 175 (9) (2026), DOI 10.1215/00127094-2025-0055; arXiv:2309.06224. https://doi.org/10.1215/00127094-2025-0055 and https://arxiv.org/abs/2309.06224