# Prefix monoids of groups and right units of special inverse monoids

###### Abstract.

A prefix monoid is a finitely generated submonoid of a finitely presented
group generated by the prefixes of its defining relators. Important results of
Guba (1997), and of Ivanov, Margolis and Meakin (2001), show how the word
problem for certain one-relator monoids, and inverse monoids, can be reduced
to solving the membership problem in prefix monoids of certain one-relator
groups. Motivated by this, in this paper we study the class of prefix monoids
of finitely presented groups. We obtain a complete description of this class
of monoids. All monoids in this family are finitely generated, recursively
presented and group-embeddable. Our results show that not every finitely
generated recursively presented group-embeddable monoid is a prefix monoid,
but for every such monoid if we take a free product with a suitably chosen
free monoid of finite rank, then we do obtain a prefix monoid. Conversely we
prove that every prefix monoid arises in this way. Also, we show that the
groups that arise as groups of units of prefix monoids are precisely the
finitely generated recursively presented groups, while the groups that arise
as Schützenberger groups of prefix monoids are exactly the recursively
enumerable subgroups of finitely presented groups. We obtain an analogous
result classifying the Schützenberger groups of monoids of right units of
special inverse monoids. We also give some examples of right cancellative
monoids arising as monoids of right units of finitely presented special
inverse monoids, and show that not all right cancellative recursively
presented monoids belong to this class.

###### Key words and phrases:

Prefix monoid; Right units; Special inverse monoid; Higman Embedding Theorem;
Schützenberger group

###### 2020 Mathematics Subject Classification:

20M05; 20F05, 20M18

IGOR DOLINKA 111 Department of Mathematics and Informatics, University of Novi
Sad, Trg Dositeja Obradovića 4, 21101 Novi Sad, Serbia.
_Email address:_<EMAIL_ADDRESS>and ROBERT D. GRAY222School of
Mathematics, University of East Anglia, Norwich NR4 7TJ, England.
_Email address:_<EMAIL_ADDRESS>
##  1\. Introduction

The main themes of the present paper draw inspiration from the beautiful
algebraic theory surrounding one of the longest standing and most important
open problems in combinatorial algebra and semigroup theory: the word problem
for one-relator monoids. The classical result of Magnus [21] that all one-
relator groups have algorithmically decidable word problems, as well as the
method [20] it entails, is one of the cornerstones of combinatorial group
theory [19]. On the other hand, the question of decidability the word problem
for one-relator monoids has been a subject of a series of serious attacks,
most notably by Adian [1] and his students, among others. We refer to the
survey [29] for a thorough historical account of this fascinating topic.

There have been notable partial successes for the word problem of one-relator
monoids, perhaps the most glaring being the case of _special_ one-relator
monoids, those of the form $\operatorname{Mon}\langle{A}\,|\,{w=1}\rangle$,
where the word problem is always decidable. This result was proved by Adjan
[1] who also showed that these one-relator monoids have several other good
algebraic properties. For example, he proved that the group of units of a one-
relator special monoid $M$ is a one-relator group. Later, Makanin [22]
generalised this by showing that for any special monoid $M$, that is, one
given by defining relations of the form $w_{i}=1$, $i\in I$, the corresponding
group of units can be defined by no more relations than in the original
presentation for $M$. Furthermore, all maximal subgroups of a special monoid
$M$ must be isomorphic to its group of units [23], while the submonoids of
_right units_ (right invertible elements) always turn out to be free products
of the group of units and a free monoid (of finite rank, in the case when $M$
is finitely presented). See also the related work of Lallement [17] and Zhang
[34, 35].

Today we know, due to Adian and Oganessian [2], that the general one-relator
problem for monoids reduces to the cases of the form
$\operatorname{Mon}\langle{a,b}\,|\,{aub=ava}\rangle$ and
$\operatorname{Mon}\langle{a,b}\,|\,{aub=a}\rangle$, where
$u,v\in\\{a,b\\}^{*}$ are arbitrary words. All monoids in these reduced cases
are right cancellative, and this spurred Ivanov, Margolis and Meakin [15] to
introduce yet another type of algebraic structure into the discourse: _inverse
monoids_ , more precisely _special_ inverse monoids, ones given by
presentations of the form $\operatorname{Inv}\langle{A}\,|\,{w_{i}=1\;(i\in
I)}\rangle$. By embedding a right cancellative one-relator monoid into a one-
relator special inverse monoid, they proved that the word problem for
(ordinary) one-relator monoids reduces to the word problem for one-relator
special inverse monoids. However, surprisingly, the second-named author of
this paper has recently shown in [8] that there _exist_ one-relator special
inverse monoids in which the word problem is undecidable. Still, this does not
invalidate the approach suggested in [15], as the reduction presented there
always produces a reduced—albeit not cyclically reduced—relator word, while
the relator words constructed in [8] are necessarily non-reduced.

The connection between prefix monoids of groups and the submonoid of right
units (i.e. right invertible elements) of special inverse monoids comes from
the fact that the natural surjective homomorphism from a special inverse
monoid $T=\operatorname{Inv}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$ to its
maximal group image $G=\operatorname{Gp}\langle{A}\,|\,{w_{i}=1\;(i\in
I)}\rangle$ maps the submonoid $R$ of right units of $T$ surjectively to the
_prefix monoid_ of $G$, with respect to this presentation. Here the prefix
monoid $P$ is the submonoid of $G$ generated by all elements represented by
the prefixes of the relator words $w_{i}\;(i\in I)$. In general this
homomorphism from $R$ onto $P$ is not injective, but it is in the case that
$T$ is an _$E$ -unitary_ inverse monoid. There are many equivalent
definitions, but for our purposes it is the best to express it in the
following way: $T=\operatorname{Inv}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$
is $E$-unitary if in the natural homomorphism from $T$ to its greatest group
image $G=\operatorname{Gp}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$ the only
pre-images of the identity element of $G$ are the idempotents of $T$. Now, yet
another major result of [15] shows that when
$T=\operatorname{Inv}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$ is $E$-unitary
then, provided $\operatorname{Gp}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$
has decidable word problem, the decidability of the word problem of $T$
reduces to the membership problem for the prefix monoid of $G$. In the same
paper they also prove that when $w$ is a cyclically reduced word then
$\operatorname{Inv}\langle{A}\,|\,{w=1}\rangle$ is $E$-unitary and thus the
word problem reduces to the prefix membership problem for the corresponding
one-relator group in this case. The prefix membership problem for one-relator
groups have been studied by several authors, e.g. in [16, 25], and more
recently by the present authors in [7]. The close connections between prefix
monoids of groups and right units of special inverse monoids described above
mean that it is natural to investigate both classes in parallel.

Further motivation for the study of the right units of special inverse monoids
comes from the fact that the main undecidability results [8] are proved by
constructing special inverse monoids in which membership in the submonoid of
right units is undecidable. Also, the relevance of the study of prefix monoids
is highlighted by important work of Guba [11]. As mentioned above the word
problem remains open for monoids of the form
$\operatorname{Mon}\langle{a,b}\,|\,{a=aub}\rangle$. It follows from the
results of Guba [11] that the word problem for one-relator monoids of the form
$\operatorname{Mon}\langle{a,b}\,|\,{a=aub}\rangle$, $u\in\\{a,b\\}^{*}$,
reduces to the prefix membership problem in one-relator groups of the form
$\operatorname{Gp}\langle{x,y,C}\,|\,{xUyx^{-1}=1}\rangle$ where $x\neq y$,
$C$ is a finite alphabet, and $U$ is a positive word over $\\{x,y\\}\cup C$.
The prefix membership problem for this class of one-relator group
presentations remains open.

For brevity we shall use the expression _prefix monoid_ to always mean a
monoid isomorphic to the prefix monoid of some finitely presented group, and
by an _RU-monoid_ we mean one that is isomorphic to the submonoid of right
units of some finitely presented special inverse monoid. In this paper we are
shall consider the following four questions:

  * (1)

Which monoids are prefix monoids?

  * (2)

Which monoids are RU-monoids?

  * (3)

What can the groups of units of these monoids be?

  * (4)

What can the Schützenberger groups of these monoids be?

For prefix monoids we shall obtain complete answers to all these questions,
that is, we answer (1), (3) and (4) in this case. By the very definition,
prefix monoids are all finitely generated, recursively presented and group-
embeddable. Thus it is natural to wonder whether the answer to (1) could be
exactly the class of finitely generated, recursively presented and group-
embeddable monoids. It turns out this is not the case. Our results will show
that not every finitely generated recursively presented group-embeddable
monoid is a prefix monoid, but for every such monoid if we take a free product
with a suitably chosen free monoid of finite rank, then we do obtain a prefix
monoid. Conversely we prove that every prefix monoid arises in this way, thus
answering question (1); see Theorem 3.6. Concerning the subgroups of prefix
monoids, since any group-embeddable (and, more generally, any right
cancellative) monoid can have only a single idempotent, namely the identity
element, it follows that the only maximal subgroup this the prefix monoid has
is its group of units. We are going to answer (3) for prefix monoids by
showing (in Theorem 4.3) that the class of groups of units of prefix monoids
is precisely the class of finitely generated recursively presented groups
(which, by the Higman Embedding Theorem [12], is precisely the class of all
finitely generated subgroups of finitely presented groups). Lacking any other
subgroups, semigroup theory provides us with “hidden” group structures within
arbitrary monoids, the so-called _Schützenberger groups_ (defined in a precise
fashion in the next section), which are generalisations of the notion of
maximal subgroups to all (including non-regular) $\mathscr{D}$-classes of a
semigroup. We shall answer question (4) for prefix monoid in Theorem 4.5 where
we show that the class of Schützenberger groups of all prefix monoids is
precisely the class of recursively enumerable subgroups of finitely presented
groups.

The structure of RU-monoids is more complex than that of prefix monoids. RU-
monoids were studied in [10] where it was shown that the RU-monoid of a one-
relator special inverse monoid need not be finitely presented, and need not
decompose as a free product of the groups of units and a free monoid (as they
do in the case of non-inverse special monoids). By definition all RU-monoids
are right cancellative and recursively presented. We shall see that not every
right cancellative recursively presented monoid is an RU-monoid. Conversely we
shall identify a large class of monoids that do all arise as RU monoids,
called _finitely RC-presented monoids_. While the problem of completely
describing RU-monoids remains open, we do succeed in classifying their
Schützenberger groups. For the groups of units of RU-monoids this question was
answered in the recent paper [9, Theorem 4.1] where the groups of units of
finitely presented inverse monoids are shown to be precisely the finitely
generated recursively presented groups. Since the group of units of the right
units $U$ of a special inverse monoid $M$ is equal to the group of units of
the submonoid of right units $R$ of $M$, it follows from [9, Theorem 4.1] that
the groups of units of RU-monoids are exactly the finitely generated
recursively presented groups. So that result answers question (3) for RU-
monoids. In our final main result (Theorem 5.6) we answer question (4) for RU-
monoids showing that the class of Schützenberger groups of all prefix monoids
is precisely the class of recursively enumerable subgroups of finitely
presented groups. Hence while prefix monoids and RU-monoids are in general
wildly different classes of monoids, on the level of groups of units and
Schützenberger groups the possible behaviours coincide.

The remainder of the paper consists of four sections beyond this introduction:
one of preliminary nature where we accumulate the necessary notions and
prerequisites, followed by two sections concerned with characterisations of
prefix monoids and their associated groups, respectively, and the final
section dealing with RU-monoids.

##  2\. Preliminaries

###  2.1. Presentations, prefix monoids, RU-monoids

In the course of working with monoids, inverse monoids and groups, and
presentations thereof, we shall be concerned with alphabets representing their
generating sets (finite or infinite), such as $A$ in the monoid case and
“doubled alphabets” $\overline{A}=A\cup A^{-1}$ in the inverse monoid and
group case. To represent elements of these structures, we use words over these
alphabets. The _free monoid_ $A^{*}$ consists of all words (finite sequences
of letters) over $A$. The _free group_ $FG(A)$ on $A$ is defined on a subset
of $\overline{A}^{*}$ whose elements are called _reduced words_ : these are
words that do not contain subwords of the form $aa^{-1}$ and $a^{-1}a$ for any
$a\in A$. Every word $w\in\overline{A}^{*}$ has its _reduced form_
$\operatorname{red}(w)$ obtained by successively removing subwords of the
indicated form; the reduced form of a word is unique as this process can be
shown to be confluent. So, in $FG(A)$, $u\cdot v=\operatorname{red}(uv)$. For
any letter $a\in A$ we define $(a^{-1})^{-1}=a$ and then for any word
$a_{1}\ldots a_{k}\in\overline{A}^{*}$ we define $(a_{1}\ldots
a_{k})^{-1}=a_{k}^{-1}\ldots a_{1}^{-1}$. With this notation if $w$ is a
reduced word then $w^{-1}$ is the unique reduced word representing the inverse
of $w$ in the free group. Finally, the _free inverse monoid_ $FIM(A)$ is
obtained as the quotient of the free monoid $\overline{A}^{*}$ by the so-
called _Wagner congruence_ , generated by the pairs $(uu^{-1}u,u)$ and
$(uu^{-1}vv^{-1},vv^{-1}uu^{-1})$ for all $u,v\in\overline{A}^{*}$. An elegant
geometric description of $FIM(A)$, with elements represented as finite
connected birooted subgraphs of the Cayley graph of $FG(A)$, was given by Munn
[27] (see also Scheiblich [31]), thus explaining the term _Munn trees_ used
for such graphs.

Combinatorial algebra studies algebraic structures by representing then using
_presentations_ : as quotients of corresponding free structures by certain
congruences whose generating pairs are written as “defining relations” (or
_relators_). So, for a monoid we write
$M=\operatorname{Mon}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in I)}\rangle$ if $M\cong
A^{*}/\theta$ where $\theta$ is the congruence of the free monoid $A^{*}$
generated by the set of pairs of words $\\{(u_{i},v_{i}):\ i\in I\\}$.
Analogously $T=\operatorname{Inv}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in
I)}\rangle$ is defined to be the quotient of the free inverse monoid $FIM(A)$
by the congruence on $FIM(A)$ generated by the set of pairs of words
$\\{(u_{i},v_{i}):\ i\in I\\}$. Finally, for a group $G$ we write
$G=\operatorname{Gp}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$ if $G\cong
FG(A)/N$ where $N$ is a normal subgroup of $FG(A)$ generated (as a normal
subgroup) by the words $w_{i}$, $i\in I$ (in fact, to be precise, by the words
$\operatorname{red}(w_{i})$ as some of the $w_{i}$ might not be reduced). By a
finitely presented monoid, inverse monoid, or group, we mean one that admits a
presentation with finitely many generators and finitely many defining
relations. It is easy to prove that a group is finitely presented as a group
if and only if it is finitely presented as a monoid if and only if it is
finitely presented as an inverse monoid. Interestingly, the same is not true
for monoids and inverse monoids since even free inverse monoids are not
finitely presented as monoids; see [32].

In general, for the element represented by a word $w$ (over the suitable
alphabet) in the structure $S$ given by the presentation
$\langle{A}\,|\,{\mathfrak{R}}\rangle$ (be it a monoid, an inverse monoid, or
a group) we write $[w]_{S}$.

For further background in combinatorial group theory (such as free products
and HNN extensions) we refer to [19].

######  Definition 2.1.

Let $G$ be a finitely presented group. We say that $M$ is a _prefix monoid in
$G$_ if there exists a finite presentation of $G$,

$G=\operatorname{Gp}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle,$

such that $M$ is isomorphic to the submonoid of $G$ generated by all elements
$[p]_{G}$ such that the word $p$ is a prefix of $w_{i}$ for some $i\in I$. We
simply say that $M$ is a _prefix monoid_ if it is a prefix monoid in some
finitely presented group. Notice that a group might have a number of prefix
monoids, as this definition depends on the presentation, not just the group it
defines; it might happen (see Example 2.3) that by changing a presentation of
a given group we arrive at a different prefix monoid. For a fixed group
presentation we talk about _the_ prefix monoid of the group with respect to
that presentation.

######  Remark 2.2.

It is important to note that, since we are often concerned with considering
group presentations and inverse monoid presentations given by the same
generators and relators, here we do not assume that the relator words
appearing in group presentations are cyclically reduced or even reduced. Also,
when considering inverse monoid presentations that turn out to define groups
we do not necessarily assume that the relations $aa^{-1}=a^{-1}a=1$ for $a\in
A$ are in the presentation; the fact that an element represented by a letter
is invertible might be shown in an entirely different way e.g. by deducing
relations of the form $au=va=1$ for some words $u,v\in\overline{A}^{*}$.

######  Example 2.3.

The following example, taken from [15, page 90], shows that the prefix monoid
can depend on the choice of presentation for the group. The prefix monoid of
the group presentation

$G=\operatorname{Gp}\langle{a,b}\,|\,{aba=1}\rangle$

is generated by $\\{a,ab\\}=\\{a,a^{-1}\\}$ which, since $b=a^{-2}$ in this
group, is the whole group $G$. On the other hand, the prefix monoid of the
presentation

$G=\operatorname{Gp}\langle{a,b}\,|\,{aab=1}\rangle$

is generated by $\\{a,a^{2}\\}$ and hence is equal to the submonoid of $G$
generated by $\\{a\\}$. Since $b=a^{-2}$ this generator is redundant and
eliminating it we see that $G$ is isomorphic to the infinite cyclic group
generated by $\\{a\\}$. So in the latter case the prefix monoid is isomorphic
to the infinite monogenic monoid $\\{a^{i}:i\geq 0\\}$. Hence these two
different presentations for $G$ yield two different prefix monoids.

It is immediately clear that all prefix monoids are finitely generated and
group-embeddable. So, the following general question arises naturally.

######  Question 2.4.

Which finitely generated group-embeddable monoids arise as prefix monoids?

######  Definition 2.5.

Let $M$ be a finitely presented special inverse monoid,

$M=\operatorname{Inv}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle.$

We call the submonoid $R=\\{m\in M:mm^{-1}=1\\}$ of right units of $M$ the
_RU-monoid_ of $M$. A monoid $T$ is an _RU-monoid_ if it is isomorphic to the
RU-monoid of some finitely presented special inverse monoid.

It follows from the argument in the proof of [15, Proposition 4.2] that the
RU-monoid of $M=\operatorname{Inv}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$
is generated by the set of all elements $[p]_{M}$ represented by prefixes $p$
of the set of defining relators $w_{i}$, $i\in I$. Of course the RU-monoid of
a special inverse monoid $M$ does not depend on the choice of presentation for
$M$, but different choices of special presentation can give different finite
generating sets for the monoid given by the prefixes of the defining relators.
Since an RU-monoid is by definition an RU-monoid of a finitely presented
special inverse monoid, it follows that the set of prefixes of defining
relators is finite, hence all RU-monoids are finitely generated, and it is
very easy to see that they are necessarily right cancellative. Indeed, if
$a,b,c$ are right units of any monoid then, choosing $x$ to be an element
satisfying $cx=1$ we see that if $ac=bc$ then $a=acx=bcx=b$. So, we instantly
have an analogous question to the one before.

######  Question 2.6.

Which finitely generated right cancellative monoids arise as RU-monoids?

###  2.2. Green’s relations and Schützenberger groups

The most basic tool in studying the structure of semigroups are the five
equivalence relations called _Green’s relations_. The first three of them,
$\mathscr{R},\mathscr{L},\mathscr{J}$, classify the elements of a semigroup
according to the right/left/two-sided principal ideals they generate. Since we
only work with monoids in this paper we give the definitions here just for
monoids. So, in a monoid $S$ we have the following definitions:

$a\,\mathscr{R}\,b\Leftrightarrow aS=bS,\quad a\,\mathscr{L}\,b\Leftrightarrow
Sa=Sb,\quad a\,\mathscr{J}\,b\Leftrightarrow SaS=SbS.$

Further, $\mathscr{H}=\mathscr{R}\cap\mathscr{L}$ and
$\mathscr{D}=\mathscr{R}\vee\mathscr{L}$, which is just
$\mathscr{R}\circ\mathscr{L}$ as it may be shown that $\mathscr{R}$ and
$\mathscr{L}$ commute. We say that $a\in S$ is _regular_ if $a=axa$ for some
$x\in S$. The $\mathscr{D}$-classes are exclusive with respect to regularity:
either all elements of a $\mathscr{D}$-class are regular, or none of them. In
the former case, each $\mathscr{R}$-class and each $\mathscr{L}$-class
contains at least one idempotent. The $\mathscr{H}$-classes containing
idempotents are maximal subgroups of a monoid and, in turn, every maximal
subgroup arises in this way. Group $\mathscr{H}$-classes within a given
$\mathscr{D}$-class are all isomorphic; hence, there is a natural way to
associate a group with each regular $\mathscr{D}$-class. Also, note that by
the definition of $\mathscr{R}$ it is immediate that in any monoid $M$, an
element $m$ belongs to the $\mathscr{R}$-class of $1$ in $M$ if and only if
$m$ is right invertible. In particular the RU-monoid of a special inverse
monoid is equal to the $\mathscr{R}$-class of $1$ in that monoid.

Even though non-regular $\mathscr{D}$-classes do not contain idempotents and
hence do not contain any subgroups, they carry a “hidden” group structure
encapsulated by the concept of a _Schützenberger group_. Namely, let $H$ be an
$\mathscr{H}$-class within a $\mathscr{D}$-class $D$, say of a monoid $S$.
Define first the _right stabiliser_ of $H$,

$\operatorname{Stab}(H)=\\{s\in S:\ Hs\subseteq H\\}.$

Then, if $s\in\operatorname{Stab}(H)$, it turns out that the right translation
corresponding to the element $s$, $\rho_{s}:a\mapsto as$ ($a\in S$), restricts
to a permutation of the set $H$. It is not difficult to see that
$\operatorname{Stab}(H)$ is a submonoid of $S$ and upon defining an
equivalence relation $\sigma$ on $\operatorname{Stab}(H)$ by $(s,t)\in\sigma$
if and only if $\rho_{s}|_{H}=\rho_{t}|_{H}$ then $\sigma$ is a congruence and
the quotient $\operatorname{Stab}(H)/\sigma$ is a group. This is the _right
Schützenberger group_ $\Gamma(H)$ of $H$. Analogously we can define the the
_left_ Schützenberger group of an $\mathscr{H}$-class, but it may be shown
that it is always isomorphic to the right one. This group has $|H|$ elements,
and Schützenberger groups of $\mathscr{H}$-classes from the same
$\mathscr{D}$-class are isomorphic to each other. As is expected, the
Schützenberger group of an $\mathscr{H}$-class $H$ from a regular
$\mathscr{D}$-class is just isomorphic to the maximal subgroup contained in
that class; in particular, if an $\mathscr{H}$-class $H$ is a group then
$\Gamma(H)\cong H$.

For further background in semigroup theory we refer to [6, 14], and,
specifically for inverse semigroups, to [18, 30].

###  2.3. Recursive enumerability and the Higman Embedding Theorem

A set of natural numbers $A\subseteq\mathbb{N}$ is _recursively enumerable_
(_r.e._ for short) if it is an image of a unary (primitive) recursive
function, that is, $A=\\{\varphi(n):\ n\in\mathbb{N}\\}$ for some primitive
recursive $\varphi:\mathbb{N}\to\mathbb{N}$. The notion of recursive
enumerability can be extended to languages as well (and then also to sets of
tuples of words) via some of the standard enumerations of all words over a
finite alphabet. It is one of the principal results of Turing [33, 24] that
r.e. languages are precisely the languages of Turing machines:
$L\subseteq\Sigma^{*}$ is r.e. if and only there exists a Turing machine
$\mathcal{M}$ such that $L(\mathcal{M})=L$, which means that $\mathcal{M}$
halts and accepts on any input word $w\in L$, while if $w\not\in L$ then
$\mathcal{M}$ either halts and rejects the word or works forever. Actually,
this is the criterion of a language being r.e. that we use throughout as is
the case in modern theoretical computer science [13].

Now we say that a finitely generated group $G$ is _recursively presented_ if

$G=\operatorname{Gp}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$

where $A$ is a finite set and $\\{w_{i}:\ i\in I\\}$ is a r.e. language over
$\overline{A}=A\cup A^{-1}$. Similarly, a monoid $M$ is _recursively
presented_ if

$M=\operatorname{Mon}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in I)}\rangle$

for a finite set $A$ and a r.e. subset $\\{(u_{i},v_{i}):\ i\in I\\}$ of
$A^{*}\times A^{*}$.

######  Theorem 2.7 (The Higman Embedding Theorem [12]).

A finitely generated group embeds into a finitely presented group if and only
if it is recursively presented.

In fact, there is a counterpart of the previous theorem for semigroups/monoids
and inverse semigroups/monoids, obtained, respectively, by Murskiĭ [28] and
Belyaev [3], so that a finitely generated (inverse) monoid embeds into a
finitely presented one if and only if it is recursively presented.

Let $G=\operatorname{Gp}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$ is a
finitely presented group. and that $L\subseteq\overline{A}^{*}$ is a r.e.
language such that $H=\\{[w]_{G}:\ w\in L\\}$ is a subgroup of $G$. Then we
say that $H$ is a _recursively enumerable subgroup_ of $G$. It is not
difficult to see that any finitely generated subgroup of $G$ is recursively
enumerable: if the generating elements of such a subgroup are represented by
words $u_{1},\dots,u_{k}\in\overline{A}^{*}$ then the (rational) language
$L=\\{u_{1},\dots,u_{k}\\}^{*}$ suffices to see this. Therefore, by Higman’s
Theorem any finitely generated recursively presented group arises as a
recursively enumerable subgroup of some finitely presented group. In fact,
although we will not need it here, more generally it follows from the argument
in [12, Corollary to Theorem 1] that any not necessarily finitely generated
recursively presented group is isomorphic to a recursively enumerable subgroup
of a finitely presented group.

##  3\. A characterisation of prefix monoids

By their very definition, prefix monoids are finitely generated submonoids of
finitely presented groups. Therefore, our first aim is to take a closer look
at such monoids. It turns out that the following holds.

######  Proposition 3.1.

A finitely generated monoid embeds into a finitely presented group if and only
if it is group-embeddable and recursively presented.

To prove this, we use an auxiliary result that is often labelled as folklore
(such as in [5, 26, 29]). A proof of the result may be found in [4,
Proposition 0.9.1], which in turn makes use of [6, Construction 12.3].

######  Lemma 3.2.

If the monoid $M=\operatorname{Mon}\langle{A}\,|\,{\mathfrak{R}}\rangle$ is
group-embeddable, then it embeds into the group with the same presentation,
$G=\operatorname{Gp}\langle{A}\,|\,{\mathfrak{R}}\rangle$.

###### Proof of Proposition 3.1.

($\Rightarrow$) Assume $M$ embeds into a finitely presented group $G$. Then
$G$ is also finitely presented as a monoid. Now the conclusion follows by
Murskiĭ’s semigroup/monoid version of the Higman Embedding Theorem [28].

($\Leftarrow$) Suppose $M=\operatorname{Mon}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in
I)}\rangle$ is group-embeddable and $\\{(u_{i},v_{i}):i\in I\\}$ is a r.e.
subset of $A^{*}\times A^{*}$. By the previous lemma, $M$ embeds into the
group $G$ with the same presentation, which is the same as
$\operatorname{Gp}\langle{A}\,|\,{u_{i}v_{i}^{-1}=1\;(i\in I)}\rangle$ where
$\\{u_{i}v_{i}^{-1}:\ i\in I\\}$ is now a r.e. language over $\overline{A}$.
Then, by the Higman Embedding Theorem, $G$ in turn embeds into a finitely
presented group, and hence so does $M$. ∎

######  Corollary 3.3.

Any prefix monoid is a group-embeddable recursively presented monoid.

The previous corollary immediately raises the question: Which group-embeddable
recursively presented monoids arise as prefix monoids? Possibly all of them?
We refute this by quickly looking at the special case when the prefix monoid
(of a finitely presented group) is itself a group.

######  Lemma 3.4.

If a group arises as a prefix monoid then it is finitely presented.

###### Proof.

Assume that $G=\operatorname{Gp}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$ is
a finitely presented group whose prefix monoid $P$ is also a group. Let
$a\in\overline{A}$ be any letter occurring in some $w_{i}$, so that
$w_{i}=w^{\prime}aw^{\prime\prime}$. Then both $[w^{\prime}]_{G}$ and
$[w^{\prime}a]_{G}$ are values of prefixes of $w_{i}$ in $G$, so they belong
to the generating set of $P$. However, the assumption that $P$ is a group
implies that $[w^{\prime}]_{G}^{-1}\in P$, and so

$[a]_{G}=[w^{\prime}]_{G}^{-1}[w^{\prime}a]_{G}\in P,$

as well as $[a]_{G}^{-1}\in P$. We conclude that $P$ coincides with the
subgroup of $G$ generated by the subset $B\subseteq A$ of all letters from $A$
appearing in the relators $w_{i}$, $i\in I$. But since
$G=\operatorname{Gp}\langle{B}\,|\,{w_{i}=1\;(i\in I)}\rangle\ast
FG(A\setminus B)$ it is then straightforward to see that
$P=\operatorname{Gp}\langle{B}\,|\,{w_{i}=1\;(i\in I)}\rangle$, so $P$ is
finitely presented. ∎

In fact, the converse is true as well, but we show this as part of the
following more general result for group-embeddable monoids.

######  Proposition 3.5.

Every group-embeddable finitely presented monoid arises as a prefix monoid.

###### Proof.

Let $M=\operatorname{Mon}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in I)}\rangle$ be a
group-embeddable finitely presented monoid. By Lemma 3.2, $M$ embeds into the
group $G=\operatorname{Gp}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in I)}\rangle$ via
the homomorphism induced by the identity map on $A$. However, the following is
then also a presentation for $G$:

$\operatorname{Gp}\langle{A}\,|\,{u_{i}v_{i}^{-1}=1\;(i\in I),\
aa^{-1}=1\;(a\in A)}\rangle.$

Now, computing the generating set for the prefix monoid $P$ with respect to
this presentation of $G$ would lead us to the prefixes of the words $u_{i}$,
words of the form $u_{i}p$, where $p$ is a prefix of $v_{i}^{-1}$, and the
individual letters $a\in A$. In the first of these cases, however, note that
if $v_{i}^{-1}=pq$ then $v_{i}=q^{-1}p^{-1}$ and $[u_{i}p]_{G}=[q^{-1}]_{G}$,
so indeed $P$ is generated by the elements of $G$ represented by the prefixes
of $u_{i},v_{i}$ ($i\in I$) and the letters $a\in A$. Since both $u_{i}$ and
$v_{i}$ are positive words (containing no inverses of letters), we conclude
that $P$ is the submonoid of $G$ generated by $\\{[a]_{G}$: $a\in A\\}$, which
is isomorphic to $M$. ∎

Proposition 3.5 shows that all group-embeddable finitely presented monoids
occur as prefix monoids. In contrast, Lemma 3.4 shows not all group-embeddable
recursively presented monoids occur as prefix monoids (for example, the non-
finitely recursively presented groups). However, we will now see that by
taking a free product of such a monoid with a free monoid of sufficient finite
rank will give a prefix monoid. This leads to a complete characterisation of
prefix monoids in the following result.

Let $\Sigma_{k}^{*}$ denote the free monoid of rank $k$.

######  Theorem 3.6.

For every group-embeddable recursively presented monoid $M$ there is a natural
number $\mu_{M}$ such that $M\ast\Sigma_{k}^{*}$ is a prefix monoid if and
only if $k\geq\mu_{M}$. Moreover, up to isomorphism, the class of all prefix
monoids is equal to

$\ \\{M\ast\Sigma_{k}^{*}:M\ \text{is a group-em\\-bed\\-d\\-a\\-ble
recursively presented monoid and}\ k\geq\mu_{M}\\}.$

###### Proof.

Let us start by noting that if $G$ is a finitely presented group that embeds
the finitely generated monoid $M$, then there exists a finite presentation

$\operatorname{Gp}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$

of $G$ such that $M$ is isomorphic to its submonoid generated by some subset
$B\subseteq A$. So, actually, we may identify
$M=\operatorname{Mon}\langle{[b]_{G}:\ b\in B}\rangle$. We begin by first
showing that there exists some finite set $C$ and a presentation for
$G*FG_{2}$, the free product of $G$ and a free group of rank 2, such that
$M*C^{*}$ is isomorphic to the prefix monoid for the presentation of
$G*FG_{2}$ in question.

The presentation of $K=G*FG_{2}$ for which we aim to describe the prefix
monoid is the following one:

$\operatorname{Gp}\langle{A,s,t}\,|\,{sw_{i}s^{-1}=1\;(i\in I),\
tbt^{-1}tb^{-1}t^{-1}=1\;(b\in B)}\rangle.$

The required prefix monoid $P$ is generated by the elements represented in $G$
by the words $sp$, where $p$ is a (possibly empty) prefix of $w_{i}$ for some
$i\in I$, and by $t,tb,tbt^{-1}$ ($b\in B$). Let $P_{1}$ denote the submonoid
of $P$ generated by $\\{[t]_{K},[tb]_{K},[tbt^{-1}]_{K}:\ b\in B\\}$, and
$P_{2}$ be the submonoid generated by $\\{[sp]_{K}:\
p\in\operatorname{pref}(w_{i}),\;i\in I\\}$. We claim that:

  * (1)

$P_{1}\cong M*\\{[t]_{K}\\}^{*}$;

  * (2)

$P_{2}$ is a free monoid of finite rank;

  * (3)

$P\cong P_{1}*P_{2}$.

For (1), start by noting that the generators of $P_{1}$ of the second type are
redundant, as $[tb]_{K}=[tbt^{-1}]_{K}[t]_{K}$ for all $b\in B$. So $P_{1}$ is
the submonoid of $K$ generated by $[t]_{K}$ and $\\{[tbt^{-1}]_{K}:\ b\in
B\\}$. Now $P_{1}$ is isomorphic to $[t]_{K}^{-1}P_{1}[t]_{K}$ which is the
submonoid of $K$ generated by $\\{[b]_{G}:\ b\in B\\}$ and $[t]_{K}$, and this
monoid is isomorphic to $M*\\{[t]_{K}\\}^{*}$ by the Normal Form Theorem for
free products [19, Theorem IV.1.2] applied to the group $K$. Let us note at
this point that all elements of $P_{1}$ are of the form $[tm_{1}\dots
tm_{k}t^{-1}]_{K}$ for some $k\geq 1$ and $m_{1},\dots,m_{k}\in B^{*}$.

To prove (2), we claim that $P_{2}$ is a free monoid on $\\{[sp]_{K}:\
p\in\operatorname{pref}(w_{i}),\;i\in I\\}$. Indeed, if

$[sp_{1}]_{K}\dots[sp_{m}]_{K}=[sp_{1}\dots sp_{m}]_{K}=[sq_{1}\dots
sq_{r}]_{K}=[sq_{1}]_{K}\dots[sq_{r}]_{K}$

holds in $P_{2}$ (and so in $K$) then again by the Normal Form Theorem in free
products we must have $m=r$ and $[p_{k}]_{G}=[q_{k}]_{G}$ for all $1\leq k\leq
m$, so $[sp_{k}]_{K}=[sq_{k}]_{K}$ for $1\leq k\leq m$, hence $P_{2}$
satisfies no nontrivial equality among its generators.

Finally, for (3), notice first that $P_{1}\cup P_{2}$ generates $P$. Also, by
the observations already made in the previous two paragraphs, we have that the
reduced forms (with respect to $K$) of all elements of $P_{1}$ are either of
the type $[t^{u_{1}}m_{1}\dots t^{u_{k}}m_{k}]_{K}$ or of the type
$[t^{u_{1}}m_{1}\dots t^{u_{k}}m_{k}t^{-1}]_{K}$ for some $u_{j}\geq 1$ and
words $m_{1},\dots,m_{k}\in B^{*}$ such that $[m_{j}]_{G}\neq 1$ for all
$1\leq j\leq k$. Similarly, the reduced forms of all elements of $P_{2}$ are
of the type $[s^{v_{1}}p_{1}\dots s^{v_{l}}p_{l}]_{K}$ for some $v_{j}\geq 1$
and words $p_{1},\dots,p_{l}\in\overline{A}^{*}$ (specifically, all these
words are non-empty prefixes of relator words $w_{i}$, $i\in I$) such that
$[p_{j}]_{G}\neq 1$ for all $1\leq j\leq l$. Therefore, if we have an equality

$[\alpha_{1}\beta_{1}\ldots\alpha_{m}\beta_{m}]_{K}=[\gamma_{1}\delta_{1}\ldots\gamma_{n}\delta_{n}]_{K}$

where $[\alpha_{q}]_{K},[\gamma_{r}]_{K}\in P_{1}$,
$[\beta_{q}]_{K},[\delta_{r}]_{K}\in P_{2}$ ($1\leq q\leq m$, $1\leq r\leq n$)
are all non-trivial, except possibly some of
$[\alpha_{1}]_{K},[\beta_{m}]_{K},[\gamma_{1}]_{K},[\delta_{n}]_{K}$, and the
words $\alpha_{q},\beta_{q},\gamma_{q}$ and $\delta_{q}$ are all words in the
reduced forms described above for $P_{1}$ and $P_{2}$.

Since every word $\alpha_{q},\gamma_{r}$ begins with $t$ and ends with either
a letter from $B$ or $t^{-1}$, and every word $\beta_{q},\delta_{r}$ begins
with $s$ and ends with a letter from $A$, it follows that both the words
$\alpha_{1}\beta_{1}\ldots\alpha_{m}\beta_{m}$ and
$\gamma_{1}\delta_{1}\ldots\gamma_{n}\delta_{n}$ are already in reduced form
with respect to the free product $K$. This yields an equality of reduced forms
in $K$ of the following type:

$[x_{1}y_{1}\dots x_{\sigma}y_{\sigma}]_{K}=[x^{\prime}_{1}y^{\prime}_{1}\dots
x^{\prime}_{\tau}y^{\prime}_{\tau}]_{K},$

where $\alpha_{1}\beta_{1}\ldots\alpha_{m}\beta_{m}=x_{1}y_{1}\dots
x_{\sigma}y_{\sigma}$ and
$\gamma_{1}\delta_{1}\ldots\gamma_{n}\delta_{n}=x^{\prime}_{1}y^{\prime}_{1}\dots
x^{\prime}_{\tau}y^{\prime}_{\tau}$ and each $x_{j},x_{j}^{\prime}$ is either
a power of $t$, or a power of $s$, or of the form $t^{-1}s^{v}$ for some
$v\geq 1$ and each $y_{j},y_{j}^{\prime}$ is a word over $\overline{A}$
representing a non-trivial element of the group $G$ (in case of words
occurring immediately after powers of $t$, there are in fact words from
$B^{*}$). By employing the Normal Form Theorem in free products once again, we
conclude that $\sigma=\tau$ and that $x_{j}=x^{\prime}_{j}$ and
$[y_{j}]_{G}=[y^{\prime}_{j}]_{G}$ for all $1\leq j\leq\sigma$. But then
combining this with the equalities of words
$\alpha_{1}\beta_{1}\ldots\alpha_{m}\beta_{m}=x_{1}y_{1}\dots
x_{\sigma}y_{\sigma}$ and
$\gamma_{1}\delta_{1}\ldots\gamma_{n}\delta_{n}=x^{\prime}_{1}y^{\prime}_{1}\dots
x^{\prime}_{\tau}y^{\prime}_{\tau}$ it follows that $m=n$,
$[\alpha_{q}]_{K}=[\gamma_{q}]_{K}$ and $[\beta_{q}]_{K}=[\delta_{q}]_{K}$ for
all $1\leq q\leq m$. This suffices to establish that $P$ is a free product of
$P_{1}$ and $P_{2}$.

For the remainder of the proof, assume that, for some $k$, $M*\Sigma_{k}^{*}$
is a prefix monoid in the finitely presented group
$L=\operatorname{Gp}\langle{X}\,|\,{\mathfrak{R}}\rangle$. Let $y$ be a symbol
not in $X$, and consider the group

$L^{\prime}=\operatorname{Gp}\langle{X,y}\,|\,{\mathfrak{R},\;yy^{-1}=1}\rangle.$

We have that $L^{\prime}\cong L*FG(y)$. Then the prefix monoid for the given
presentation of $L^{\prime}$ is generated by the prefix monoid of the
considered presentation of $L$ and the element represented by the letter $y$.
Therefore, the prefix monoid of $L^{\prime}$ is isomorphic to
$M*\Sigma_{k}^{*}*\\{y\\}^{*}\cong M*\Sigma_{k+1}^{*}$. Hence, if $\mu_{M}$ is
the minimal value of $k$ such that $M*\Sigma_{k}^{*}$ arises as a prefix
monoid (of a finitely presented group), it follows that $M*\Sigma_{k}^{*}$ is
a prefix monoid for all larger values of $k$. From this remark, the statement
of the first sentence in the theorem follows.

Conversely, given any group-embeddable recursively presented monoid $M$ that
arises as a prefix monoid we have $\mu_{M}=0$ and so $M\cong
M\ast\Sigma_{0}^{*}$ belongs to the class in the statement of theorem. ∎

######  Remark 3.7.

The size of the finite set $C$ appearing in the first part of the proof of the
previous result is bounded from above by one plus the sum of lengths of
relators needed to define the finitely presented group $G$ so that the
generating set of $M$ is included into the generating set of $G$. More
precisely, $|C|-1$ is actually the number of different elements of the group
$G$ represented by all prefixes of relators.

##  4\. Groups of units and Schützenberger groups of prefix monoids

Bearing in mind the goals of this section, the characterisation of the classes
of groups arising as groups of units and Schützenberger groups in prefix
monoids, respectively, we first record several basic facts about group-
embeddable monoids. Actually, the scope of some of these auxiliary results
extend to the wider classes of (right, left) cancellative monoids.

######  Proposition 4.1.

Let $M$ be a monoid with $x,y\in M$ and let $U$ be its group of units.

  * (1)

If $M$ is right cancellative then $x\,\mathscr{L}\,y$ if and only if $y=ux$
for some $u\in U$. Consequently, $L_{x}=Ux$.

  * (2)

If $M$ is left cancellative then $x\,\mathscr{R}\,y$ if and only if $y=xu$ for
some $u\in U$. Consequently, $R_{x}=xU$.

  * (3)

If $M$ is cancellative then $H_{x}=Ux\cap xU$ and $D_{x}=UxU$.

  * (4)

If $M$ is a submonoid of a group $G$ then the Schützenberger group of $H_{x}$
is isomorphic to $U\cap x^{-1}Ux$.

###### Proof.

(1) $x\,\mathscr{L}\,y$ holds if and only if $y=ux$ and $x=vy$ for some
$u,v\in M$. But then $x=vux$, and by right cancellativity of $M$ it follows
that $vu=1$. Similarly, $y=uvy$ implies $uv=1$, so both $u,v$ must be units of
$M$. (2) is dual to (1), and (3) follows from (1) and (2).

Assume now that $M$ is a submonoid of a group $G$; we compute the right
Schützenberger group of $H_{x}$. Indeed, $m\in M$ stabilises $H_{x}$ from the
right if and only if $H_{x}m\subseteq H_{x}$. In particular,
$xm\,\mathscr{R}\,x$, which by (2) implies $m\in U$. Furthermore, we must have
$xm\,\mathscr{L}\,x$, so $xm=ux$ for some $u\in U$. This, in $G$, yields
$m=x^{-1}ux\in x^{-1}Ux$. Conversely, the assumption $m\in U\cap x^{-1}Ux$
implies that $xm\in xU\cap xx^{-1}Ux=xU\cap Ux=H_{x}$. Since $xm\in H_{x}$ it
follows by Green’s Lemma [14] that $H_{x}m=H_{x}$. So,
$\operatorname{Stab}(H_{x})=U\cap x^{-1}Ux$. However, the (right)
Schützenberger group of $H_{x}$ must coincide now with its right stabiliser,
as left cancellativity of $M$ implies that its every element must induce a
different permutation of $H_{x}$. ∎

######  Proposition 4.2.

Let $M$ be a right (or left) cancellative monoid and let $U$ be its group of
units.

  * (1)

$M\setminus U$ is an ideal of $M$. Consequently, if $M$ is finitely generated
(resp. recursively presented), so is $U$.

  * (2)

Every Schützenberger group of $M$ embeds into $U$.

  * (3)

If $M$ is recursively presented then every Schützenberger group of $M$ is a
recursively enumerable subgroup of a finitely presented group.

###### Proof.

We consider only the case when $M$ is right cancellative, the left
cancellative case being dual.

(1) Assume that $x,y\in M$ are such that $xy\in U$. Then $xyz=zxy=1$ for some
$z\in M$. Hence, $yzxy=y$ which by right cancellativity implies $yzx=1$. So,
$zx$ is an inverse of $y$ and $yz$ is an inverse of $x$, thus $x,y\in U$.
Therefore, if any of $a,b\in M$ does not belong to $U$ it follows that $ab\in
M\setminus U$, showing that $M\setminus U$ is an ideal of $M$.

Now if $X\subseteq M$ is any generating set of $M$ it follows that $X\cap U$
must be a (monoid) generating set of $U$: indeed, the previous paragraph shows
that if for $u\in U$ we have $u=x_{1}\dots x_{n}$ for some
$x_{1},\dots,x_{n}\in X$ then in fact we must have $x_{1},\dots,x_{n}\in X\cap
U$. So, if $X$ is finite (witnessing that $M$ is finitely generated), so is
$X\cap U$, thus $U$ is a finitely generated group.

Finally, assume that $M$ is recursively presented. As just shown, this implies
that the group $U$ is finitely generated, and it embeds, together with the
whole $M$, into a finitely presented monoid [28]. So, as a monoid, $U$ is
recursively presented, say
$U=\operatorname{Mon}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in I)}\rangle$. Since $U$
is a group, the group presentation
$\operatorname{Gp}\langle{A}\,|\,{u_{i}v_{i}^{-1}=1\;(i\in I)}\rangle$ also
defines $U$. Here, $\\{u_{i}v_{i}^{-1}:\ i\in I\\}$ is a r.e. language,
showing $U$ to be a recursively presented group.

(2) Here we use the fact (already mentioned in the preliminary section) that
the (right) Schützenberger group of an $\mathscr{H}$-class is isomorphic to
the left Schützenberger group of that $\mathscr{H}$-class. Since $M$ is right
cancellative, if $H$ is an $\mathscr{H}$-class of $M$, the condition $uH=H$
for some $u\in M$, implies, by Proposition 4.1 (1), that $u$ is a unit of $M$.
Furthermore, if $u^{\prime}\neq u$ is also a unit of $M$ then for any $h\in H$
we have $uh\neq u^{\prime}h$ because of the right cancellative property.
Hence, every element $u$ of the left stabiliser of $H$ induces (via the left
translation $\lambda_{u}:h\mapsto uh$, $h\in H$) a different permutation of
$H$, implying that it coincides with the left Schützenberger group of $H$ and
embeds into $U$.

(3) Let $H$ be an $\mathscr{H}$-class of
$M=\operatorname{Mon}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in I)}\rangle$. By (2),
the Schützenberger group $K$ of $H$ embeds into $U$. By (1), the group of
units $U$ is recursively presented, say $U=\operatorname{Gp}\langle{A\cap
U}\,|\,{\mathfrak{R}}\rangle$, and so it embeds into a finitely presented
group. By combining these two facts, we obtain that $K$ is a subgroup of a
finitely presented group
$G=\operatorname{Gp}\langle{B}\,|\,{\mathfrak{R}^{\prime}}\rangle$; in this
sense we aim to show that $K$ is a recursively enumerable subgroup of a
finitely presented group.

Assume that $H=H_{x}$ for some $x\in M$, and let $w\in A^{*}$ be any word such
that $[w]_{M}=x$. Also, since $U$ embeds into $G$, there is a mapping which
assigns to each letter $a\in A\cap U$ a word $w_{a}\in\overline{B}^{*}$
inducing the embedding $U\to G$ from the previous paragraph, so that
$[a_{1}\dots a_{m}]_{U}$ is mapped to $[w_{a_{1}}\dots w_{a_{m}}]_{G}$ for all
$a_{1},\dots,a_{m}\in A\cap U$. Now note that for $u\in A^{*}$, $[u]_{M}\in K$
if and only if $[u]_{M}$ is a unit of $M$ and there exist words $p,q\in A^{*}$
such that $[uw]_{M}=[wp]_{M}$ and $[wpq]_{M}=[w]_{M}$. The latter two
equalities ensure that $[u]_{M}x\,\mathscr{R}\,x$ and so
$[u]_{M}x\,\mathscr{H}\,x$ (as we have $[u]_{M}x\,\mathscr{L}\,x$ for granted,
by Proposition 4.1 (1)), and by Green’s Lemma (see e.g. [14, Lemma 2.2.1 and
its dual, Lemma 2.2.2]) the condition $[u]_{M}x\in H_{x}=H$ is equivalent to
$[u]_{M}H=H$.

Therefore, (3) will be proved as soon as we construct a Turing machine
$\mathcal{M}$ that halts on input $u\in A^{*}$ if and only if the word $u$ has
the properties described in the previous paragraph, for then the language

$\\{w_{a_{1}}\dots w_{a_{m}}:\ a_{1}\dots a_{m}\in
L(\mathcal{M})\\}\subseteq\overline{B}^{*},$

whose words represent the elements of the image of $K$ under the considered
embedding $U\to G$, is clearly r.e. In more detail, $\mathcal{M}$ should
“detect” the words $u\in A^{*}$ such that the equalities

$[uv]_{M}=[vu]_{M}=1,\quad[uw]_{M}=[wp]_{M},\quad[wpq]_{M}=[w]_{M}$

hold for some $v,p,q\in A^{*}$.

Since $M$ is a recursively presented monoid, its word problem, that is, the
set $\\{(u,v)\in A^{*}\times A^{*}:\ [u]_{M}=[v]_{M}\\}$, is well-known to be
r.e. (For groups this is already contained in the results of Higman [12], and
for monoids this is a consequence of the work of Murskiĭ [28].) Hence, there
exists a Turing machine $\mathcal{M}_{M}$ whose language is the word problem
of $M$. Use some of the standard enumerations of triples of all words over
$\overline{A}$ to obtain
$\overline{A}^{*}\times\overline{A}^{*}\times\overline{A}^{*}=\\{(v_{n},p_{n},q_{n}):\
n\in\mathbb{N}\\}$. Then, use countably infinitely many copies
$\mathcal{M}_{n}$, $n\in\mathbb{N}$, of the machine $\mathcal{M}_{M}$ and feed
the inputs $(uv_{i},1)$, $(v_{i}u,1)$, $(uw,wp_{i})$ and $(wp_{i}q_{i},w)$
into the machines $\mathcal{M}_{4i}$, $\mathcal{M}_{4i+1}$,
$\mathcal{M}_{4i+2}$, $\mathcal{M}_{4i+3}$, $i\in\mathbb{N}$, respectively, so
that the resulting machine first performs the first step of machine
$\mathcal{M}_{0}$, then the first step of machine $\mathcal{M}_{1}$ and the
second step of machine $\mathcal{M}_{0}$, and so on. Such a machine
$\mathcal{M}$ will halt and return a positive answer if and only if the word
$u$ represents (in $M$) an element of $K$, the required Schützenberger group
of $H$. ∎

######  Theorem 4.3.

A group arises as a group of units of a prefix monoid if and only if it is a
recursively presented group.

###### Proof.

By (1) of the previous proposition, it is immediate that the group of units of
any prefix monoid is recursively presented.

Conversely, let $G=\operatorname{Gp}\langle{A}\,|\,{\mathfrak{R}}\rangle$ be a
recursively presented group. Then $G=\operatorname{Mon}\langle{A\cup
A^{\prime}}\,|\,{\mathfrak{R}^{\prime},\;aa^{\prime}=a^{\prime}a=1\;(a\in
A)}\rangle$ is a monoid presentation for $G$, where $A^{\prime}$ is a
bijective copy of $A$ disjoint form $A$ and the relations from
$\mathfrak{R}^{\prime}$ are obtained from $\mathfrak{R}$ by replacing each
$a^{-1}$ by $a^{\prime}$, $a\in A$. This shows that $G$, as a monoid, is
recursively presented. By Theorem 3.6, there is an integer $k\geq 0$ such that
$G*\Sigma_{k}^{*}$ is a prefix monoid. It remains to note that $G$ is the
group of units of $G*\Sigma_{k}^{*}$. ∎

The main technical tool for studying Schützenberger groups in various classes
of group-embeddable finitely generated monoids is the following.

######  Theorem 4.4.

Let $\mathcal{K}$ be a class of group-embeddable recursively presented monoids
such that for any group-embeddable recursively presented monoid $M$ and any
embedding $\alpha:M\to\Gamma$ into a finitely presented group $\Gamma$ there
exist $N_{M}\in\mathcal{K}$, a finitely presented group $\Gamma_{1}$, monoid
embeddings $\beta:M\to N_{M}$ and $\alpha^{\prime}:N_{M}\to\Gamma_{1}$, and a
group embedding $\beta^{\prime}:\Gamma\to\Gamma_{1}$ such that the following
diagram commutes:

$\textstyle{M\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\beta}$$\scriptstyle{\alpha}$$\textstyle{N_{M}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha^{\prime}}$$\textstyle{\Gamma\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\beta^{\prime}}$$\textstyle{\Gamma_{1}}$

and that the restriction $\beta\restriction_{U_{M}}$ to the group of units of
$M$ is an isomorphism between $U_{M}$ and $U_{N_{M}}$, the group of units of
$N_{M}$.

Then for any group $K$ that is a recursively enumerable subgroup of a finitely
presented group there is a monoid $S\in\mathcal{K}$ such that $K$ is
isomorphic to the Schützenberger group of an $\mathscr{H}$-class of $S$.

###### Proof.

Let $H_{1}=\operatorname{Gp}\langle{A}\,|\,{\mathfrak{R}}\rangle$ be a
finitely presented group such that $K$ embeds into $H_{1}$ so that the image
of this embedding, $K_{1}=\\{[w]_{H_{1}}:\ w\in L\\}$ (for some r.e. language
$L$), is a recursively enumerable subgroup of $H_{1}$. By [9, Lemma 5.2] there
is a finitely presented group containing two conjugate subgroups, both
isomorphic to $H_{1}$, such that their intersection is isomorphic to
$K_{1}\cong K$. In more detail, let $G_{0}$ be the HNN extension of $H_{1}$
with a stable letter $t$, conjugating each element of $K_{1}$ to itself. A
presentation for this group is
$\operatorname{Gp}\langle{A,t}\,|\,{\mathfrak{R}\cup\mathfrak{R}_{0}}\rangle$,
where $\mathfrak{R}_{0}=\\{t^{-1}wtw^{-1}:\ w\in L\\}$. Here
$\mathfrak{R}_{0}$ is clearly a r.e. language, so $G_{0}$ is finitely
generated and recursively presented. By the Higman Embedding Theorem, it
embeds into some finitely presented group $G$. Within $G$ we have
$H_{2}=[t]_{G}^{-1}H_{1}[t]_{G}\cong H_{1}$ and $H_{1}\cap H_{2}=K_{1}$.

Now let $M$ be the submonoid of $G$ generated by $H_{1}$ and $[t]_{G}$. This
is a finitely generated submonoid of $G$, a finitely presented group, so $M$
is a group-embeddable recursively presented monoid. A generating set of $M$ is
$\\{[a]_{G},[a]_{G}^{-1}:\ a\in A\\}\cup\\{[t]_{G}\\}$. Let us pause for a
moment to analyse the group of units of $M$. Indeed, for a word
$w\in(\overline{A}\cup\\{t\\})^{*}$ we have that $[w]_{G}$ is invertible in
$M$ if and only if $[w]_{G},[w]_{G}^{-1}\in M$. Let $w$ be one such word. Then
we can write

$[w]_{G}=[h_{0}th_{1}t\dots th_{\ell}]_{G}$

for some $\ell\geq 0$ and words $h_{i}\in\overline{A}^{*}$, $0\leq i\leq\ell$,
such that $[h_{i}]_{G}\in H_{1}$. Note that the word $h_{0}th_{1}t\dots
th_{\ell}$ is already in a reduced form with respect to the HNN-extension
structure of $G_{0}$ (see [19, p.181]). Hence,

$[w]_{G}^{-1}=[h_{\ell}^{-1}t^{-1}\dots
t^{-1}h_{1}^{-1}t^{-1}h_{0}^{-1}]_{G}.$

The word on the right hand side is also already in a reduced form. However,
the condition $[w]_{G}^{-1}\in M$ and the very definition of $M$ implies that
there must be words
$h_{0}^{\prime},h_{1}^{\prime},\dots,h_{p}^{\prime}\in\overline{A}^{*}$ with
$[h_{j}^{\prime}]_{G}\in H_{1}$ for all $0\leq j\leq p$ such that

$[h_{\ell}^{-1}t^{-1}\dots
t^{-1}h_{1}^{-1}t^{-1}h_{0}^{-1}]_{G}=[h_{0}^{\prime}th_{1}^{\prime}t\dots
th_{p}^{\prime}]_{G}.$

This is now an equality of two reduced forms in the HNN-extension $G_{0}$ and
by [7, Lemma 6.2] it is impossible unless $\ell=p=0$ and
$[h_{0}^{\prime}]_{G}=[h_{0}]_{G}^{-1}\in H_{1}$. On the other hand, it is
clear that any element of $H_{1}$ is a unit in $M$, so $U_{M}=H_{1}$.

Next, start with $M$ and its inclusion map into $G$. By the condition of the
theorem, there is a monoid $S=N_{M}\in\mathcal{K}$, a finitely presented group
$G_{1}$ and embeddings $\phi,\psi,\xi$ such that the diagram

$\textstyle{M\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\phi}$$\scriptstyle{\subseteq}$$\textstyle{S\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi}$$\textstyle{G\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\xi}$$\textstyle{G_{1}}$

commutes, and the corresponding restriction of $\phi$ induces an isomorphism
between the group of units $U_{M}$ and $U_{S}$. By Proposition 4.1 (4), the
Schützenberger group of $H_{[t]_{G}}$ is isomorphic to
$U_{M}\cap[t]_{G}^{-1}U_{M}[t]_{G}=H_{1}\cap H_{2}\cong K$. Applying
Proposition 4.1 (4) to $H_{\mathbf{t}}$ in $S$, where
$\mathbf{t}=[t]_{G}\phi$, the Schützenberger group of $H_{\mathbf{t}}$ is
isomorphic to

$U_{S}\psi\cap(\mathbf{t}^{-1}U_{S}\mathbf{t})\psi.$

However, since $U_{S}=U_{M}\phi$ and $\phi\psi=\xi\restriction_{M}$, the
latter group is just $K_{1}\xi$, an isomorphic copy of $K$. ∎

######  Theorem 4.5.

The Schützenberger groups of prefix monoids are exactly the recursively
enumerable subgroups of finitely presented groups.

###### Proof.

($\Rightarrow$) By Corollary 3.3, if $M$ is a prefix monoid then it is group-
embeddable (and so right cancellative) and recursively presented. Hence by
Proposition 4.2 (3) every Schützenberger group of $M$ is a recursively
enumerable subgroup of a finitely presented group.

($\Leftarrow$) In Theorem 4.4, set $\mathcal{K}$ to be the class of prefix
monoids. The first part of the proof of Theorem 3.6 shows that for any group-
embeddable recursively presented monoid $M$ and any embedding $M\to G$ into a
finitely presented group $G$, there exists a finite set $C$ such that
$M*C^{*}$ is isomorphic to a prefix monoid in $G*FG_{2}$. Since the group of
units of $M*C^{*}$ is the same as that of $M$, the natural embedding $M\to
M*C^{*}$, the isomorphism between $M*C^{*}$ and a prefix monoid of
$G_{1}=G*FG_{2}$ as in the proof of Theorem 3.6, and the group embedding $G\to
G_{1}$ defined by

$g\mapsto[t]_{G_{1}}g[t]_{G_{1}}^{-1}$

for all $g\in G$, provide us with all the required parameters for the
application of Theorem 4.4. It now yields that any recursively enumerable
subgroup of a finitely presented group occurs as a Schützenberger group of a
prefix monoid. ∎

##  5\. On RU-monoids

In the previous two sections we studied prefix monoids, giving a
characterisation of those monoids that arise as prefix monoids, and of their
groups of units and Schützenberger groups. In this section we start by
collecting a few basic facts about the submonoids of right units of finitely
presented special inverse monoids which, as mentioned above, we call the RU-
monoids; subsequently, we provide a characterisation of groups arising as
Schützenberger groups of RU-monoids. While prefix monoids are all group-
embeddable, for RU-monoids we need to work with the wider class of right
cancellative monoids.

######  Lemma 5.1.

Every RU-monoid is a right cancellative recursively presented monoid.

###### Proof.

First of all, every RU-monoid $R$ is finitely generated, namely by the
elements represented by all prefixes of the relator words appearing in the
presentation of the finitely presented special inverse monoid
$I=\operatorname{Inv}\langle{A}\,|\,{\mathfrak{R}}\rangle$, the monoid of
right units of which is isomorphic to $R$. However, as a monoid,
$I\cong\overline{A}^{*}/\theta_{\mathfrak{R}}$, where $\theta_{\mathfrak{R}}$
is the smallest congruence of the free monoid $\overline{A}^{*}$ containing
$\mathfrak{R}$ and the Wagner congruence. We conclude that $I$ is recursively
presented as a monoid, and thus it embeds (together with $R$) into a finitely
presented monoid $M$. Therefore, $R$ is a recursively presented monoid. ∎

Analogously to the case of prefix monoids, the first question that arises
following the previous lemma is if all right cancellative recursively
presented monoids arise as RU-monoids. (Shortly we shall see that there are
two approaches to defining right cancellative monoids by means of
presentations.) The answer is negative: namely, there is a parallel result to
that of Lemma 3.4.

######  Lemma 5.2.

If the monoid $R$ of right units of a finitely presented special inverse
monoid $M=\operatorname{Inv}\langle{A}\,|\,{w_{i}=1\;(i\in I)}\rangle$ is a
group, then it is finitely presented.

###### Proof.

First of all, recall that $R$ is the submonoid of $M$ generated by all of its
elements of the form $[p]_{M}$ where $p$ is a prefix of a word $w_{i}$, $i\in
I$. Let $a\in\overline{A}$ be any letter occurring in some $w_{i}$, so that
$w_{i}=w^{\prime}aw^{\prime\prime}$. Similarly as in the proof of Lemma 3.4,
we have that both $[w^{\prime}]_{M}$ and $[w^{\prime}a]_{M}$ are values of
prefixes of $w_{i}$ in $M$, so they belong to $R$. Since $R$ is a group,
$[w^{\prime}]_{M}^{-1}\in R$. Therefore, $[w^{\prime}]_{M}^{-1}$ is a right
unit of $M$, so $[w^{\prime}]_{M}^{-1}[w^{\prime}]_{M}=1$. This allows us to
conclude that

$[a]_{M}=[w^{\prime}]_{M}^{-1}[w^{\prime}a]_{M}\in R,$

and so $[a]_{M}$ is a unit of $M$ for any letter $a\in A$ that appears in some
$w_{i}$. If $A^{\prime}\subseteq A$ denotes the set of all such letters, we
obtain that the special inverse monoid
$\operatorname{Inv}\langle{A^{\prime}}\,|\,{w_{i}=1\;(i\in I)}\rangle$ is a
group and it coincides with the group with the same presentation,
$G=\operatorname{Gp}\langle{A^{\prime}}\,|\,{w_{i}=1\;(i\in I)}\rangle$. Now
$M\cong G*FIM(A\setminus A^{\prime})$, where this free product is taken in the
category of inverse monoids, from which it instantly follows that $R\cong G$,
so $R$ is a finitely presented group. ∎

The converse of this lemma is also true, as any finitely presented group is
finitely presented as a special inverse monoid (by adding in the relations
$aa^{-1}=1$ and $a^{-1}a=1$ for all generators $a$) and, viewed this way, is
the monoid of right units of itself.

Now, while dealing with right cancellative monoids, there is yet another type
of presentation that is worthwhile considering in this context. Namely, since
right cancellative monoids form a quasi-variety (defined by the implication
$xz=yz\Rightarrow x=y$), we have that for any monoid $M$ and any family
$\\{\rho_{i}:\ i\in I\\}$ of its congruences with the property that
$M/\rho_{i}$ is right cancellative, the intersection $\rho$ of this family is
again a congruence of $M$ such that $M/\rho$ is right cancellative. For this
reason, not unlike the greatest group image (of an inverse monoid, for
example), there exists the greatest right cancellative image of a monoid. In
particular, if $M=\operatorname{Mon}\langle{A}\,|\,{\mathfrak{R}}\rangle$,
this greatest right cancellative image is denoted by
$\operatorname{MonRC}\langle{A}\,|\,{\mathfrak{R}}\rangle$, and it is defined
as $A^{*}/\mathfrak{R}^{\mathrm{RC}}$, where $\mathfrak{R}^{\mathrm{RC}}$ is
the intersection of all congruences $\sigma$ of $A^{*}$ with the property that
$\sigma\supseteq\mathfrak{R}$ and $A^{*}/\sigma$ is right cancellative. So, a
monoid $M=\operatorname{Mon}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in I)}\rangle$ is
right cancellative (and there are conditions implying this, see e.g. [1]) if
and only if $\operatorname{Mon}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in
I)}\rangle=\operatorname{MonRC}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in I)}\rangle$.

When both $A,\mathfrak{R}$ are finite,
$M=\operatorname{MonRC}\langle{A}\,|\,{\mathfrak{R}}\rangle$ is said to be
_finitely RC-presented_. The previous remark implies that when the finitely
presented monoid $\operatorname{Mon}\langle{A}\,|\,{\mathfrak{R}}\rangle$
happens to be right cancellative, it is also finitely RC-presented; the
converse of this, however, is not true in general (cf. [5] and the references
mentioned there). So, finitely RC-presented (right cancellative) monoids form
a strictly wider class than that of finitely presented monoids which are right
cancellative. By the following result we include the former class into the
scope of our considerations.

######  Theorem 5.3.

Every finitely RC-presented monoid
$T=\operatorname{MonRC}\langle{A}\,|\,{u_{i}=v_{i}\;(i\in I)}\rangle$ is an
RU-monoid.

###### Proof.

Begin by defining a finitely presented special inverse monoid

$M_{T}=\operatorname{Inv}\langle{A}\,|\,{aa^{-1}=1\;(a\in A),\
u_{i}v_{i}^{-1}=1\;(i\in I)}\rangle.$

We claim that its monoid of right units is isomorphic to $T$. Notice that the
inverse monoid $M_{T}$ is also presented by
$\operatorname{Inv}\langle{A}\,|\,{aa^{-1}=1\;(a\in A),\ u_{i}=v_{i}\;(i\in
I)}\rangle$: under the assumption that all the letters $a\in A$ represent
right units, the equations $u_{i}v_{i}^{-1}=1$ and $u_{i}=v_{i}$ are
equivalent, by using that fact that if a word $w\in\overline{A}^{*}$ and an
inverse monoid $K$ is such that $[w]_{K}$ is a right unit of $K$ then
$[w]_{K}=[\operatorname{red}(w)]_{K}$, see e.g. [8, Corollary 3.2].

We proceed by mimicking the argument from [15, Theorem 2.2]. Namely, $T$ is a
right cancellative monoid, so [6, Theorem 1.22] applies: $T$ is isomorphic to
the monoid of right units of its _inverse hull_ $IH(T)$, the inverse monoid of
partial bijections on $T$ generated by the right translations $\rho_{t}$,
$t\in T$ (since $T$ is right cancellative, each $\rho_{t}$ must be an
injective transformation of $T$, with the left ideal $Tt$ as its image). Since
for all $i\in I$, both $[u_{i}]_{IH(T)}$ and $[v_{i}]_{IH(T)}$ are right units
of the inverse monoid $IH(T)$, we have $[u_{i}v_{i}^{-1}]_{IH(T)}=1$ in this
inverse monoid. Hence, there is a surjective inverse monoid homomorphism
$\mu:M_{T}\to IH(T)$ extending the map $[a]_{M_{T}}\mapsto\rho_{a}$, $a\in A$;
also, there is a natural surjective involutory monoid homomorphism
$\nu:\overline{A}^{*}\to M_{T}$. Write $T^{\prime}=A^{*}\nu$, which is a
submonoid of $M_{T}$ generated by $[a]_{M_{T}}$ for all $a\in A$. This is
precisely the generating set for the monoid of its right units of $M_{T}$, so
this monoid must be $T^{\prime}$. However, $T^{\prime}\mu$ is just the monoid
of right units of $IH(T)$ (the latter being isomorphic to $T$). But we have
$[u_{i}]_{M_{T}}=[v_{i}]_{M_{T}}$ for all $i\in I$, and since $u_{i},v_{i}\in
A^{*}$ this implies $[u_{i}]_{T^{\prime}}=[v_{i}]_{T^{\prime}}$. As
$T^{\prime}$ is right cancellative (being an RU-monoid), it is a homomorphic
image of $T$, forcing $\mu\restriction_{T^{\prime}}$ to be a monoid
isomorphism. Thus $T$ is an RU-monoid. ∎

######  Corollary 5.4.

All group-embeddable finitely presented monoids are RU-monoids.

However, as the previous theorem shows, RU-monoids are not confined to group-
embeddable monoids; for example, the right units of

$M=\operatorname{Inv}\langle{a,b,c}\,|\,{aa^{-1}=bb^{-1}=cc^{-1}=1,\
abc^{-1}a^{-1}=1}\rangle$

is a right cancellative monoid that is not group-embeddable. Indeed, the proof
above tells us that in fact
$M=\operatorname{Inv}\langle{a,b,c}\,|\,{aa^{-1}=bb^{-1}=cc^{-1}=1,\
ab=ac}\rangle$. Now, in the monoid $R$ of right units of $M$ we clearly must
have $[ab]_{M}=[ac]_{M}$, but certainly not $[b]_{M}=[c]_{M}$ (as, in fact,
$R=\operatorname{MonRC}\langle{a,b,c}\,|\,{ab=ac}\rangle$), which contradicts
group-embeddability of $R$.

Since every unit of an inverse monoid is automatically a right unit, it
follows that the group of units of the RU-monoid of an inverse monoid $M$
coincides with the group of units of of $M$; therefore, as mentioned in the
introduction, [9, Theorem 4.1] shows that the class of groups of units of all
RU-monoids is precisely the class of recursively presented groups.

In the final result of this paper we describe the Schützenberger groups of RU-
monoids. For this, we recall a construction from [10, Section 6] and a couple
of pertinent results from that paper that we are going to use in the
following. Let $A=\\{a_{1},\dots,a_{n}\\}$ be a finite alphabet, and let $Q$
and $W$ be two subsets of $\overline{A}^{*}$ with $W=\\{w_{1},\dots,w_{k}\\}$
finite and $Q=\\{r_{i}:\ i\in I\\}$ where $I$ contains a distinguished index
1. Furthermore, let $t$ be a letter not in $\overline{A}$. Let
$K_{Q}=\operatorname{Gp}\langle{A}\,|\,{r_{i}=1\;(i\in I)}\rangle$. For any
list of words $u_{1},\dots,u_{m}\in\overline{A}^{*}$ we define

$e(u_{1},u_{2},\dots,u_{m})=u_{1}u_{1}^{-1}u_{2}u_{2}^{-1}\dots
u_{m}u_{m}^{-1}.$

Now we define the special inverse monoid

$M_{Q,W}=\operatorname{Inv}\langle{A,t}\,|\,{fr_{1}=1,\;r_{i}=1\;(i\in
I\setminus\\{1\\})}\rangle$

where

$f=e(a_{1},\dots,a_{n},tw_{1}t^{-1},\dots,tw_{k}t^{-1},a_{1}^{-1},\dots,a_{n}^{-1}).$

As noted in [10], it was shown in [8, Lemma 3.3] that $M_{Q,W}$ is equal to
the monoid defined by the presentation with generating set $A\cup\\{t\\}$ and
defining relations

$\displaystyle r_{i}=1$ $\displaystyle(i\in I),$ $\displaystyle
aa^{-1}=a^{-1}a=1$ $\displaystyle(a\in A),$ $\displaystyle
tw_{j}t^{-1}tw_{j}^{-1}t^{-1}=1$ $\displaystyle(1\leq j\leq k).$

We are going to make use of the following results from [10].

######  Proposition 5.5 ([10, Theorem 6.3]).

With the above notation and definitions we have the following.

  * (1)

Let $T_{W}$ be the submonoid of the group $K_{Q}$ generated by
$\\{[w_{j}]_{K_{Q}}:\ 1\leq j\leq k\\}$. The submonoid of right units of
$M_{Q,W}$ is isomorphic to the submonoid of the group $G_{Q}=K_{Q}*FG(t)$
generated by

$\\{[t]_{G_{Q}}\\}\cup K_{Q}\cup[t]_{G_{Q}}T_{W}[t]_{G_{Q}}^{-1}.$

  * (2)

The group of units of $M_{Q,W}$ is isomorphic to the subgroup $U$ of $G_{Q}$
generated by

$K_{Q}\cup\\{[twt^{-1}]_{G_{Q}}:\ w\in W^{\prime}\\},$

where $W^{\prime}\subseteq W$ consists of all $w_{j}\in W$ such that the word
$tw_{j}t^{-1}$ represents a unit of $M_{Q,W}$. Furthermore, $U$ is generated
by its subgroups $K_{Q}$ and $[t]_{G_{Q}}H_{W^{\prime}}[t]_{G_{Q}}^{-1}$ where
$H_{W^{\prime}}$ is the subgroup of $K_{Q}$ generated by $\\{[w]_{K_{Q}}:\
w\in W^{\prime}\\}$, and is in fact isomorphic to the free product of these
subgroups.

Item (1) of the previous proposition is precisely Theorem 6.3 (iii) from [10],
while item (2) may be found within the proof of part (v) of the same theorem.

######  Theorem 5.6.

The Schützenberger groups of RU-monoids are exactly the recursively enumerable
subgroups of finitely presented groups.

###### Proof.

($\Rightarrow$) By Lemma 5.1, if $M$ is an RU-monoid then it is right
cancellative and recursively presented (as a monoid). Hence by Proposition 4.2
(3) every Schützenberger group of $M$ is a recursively enumerable subgroup of
a finitely presented group.

($\Leftarrow$) The initial setup for our argument is the same as in the
beginning of the proof of Theorem 4.4. Namely, let $K$ be an arbitrary group
that arises as a recursively enumerable subgroup of a finitely presented
group. Let $H_{1}=\operatorname{Gp}\langle{B}\,|\,{\mathfrak{R}_{1}}\rangle$
be a finitely presented group and $L$ a r.e. language such that
$K_{1}=\\{[w]_{H_{1}}:\ w\in L\\}$ is a subgroup of $H_{1}$ isomorphic to $K$.
We let $G_{0}$ to be the HNN extension of $H_{1}$, this time with $z$ as the
stable letter (the letter $t$ will be reserved for a different purpose in this
proof), conjugating each element of $K_{1}$ to itself. As seen in Theorem 4.4,
$G_{0}$ is a recursively presented group, so it embeds into a finitely
presented group $G=\operatorname{Gp}\langle{A}\,|\,{\mathfrak{R}}\rangle$.
Here we may assume that $B\subseteq A$ and $z\in A\setminus B$, so that the
subgroup of $G$ generated by $\\{[b]_{G}:\ b\in B\\}$ is equal to the embedded
copy $H$ of $H_{1}$ in $G$.

Bearing in mind the notation introduced just before the statement of this
theorem, consider the special inverse monoid $M=M_{\mathfrak{R},W}$ where
$W=B\cup B^{-1}\cup\\{z\\}$ (so all words from $W$ here have length 1). By
Proposition 5.5 (1) we have that the monoid of right units of $M$ is
isomorphic to the submonoid $R$ of the free product $P=G*FG(t)$ generated by

$\\{[t]_{P}\\}\cup\\{[a]_{P},[a]_{P}^{-1}:\ a\in
A\\}\cup[t]_{P}T_{W}[t]_{P}^{-1},$

where $T_{W}$ is the submonoid of $G$ generated by
$\\{[z]_{G}\\}\cup\\{[b]_{G},[b]_{G}^{-1}:\ b\in B\\}$ (in other words, by
$[z]_{G}$ and $H$).

Furthermore, item (2) of Proposition 5.5 implies that the group of units of
$M$ is isomorphic to the subgroup $U$ of $P$ generated by

$\\{[a]_{P}:\ a\in A\\}\cup\\{[tbt^{-1}]_{P}:\ b\in B\\},$

with $U$ being the free product of $G$ and the subgroup $[t]_{P}H[t]_{P}^{-1}$
of $P$. This is a consequence of the fact that the word $tbt^{-1}$ represents
a unit of $M$ for all $b\in B$, while $tzt^{-1}$ does not (even though it does
represent a right unit), as we shall now justify. Indeed, from the displayed
equations immediately before the statement of Proposition 5.5, the fact that
$B\cup B^{-1}\subseteq W$ implies that
$[(tbt^{-1})(tb^{-1}t^{-1})]_{M}=[(tb^{-1}t^{-1})(tbt^{-1})]_{M}=1$ holds,
showing $[tbt^{-1}]_{M}$ and also $[tb^{-1}t^{-1}]_{M}$ is a unit of $M$. On
the other hand, seeking a contradiction assume that $tzt^{-1}$ represents a
unit of $M$. Then $[tzt^{-1}]_{P}$ is a unit of $R$, implying that
$[tz^{-1}t^{-1}]_{P}\in R$. Bearing in mind the generating set of $R$ provided
above, it follows that there are words
$w_{0},w_{1},\dots,w_{n}\in\overline{A}^{*}$ for some $n\geq 2$ and
$\varepsilon_{i}\in\\{1,-1\\}$, $1\leq i\leq n$, such that

$[tz^{-1}t^{-1}]_{P}=[w_{0}t^{\varepsilon_{1}}w_{1}t^{\varepsilon_{2}}w_{2}\dots
w_{m-1}t^{\varepsilon_{m}}w_{m}]_{P}$

holds, where no two consecutive $\varepsilon_{i},\varepsilon_{i+1}$ are equal
to $-1$, we have $[w_{i}]_{G}\neq 1$ whenever
$\varepsilon_{i}\neq\varepsilon_{i+1}$, and we have $w_{i}\in W^{*}$ whenever
$\varepsilon_{i}=1$ and $\varepsilon_{i+1}=-1$. By the Normal Form Theorem for
free products applied to $P$, this is possible only if $n=2$,
$\varepsilon_{1}=1$, $\varepsilon_{2}=-1$, $[w_{0}]_{G}=[w_{2}]_{G}=1$ and

$[z^{-1}]_{G}=[w_{1}]_{G},$

which from the conditions above implies $w_{1}\in W^{*}$. However, both
elements of $G$ involved in the latter equality actually belong the subgroup
$G_{1}$ of $G$ generated by $[z]_{G}$ and $H$, an isomorphic copy of $G_{0}$.
Therefore we arrive at $[z^{-1}]_{G_{0}}=[w_{1}]_{G_{0}}$, but this is
impossible by Britton’s Lemma (see also [19, Theorem IV.2.1]) applied to the
HNN extension $G_{0}$, as the word $w_{1}$ may contain only occurrences of the
letter $z$ but not of its inverse $z^{-1}$. This is a contradiction, whence
$[tzt^{-1}]_{M}$ is not a unit of $M$.

Now consider the Schützenberger group of the $\mathscr{H}$-class of the
element $[tzt^{-1}]_{P}$ in the (group-embeddable) monoid $R$, an isomorphic
copy of the RU-monoid of $M$. By Proposition 4.1 (4), this group is isomorphic
to

$U\cap[tz^{-1}t^{-1}]_{P}U[tzt^{-1}]_{P}.$

By using the Normal Form Theorem for free products again, we conclude that a
typical word representing an element from $U$ is of the form

$u_{1}tv_{1}t^{-1}u_{2}tv_{2}t^{-1}\dots u_{m}tv_{m}t^{-1}u_{m+1}$

where the words $u_{1},\dots,u_{m+1}\in\overline{A}^{*}$,
$v_{1}\dots,v_{m}\in\overline{B}^{*}$ are non-empty except possibly $u_{1}$
and $u_{m}$. Hence, the elements of $[tz^{-1}t^{-1}]_{P}U[tzt^{-1}]_{P}$ are
represented by words of the form

$tz^{-1}t^{-1}u_{1}tv_{1}t^{-1}u_{2}tv_{2}t^{-1}\dots
u_{m}tv_{m}t^{-1}u_{m+1}tzt^{-1},$

subject to the same conditions as above (note that if, for example, $u_{1}$ is
empty then the prefix $tz^{-1}t^{-1}u_{1}tv_{1}t^{-1}$ of the previous word
reduces to $tz^{-1}v_{1}t^{-1}$). So, upon employing the Normal Form Theorem
for the third time, we conclude that an element of $U$ also belongs to the
conjugate subgroup $[tz^{-1}t^{-1}]_{P}U[tzt^{-1}]_{P}$ of $P$ if and only if
$u_{1},u_{m+1}$ are empty and there exist words
$u_{2},u_{2}^{\prime},\dots,u_{m},u_{m}^{\prime}\in\overline{A}^{*}$ and
$v_{1},v_{1}^{\prime},\dots,v_{m},v_{m}^{\prime}\in\overline{B}^{*}$ such that

$[tv_{1}t^{-1}u_{2}tv_{2}t^{-1}\dots
u_{m}tv_{m}t^{-1}]_{P}=[tz^{-1}v_{1}^{\prime}t^{-1}u_{2}^{\prime}tv_{2}^{\prime}t^{-1}\dots
u_{m}^{\prime}tv_{m}^{\prime}zt^{-1}]_{P}.$

If $m\geq 2$, the latter condition is equivalent to the equalities
$[u_{i}]_{G}=[u_{i}^{\prime}]_{G}$ for all $2\leq i\leq m$,
$[v_{i}]_{G}=[v_{i}^{\prime}]_{G}$ for all $2\leq i\leq m-1$,
$[v_{1}]_{G}=[z^{-1}v_{1}^{\prime}]_{G}$ and
$[v_{m}]_{G}=[v_{m}^{\prime}z]_{G}$ holding simultaneously. This implies
$[z]_{G}=[v_{1}^{\prime}v_{1}^{-1}]_{G}=[(v_{m}^{\prime})^{-1}v_{m}]_{G}\in
H$, a contradiction. Hence, $m=1$. In such a case, the previous condition
reduces to

$[tv_{1}t^{-1}]_{P}=[tz^{-1}v_{1}^{\prime}zt^{-1}]_{P},$

which, on the other hand, holds for any words
$v_{1},v_{1}^{\prime}\in\overline{B}^{*}$ such that
$[v_{1}]_{G}=[z^{-1}v_{1}^{\prime}z]_{G}$. From this we immediately conclude
that

$U\cap[tz^{-1}t^{-1}]_{P}U[tzt^{-1}]_{P}\cong H\cap[z^{-1}]_{G}H[z]_{G}\cong
K_{1}.$

Thus we have that the considered Schützenberger group of $M$ is isomorphic to
$K$, completing the proof. ∎

######  Acknowledgements.

The research of the first named author is supported by the Personal Grant
F-121 “Problems of combinatorial semigroup and group theory” of the Serbian
Academy of Sciences and Arts. The research of the second named author was
supported by the EPSRC Fellowship Grant EP/V032003/1 “Algorithmic, topological
and geometric aspects of infinite groups, monoids and inverse semigroups”.

## References

  * [1] S. I. Adjan, Defining relations and algorithmic problems for groups and semigroups (in Russian), _Trudy Mat. Inst. Steklov._ 85 (1966), 123 pp.
  * [2] S. I. Adyan, G. U. Oganesyan, On the word and divisibility problems for semigroups with one relation (in Russian), _Mat. Zametki_ 41 (1987), 412–421.
  * [3] V. Y. Belyaev, Imbeddability of recursively defined inverse semigroups in finite presented semigroups (in Russian), _Sibirsk. Mat. Zh._ 25 (1984), 50–54.
  * [4] A. J. Cain, _Presentations of Subsemigroups of Groups_ , Ph.D. thesis, University of St Andrews, 2005.
  * [5] A. J. Cain, E. F. Robertson, N. Ruškuc, Cancellative and Malcev presentations for finite Rees index subsemigroups and extensions, _J. Austral. Math. Soc._ 84 (2008), 39–61.
  * [6] A. H. Clifford, G. B. Preston, _The Algebraic Theory of Semigroups, Vol. I & II_, Mathematical Surveys No. 7, American Mathematical Society, Providence, R.I., 1961 & 1967\.
  * [7] I. Dolinka, R. D. Gray, New results on the prefix membership problem for one-relator groups, _Trans. Amer. Math. Soc._ 374 (2021), 4309–4358.
  * [8] R. D. Gray, Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups, _Invent. Math._ 219 (2020), 987–1008.
  * [9] R. D. Gray, M. Kambites, Group $\mathcal{H}$-classes of finitely presented special inverse monoids, _submitted_ , arXiv: 2212.04204.
  * [10] R. D. Gray, N. Ruškuc, Units of special one-relator inverse monoids, _submitted_ , arXiv: 2103.02995.
  * [11] V. S. Guba, On a relation between the word problem and the word divisibility problem for semigroups with one defining relation (in Russian), _Izv. Ross. Akad. Nauk Ser. Mat._ 61 (6) (1997), 27–58.
  * [12] G. Higman, Subgroups of finitely presented groups, _Proc. Roy. Soc. London Ser. A_ 262 (1961), 455–475.
  * [13] J. E. Hopcroft, R. Motwani, J. D. Ullman, _Introduction to Automata Theory, Languages, and Computation_ (2nd ed.), Addison-Wesley, Boston, 2001.
  * [14] J. M. Howie, _Fundamentals of Semigroup Theory_ , London Math. Soc. Monographs Vol. 12, Clarendon Press, Oxford, 1995.
  * [15] S. V. Ivanov, S. W. Margolis, J. C. Meakin, On one-relator inverse monoids and one-relator groups, _J. Pure Appl. Algebra_ 159 (2001), 83–111.
  * [16] A. Juhász, Solution of the membership problem of the prefix monoid in certain one-relator groups, _Semigroup Forum_ 89 (2014), 479–490.
  * [17] G. Lallement, On monoids presented by a single relation, _J. Algebra_ 32 (1974), 370–388.
  * [18] M. V. Lawson, _Inverse Semigroups: The Theory of Partial Symmetries_ , World Scientific, Singapore, 1998.
  * [19] R. C. Lyndon, P. E. Schupp, _Combinatorial Group Theory_ , Springer-Verlag, Berlin, 1977.
  * [20] W. Magnus, Über diskontinuierliche Gruppen mit einer definierenden Relation. (Der Freiheitssatz), _J. reine angew. Math._ 163 (1930), 141–165.
  * [21] W. Magnus, Das Identitätsproblem für Gruppen mit einer definierenden Relation, _Math. Ann._ 106 (1932), 295–307.
  * [22] G. S. Makanin, On the identity problem in finitely defined semigroups (in Russian), _Dokl. Akad. Nauk SSSR_ 171 (1966), 285–287.
  * [23] A. Malheiro, Complete rewriting systems for codified submonoids, _Internat. J. Algebra Comput._ 15 (2005), 207–216.
  * [24] A. I. Mal’cev: _Algorithms and Recursive Functions_ (in Russian), Nauka, Moskva, 1965. [English translation: Wolters-Noordhoff, Groningen, 1970.]
  * [25] S. W. Margolis, J. C. Meakin, Z. Šuniḱ, Distortion functions and the membership problem for submonoids of groups and monoids, in: _Geometric Methods in Group Theory_ , pp. 109–129, Contemporary Math., Vol. 372, Amer. Math. Soc., 2005.
  * [26] J. Meakin, Groups and semigroups: connections and contrasts, in: _Groups St Andrews 2005, Vol. 2_ , pp. 357–400, London Math. Soc. Lecture Note Ser., Vol. 340, Cambridge Univ. Press, Cambridge, 2007.
  * [27] W. D. Munn, Free inverse semigroups, _Proc. London Math. Soc. (3)_ 29 (1974), 385–404.
  * [28] V. L. Murskiĭ, Isomorphic embeddability of a semigroup with enumerable set of defining relations to a finitely presented semigroup (in Russian), _Mat. Zametki_ 1 (1967), 217–224.
  * [29] C.-F. Nyberg Brodda, The word problem for one-relation monoids: a survey, _Semigroup Forum_ 103 (2021), 297–355.
  * [30] M. Petrich, _Inverse Semigroups_ , Wiley, 1984.
  * [31] H. E. Scheiblich, Free inverse semigroups, _Proc. Amer. Math. Soc._ 38 (1973), 1–7.
  * [32] B. M. Schein, Free inverse semigroups are not finitely presentable, _Acta Math. Acad. Sci. Hungar._ 26 (1975), 41–52.
  * [33] A. M. Turing, On computable numbers with an application to the Entscheidungsproblem, _Proc. London Math. Soc._ 42 (1936), 230–265. Erratum: _ibid._ 43 (1937), 544–546.
  * [34] L. Zhang, A short proof of a theorem of Adjan, _Proc. Amer. Math. Soc._ 116 (1992), 1–3.
  * [35] L. Zhang, Applying rewriting methods to special monoids, _Math. Proc. Cambridge Philos. Soc._ 112 (1992), 495–505.