Membership problems for positive one-relator groups and one-relation monoids

Abstract

Motivated by approaches to the word problem for one-relation monoids arising from work of Adian and Oganesian (1987), Guba (1997), and Ivanov, Margolis, and Meakin (2001), we study the submonoid and rational subset membership problems in one-relation monoids and in positive one-relator groups. We give the first known examples of positive one-relator groups with undecidable submonoid membership problem, and we apply this to give the first known examples of one-relation monoids with undecidable submonoid membership problem. We construct several infinite families of one-relation monoids with undecidable submonoid membership problem, including examples that are defined by relations of the form $w=1$ but which are not groups, and examples defined by relations of the form $u=v$ where both of u and v are nonempty. As a consequence, we obtain a classification of the right-angled Artin groups that can arise as subgroups of one-relation monoids. We also give examples of monoids with a single defining relation of the form $aUb = a$ and examples of the form $aUb=aVa$, with undecidable rational subset membership problem. We give a one-relator group defined by a freely reduced word of the form $uv^{-1}$ with $u, v$ positive words, in which the prefix membership problem is undecidable. Finally, we prove the existence of a special two-relator inverse monoid with undecidable word problem, and in which both the relators are positive words. As a corollary, we also find a positive two-relator group with undecidable prefix membership problem. In proving these results, we introduce new methods for proving undecidability of the rational subset membership problem in monoids and groups, including by finding suitable embeddings of certain trace monoids.

1 Introduction and summary of results

Central among algorithmic problems in combinatorial algebra is the word problem which, given an algebraic structure defined by generators and relations, asks whether there is an algorithm which takes two expressions over the generators and decides whether they represent the same element. The word problem for finitely presented semigroups was proved undecidable by Markov and, independently, Post in 1947. This was subsequently improved to the undecidability of the word problem in finitely presented cancellative semigroups by Turing [57] resp. groups by Novikov in 1952 and, independently, Boone and Britton in 1958. In spite of, and of course unaware of, these general impossibilities, Magnus [35] had proved in 1932 that the word problem is decidable for all groups with only a single defining relation; such groups are now called one-relator groups. By contrast, the word problem for monoids with one defining relation – one-relation monoids – remains a tantalizing open problem, in spite of over a century of investigations; see [45] for a recent survey of the problem.

The majority of the results on the word problem for one-relation monoids have been focused on trying to obtain a positive solution. The problem has now been solved positively in several cases. For example, Adian [2] proved that the word problem is decidable for all special one-relation monoids, being those admitting a presentation of the form $M = \operatorname {Mon}\big \langle A\:|\:w=1 \big \rangle $ , and results of Adian and Oganesian [4, 5] show that the word problem for a given $\operatorname {Mon}\big \langle A\:|\:u = v \big \rangle $ can be reduced to the word problem for a one-relation monoid of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa = aV a \big \rangle $ or $\operatorname {Mon}\big \langle a,b\:|\:bUa = a \big \rangle $ . In both of these cases, the word problem remains open.

There are several important reduction results in the literature that relate the word problem in one-relation monoids to other natural decision problems in one-relator groups, one-relation monoids, and also in a class that lies between these two called inverse monoids. As we shall explain in more detail below, these reduction results divide into three interrelated approaches to the word problem for one-relation monoids – namely, (i) results of Ivanov, Margolis, and Meakin [22] that give a reduction to the word problem in one-relator inverse monoids, (ii) results of Guba [16] that give a reduction to the submonoid membership problem in positive one-relator groups, and (iii) results of Adian and Oganesian [2, 3, 5] that give a reduction to the problem of deciding membership in principal right ideals of certain one-relation monoids. Here, a one-relator group is positive if it admits a presentation $\operatorname {Gp}\big \langle A\:|\:r=1 \big \rangle $ where no inverse symbol appears in r. Such groups were studied by, for example, Baumslag [6], as well as by Perrin and Schupp [50], who proved that a one-relator group is positive if and only if it is a one-relation monoid. There are also natural connections between the three approaches above. For example, Guba’s reduction may alternatively be expressed as a question asking for membership in the submonoid of a one-relator group with defining relation of the form $uv^{-1}=1$ generated by the prefixes of the defining relation, where $u, v$ are both positive words. This prefix membership problem for one-relator groups also arises naturally in the work of Ivanov, Margolis, and Meakin [22] where for cyclically reduced relator words, they show that word problem for the inverse monoid reduces to the prefix membership problem for the group. In the reduction result (iii), the principal right ideals of one-relation monoids will not typically be finitely generated submonoids, but they are examples of rational subsets of the monoid. Hence, one consequence of the reduction result (iii) of Adian and Oganesian is that a necessary step for constructing one-relation monoids with undecidable word problem is to first construct examples in which there are rational subsets in which membership is undecidable. This provides a connection between this approach and the approach of Guba to the word problem. Indeed, since by [50] every positive one-relator group is in particular a one-relation monoid, the study of the submonoid membership problem for one-relation monoids has as a special case the submonoid membership problem for positive one-relator groups. Hence, both of these approaches lie within the broader study of decidability of membership in rational subsets of one-relation monoids. These three approaches to the word problem for one-relation monoids with their various interrelations are summarized in the diagram in Figure 1. In addition to the motivation for their study coming from the connection with the word problem for one-relation monoids, the decision problems listed there (e.g., submonoid membership problem for one-relation monoids) are also natural questions to study in their own right.

Figure 1: A summary of the main results of this article and how they relate to the three approaches to the word problem for one-relation monoids given by reduction results of (i) Ivanov, Margolis, and Meakin [22], (ii) Guba [16], and (iii) Adian and Oganesian [2, 3, 5]. The arrows indicate implication of decidability. The problems in red are all proved to be undecidable in this article in the results listed in the corresponding boxes. The problems in white boxes are all open.

The connections explained above have led to extensive research, and numerous positive decidability results have been obtained for special cases of these problems; see, for example, [16, 22, 23, 24, 25, 38, 40]. Until recently, all of the focus of this work has been on showing that various special cases of these problems are decidable. However, several recent striking undecidability results in this area have for the first time brought into question the view that our attention should only be focused on seeking positive solutions to such problems. First, Gray [14] proved the existence of a special one-relator inverse monoid $\operatorname {Inv}\big \langle A\:|\:w=1 \big \rangle $ with undecidable word problem and at the same time proved that there are one-relator groups with undecidable submonoid membership problem. Then, Dolinka and Gray [12] went on to prove the existence of a one-relator group $\operatorname {Gp}\big \langle B\:|\:r=1 \big \rangle $ with undecidable prefix membership problem (where r is a reduced word). Given the reduction results of Guba [16] and Ivanov, Margolis, Meakin [22] discussed above, if any of these problems had been decidable, it would have resolved positively the word problem for one-relation monoids either in general, or for one of the two main open cases.

These recent undecidability results give the first serious indication that the word problem for one-relation monoids could in fact be undecidable. If it is undecidable, then, of course, all of the other reduction results mentioned above must also have negative answers. With that viewpoint in mind, the main goal of the current paper is to present a collection of new undecidability results all of the type that if they had been decidable, then it would have solved positively the word problem for one-relation monoids (either in general, or in one of the two main open cases). For this, we will conduct a detailed study of the rational subset, and submonoid, membership problems in positive one-relator groups, and in one-relation monoids. We will also introduce new tools for proving undecidability results of this kind.

Figure 1 gives a summary of the main undecidability results proved in this article and how they relate to the three approaches to the word problem discussed above. We shall now explain in more detail the reduction results discussed above, and summarized in Figure 1, and in each case give an overview of the undecidability results related to them that we shall prove in this paper.

The word problem for one-relation monoids of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ remains open. We shall call these the monadic one-relation monoids. Important work of Guba [16, Corollary 2.1] implies that the word problem for one-relation monoids in this class reduces to the submonoid membership problem for positive one-relator groups. In more detail, it follows from the results of Guba [16] that for every one-relation monoid of the form $M = \operatorname {Mon}\big \langle a,b\:|\:bQa=a \big \rangle $ , with a and b distinct, there exists a group defined by a presentation of the form $G = \operatorname {Gp}\big \langle a,b,C\:|\:aUba^{-1}=1 \big \rangle $ , where C is a finite set of new generators and U is a positive word over $\{a,b\} \cup C$ , such that if G has decidable prefix membership problem, then M has decidable word problem. In fact, Guba proves the equivalent dual result reducing the problem to the suffix membership problem in $\operatorname {Gp}\big \langle a,b,C\:|\:a^{-1}bUa=1 \big \rangle $ . Note that $\operatorname {Gp}\big \langle a,b,C\:|\:abUa^{-1}=1 \big \rangle $ is a positive one-relator group, as it is isomorphic to $\operatorname {Gp}\big \langle a,b,C\:|\:bU=1 \big \rangle $ . However, in general, the prefix monoid of $\operatorname {Gp}\big \langle a,b,C\:|\:abUa^{-1}=1 \big \rangle $ and of $\operatorname {Gp}\big \langle a,b,C\:|\:bU=1 \big \rangle $ will not be the same and, related to this, decidability of the prefix membership problem depends on the choice of presentation for a group rather than just its isomorphism type. Clearly, if the positive one-relator group G has decidable submonoid membership problem, then in particular, we can decide membership in the prefix monoid. Hence, this reduction result of Guba motivates the question of whether the submonoid membership problem is decidable for positive one-relator groups. Further motivation for this question comes from the fact that the submonoid membership problem is decidable for all surface groups if and only if it is decidable in the positive one-relator group with defining relation $a^2b^2c^2=1$ ; see Subsection 3.1 for further discussion of this important open problem. As mentioned above, it was only recently discovered in [14] that there exist one-relator groups that contain finitely generated submonoids in which membership is undecidable. The first example of such a one-relator group was constructed by Gray [14] and has the single defining relation $abba = baab$ . Recently, Nyberg–Brodda [47] proved that the one-relator groups $\operatorname {Gp}\big \langle a,b\:|\:a^mb^n = b^na^m \big \rangle $ have undecidable submonoid membership problem for every $m, n \geq 2$ . However, it may be shown (see below) that none of these one-relator groups admits a one-relator presentation with a positive defining relator word; that is, none of them are positive one-relator groups. The starting point for the work in this paper is to build on the examples from [47] to obtain positive one-relator groups with undecidable word problem by allowing m and n to vary through all integer values. As with previous examples, this is achieved by showing that the right-angled Artin group $A(P_4)$ of the path with four vertices embeds in the group and then appealing to a theorem of Lohrey and Steinberg [33, Theorem 2]. However, what makes doing this more difficult than in the cases considered in [47] is that the embedded copies of $A(P_4)$ that we find in the positive one-relator groups are no longer subgroups of finite index, so Reidemeister–Schreier rewriting methods alone are not sufficient to obtain the result. This gives the first main result of this paper (Theorem 3.8) where we exhibit an infinite family of positive one-relator groups all with undecidable submonoid membership problem.

In another direction, Guba’s reduction motivates the question of whether the prefix membership problem is decidable for all one-relator groups of the form $G = \operatorname {Gp}\big \langle a,b,C\:|\:aUba^{-1} = 1 \big \rangle $ , where U is a positive word. Here, the defining relator is a reduced word of the form $uv^{-1}$ , where u and v are both positive words. For words of this form, we shall call the corresponding one-relator groups $\operatorname {Gp}\big \langle A\:|\:uv^{-1}=1 \big \rangle $ quasi-positive. Quasi-positive one-relator groups have received attention in the literature in the study of the word problem for the related class of inverse monoids motivated by results of Ivanov, Margolis, and Meakin [22] discussed above and illustrated in the implications in the bottom two lines of Figure 1. The prefix membership problem for various families of quasi-positive one-relator groups has been solved positively by Margolis, Meakin, and $\check{\mathrm{S}}$ uni $\acute{\mathrm{k}} $ [38, Corollary 2.6], and some cases of the word problem for the corresponding class of inverse monoids have been resolved by Inam [20]. This connects more generally with the study of groups and inverse monoids defined by, so-called, Adian type presentations; see [55, 21]. In Section 4, we prove Theorem 4.1 showing that that there is a one-relator group of the form $\operatorname {Gp}\big \langle A\:|\:uv^{-1}=1 \big \rangle $ , where $u, v$ are positive words and $uv^{-1}$ is a reduced word, with undecidable prefix membership problem. This is the first known example of a quasi-positive one-relator group with undecidable prefix membership problem.

Our other main motivation for investigating membership problems in positive one-relator groups was the connection with the open question of whether one-relation monoids have decidable submonoid membership problem. When Magnus solved the word problem for one-relation groups, he actually proved a more general result: membership in Magnus subgroups ¹ is decidable. However, the general subgroup membership problem (also called generalized word problem) remains an important open problem for one-relator groups; see [8, Problem 18]. The analogue of this question for monoids asks whether one-relation monoids have decidable submonoid membership problem. This problem has been shown to be decidable in several examples and families of one-relation monoids; see [23, 24, 26, 48, 51]. Since by [50] a one-relator group is a one-relation monoid if and only if it is a positive one-relator group, the positive one-relator groups with undecidable submonoid membership problem that we give in this paper (Theorem 3.8) give the first known examples of one-relation monoids with undecidable submonoid membership problem (Corollary 3.9). Building on this, we shall construct several infinite families of one-relation monoids with undecidable submonoid membership problem including examples that are groups, examples that are defined by relations of the form $w=1$ but are not groups, and examples defined by relations of the form $u=v$ where neither u nor v is equal to $1$ , so these monoids have trivial groups of units; see Propositions 5.1 & 5.2, and Example 5.3. As part of this, we also obtain a classification of exactly which right-angled Artin groups can appear as subgroups of one-relation monoids; see Theorem 3.10.

Generalizing the submonoid membership problem is the rational subset membership problem, which asks for an algorithm to decide membership in the image of an arbitrary regular language. In groups, this problem has been surveyed by Lohrey [32]. The rational subset membership problem in one-relation monoids has also seen some study. Kambites’ work [26] on small overlap conditions can be used to show that almost all one-relation monoids, in a suitably defined sense, have decidable rational subset membership problem (cf. also [45, p. 338]). Furthermore, the rational subsets of the bicyclic monoid $\operatorname {Mon}\big \langle b,c\:|\:bc=1 \big \rangle $ have been fully described by Render and Kambites [51], and more generally the rational subset membership problem in any $\operatorname {Mon}\big \langle A\:|\:w=1 \big \rangle $ with virtually free group of units is decidable [48]. Results of Adian and Oganesian [2, 3, 5] imply that if membership in principal right ideals is decidable in all monoids of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ and $\operatorname {Mon}\big \langle a,b\:|\:bUa=aVa \big \rangle $ , then the word problem for all one-relation monoids is decidable (see also the related general statement [16, Lemma 3.1]). The principal right ideals of these monoids will not typically be finitely generated submonoids, but they are rational subsets. Motivated by this, in Section 6, we extend our investigation to the study of the rational subset membership problem in these two classes of one-relation monoids. Further motivation for studying this problem for monoids of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ comes from the result [16, Theorem 4.1] relating the word problem in these monoids to the membership problem in both principal left and principal right ideals. In Theorem 6.1, we give an infinite family of monoids of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ all with undecidable rational subset membership problem. Then in Remark 6.11, we explain how these examples can be adapted to give examples of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=aVa \big \rangle $ with the same property. To prove these results, it is necessary for us to introduce new techniques since the only groups that monoids in these classes can embed are trivial groups, and hence, the usual approach of embedding $A(P_4)$ is not possible. For this, we prove a new general result, Theorem 6.2, which shows that a left-cancellative monoid has undecidable rational subset membership problem if it embeds a copy of the trace monoid $T(P_4)$ that is generated by a set of elements that are all related by Green’s $\mathcal {L}$ -relation. This result is in some ways surprising since any trace monoid itself, unlike right-angled Artin groups, necessarily has decidable rational subset membership problem, so the way in which the trace monoid embeds is crucial. As another corollary to this new general result for left-cancellative monoids, we deduce (Corollary 6.4) that any group containing the trace monoid $T(P_4)$ has undecidable rational subset membership problem, and we then explore some applications of this to proving the undecidability of the rational subset membership problem in groups.

In Section 7, we shall apply the results of the previous section to the word problem for special inverse monoids. It was proved in [14] that there are special one-relator inverse monoids $\operatorname {Inv}\big \langle A\:|\:w=1 \big \rangle $ with undecidable word problem. In all known examples, the word w is not a reduced word, and it remains an open problem whether the word problem is decidable in that case. This is an important question since, if it is, then by [22, Theorem 2.2] this would imply that all one-relation monoids have decidable word problem. In particular, it is open whether there is a positive one-relator inverse monoid with undecidable word problem. Motivated by this, in Section 7, we explain how the word problem for one-relation monoids also reduces to the word problem for positive $2$ -relator special inverse monoids, and then in Theorem 7.4, we show the existence of a $2$ -relator special inverse monoid with undecidable word problem and in which both defining words are positive words. We use this result to prove the existence of a positive two-relator group with undecidable prefix membership problem in Corollary 7.6.

2 Preliminaries

In this section, we fix some notation and recall some background definitions and results from geometric and combinatorial group and monoid theory. Inverse monoids will only be considered later in Section 7, and we defer giving the more involved notation and definitions for inverse monoids to that section. For additional background we refer the reader to [36, 34] for combinatorial group theory, [19] for monoid and semigroup theory, [53, Chapter 1] for monoid presentations, and [31] for the theory of inverse monoids.

Monoid and group presentations

For a nonempty alphabet A, we use $A^*$ to denote the free monoid of all words over A, including the empty word which we denote by $\varepsilon $ . A monoid presentation is a pair $\operatorname {Mon}\big \langle A\:|\:R \big \rangle $ , where A is an alphabet and R is a subset of $A^* \times A^*$ . The monoid defined by this presentation is the quotient $A^* / \sigma $ of the free monoid by the congruence $\sigma $ on $A^*$ generated by R. We usually write a defining relation $(u,v) \in R$ as $u=v$ . Similarly, when working with a fixed monoid presentation $\operatorname {Mon}\big \langle A\:|\:R \big \rangle $ given any two words $\alpha ,\beta \in A^*$ , we write $\alpha =\beta $ to mean that $\alpha $ and $\beta $ are $\sigma $ -related; that is, they represent the same element of the monoid defined by the presentation. We write $\alpha \equiv \beta $ to mean that $\alpha $ and $\beta $ are equal as words in the free monoid $A^*$ . A monoid presentation is called special if all the defining relations are of the form $w=1$ .

A group presentation is a pair $\operatorname {Gp}\big \langle A\:|\:R \big \rangle $ , where A is an alphabet and R is a subset of $(A \cup A^{-1})^* \times (A \cup A^{-1})^*$ , where $A^{-1} = \{a^{-1} : a \in A \} $ is disjoint from A. The group defined by this presentation is then the quotient of the free group $F_A$ on A by the normal subgroup generated by the set of all $uv^{-1}$ for $(u,v) \in R$ . As for monoids, when working with a fixed group presentation, we write $\alpha = \beta $ to mean that the words represent the same element of the group, and we write the defining relations in the form $u=v$ .

A one-relator monoid (also called one-relation monoid) is one defined by a presentation of the form $\operatorname {Mon}\big \langle A\:|\:u=v \big \rangle $ . Similarly, a one-relator group is one that is defined by a presentation of the form $\operatorname {Gp}\big \langle A\:|\:w=1 \big \rangle $ .

We often abuse terminology by talking about the group $\operatorname {Gp}\big \langle A\:|\:R \big \rangle $ or the monoid $\operatorname {Mon}\big \langle A\:|\:R \big \rangle $ where we mean the group or monoid defined by the given presentation.

Given a subset X of a monoid, we use $\operatorname {Mon}\big \langle X \big \rangle $ to denote the submonoid generated by X, and similarly, if X is a subset of a group, then $\operatorname {Gp}\big \langle X \big \rangle $ denotes the subgroup generated by X.

Submonoid and rational subset membership problems

The set of all rational subsets of a monoid M is the smallest subset of the power set of M which contains all finite subsets of M, and which is closed under union, product, and Kleene hull. Here, the Kleene hull of a subset L of a monoid M is just the submonoid of M generated by L. Clearly, every finitely generated submonoid of M is a rational subset. If M is finitely generated by a set A, and $\phi :A^* \rightarrow M$ is the corresponding canonical homomorphism, then a subset $L \subseteq M$ is rational if and only if $L = \phi (K)$ for some rational subset K of $A^*$ . Since by Kleene’s theorem the rational subsets of $A^*$ are the same as those that can be recognized by a finite state automaton; in this case, K is the language defined by some finite state automaton, and L is the set of all elements of M represented by words in that language.

Let M be a monoid finitely generated by a set A, and let $\phi :A^* \rightarrow M$ be the corresponding canonical homomorphism. The submonoid membership problem for M is the following decision problem:

• • Input: A finite set of words $\Delta \subseteq A^*$ and a word $w \in A^*$

• • Question: $\phi (w) \in \phi (\Delta ^*)$ ?

Observe that $\phi (\Delta ^*)$ is equal to the submonoid of M generated by $\phi (\Delta )$ . The decidability of this problem is independent of the choice of finite generating set for the monoid. For a group G with finite generating set A, the set $A \cup A^{-1}$ is a finite monoid generating set for G, and then the submonoid membership problem for G is defined as above, where G is the monoid generated by $A \cup A^{-1}$ . Let $L(\mathcal {A})$ denote the language recognized by a finite automaton $\mathcal {A}$ . Then the rational subset membership problem for M is the decision problem

• • Input: A finite automaton $\mathcal {A}$ over the alphabet A and a word $w \in A^*$

• • Question: $\phi (w) \in \phi (L(\mathcal {A}))$ ?

Note that by the Kleene Theorem, the input to the rational subset membership problem could alternatively be taken to be a rational expression over the alphabet A. As for the submonoid membership problem, the rational subset membership problem also applies to groups where we view the group as a monoid generated by $A \cup A^{-1}$ . As every finitely generated submonoid is a rational subset (being precisely the Kleene hull of a finite set), decidability of the rational subset membership problem implies decidability of the submonoid membership problem.

A priori, it may seem natural to assume that the rational subset membership problem ought to be strictly harder than the submonoid membership problem. However, whether this is actually the case remains an open problem; the problems may be equivalent, and there are some reasons to believe that they may be (see [33]).

In the two decision problems above, the submonoid (resp. rational subset) is part of the input. The non-uniform analogues of these problems can also be studied where one considers a fixed finitely generated submonoid (or rational subset) and asks whether there is an algorithm deciding membership in that particular subset. In general, for any subset S of M, by the membership problem for S within M we mean the decision problem

• • Input: A word $w \in A^*$

• • Question: $\phi (w) \in S$ ?

Similarly, we talk about the membership problem for S within G, where G is a finitely generated group. This non-uniform version is sometimes called the weak membership problem, with the uniform being called strong (e.g., by Mikhailova [42] in the context of the subgroup membership problem).

Decidability of these problems is preserved when taking substructures in the following sense. Let M be a finitely generated monoid and let T be a finitely generated submonoid of M. If M has decidable submonoid (resp. rational subset) membership problem, then so does T. In addition to this, for any subset S of T, if the membership problem for S within M is decidable, then the membership problem for S within T is also decidable. See [32, §5] for more details on how to prove closure properties like these.

RAAGs and trace monoids

For a finite simplicial graph $\Gamma $ with vertex set $V\Gamma $ , we use $A(\Gamma )$ to denote the right-angled Artin group (abbreviated to RAAG) determined by $\Gamma $ , so $A(\Gamma )$ is the group defined by the presentation

$$\begin{align*}\operatorname{Gp}\big\langle V\Gamma\:|\:xy=yx \text{ if and only if }x \text{ is adjacent to}\ y\ \text{in}\ \Gamma \big\rangle. \end{align*}$$

We will use $T(\Gamma )$ to denote the corresponding trace monoid defined by

$$\begin{align*}\operatorname{Mon}\big\langle V\Gamma\:|\:xy=yx \text{ if and only if } x \text{ is adjacent to }\ y\ \text{in}\ \Gamma \big\rangle. \end{align*}$$

We shall now record some facts from the theory of trace monoids and RAAGs that we need later on. For more comprehensive background on RAAGs and trace monoids, we refer the reader to [10, 11]. It was proved by Paris [49] that for any graph $\Gamma $ , the identity map on $V\Gamma $ induces an embedding of the trace monoid $T(\Gamma )$ into the corresponding RAAG $A(\Gamma )$ .

Much is known about the behavior of rational subsets of trace monoids (see, for example, [11]). In particular, since trace monoids are defined by presentations where the defining relations are all length preserving (so called “homogeneous presentations”), it follows that any trace monoid has decidable rational subset membership problem. By contrast, not every RAAG has decidable rational subset membership. Indeed, Lohrey and Steinberg [33] proved that a RAAG $A(\Gamma )$ has decidable submonoid membership problem if and only if it has decidable rational subset membership problem if and only if $\Gamma $ does not embed the path $P_4$ with four vertices, or the square $C_4$ with four vertices, as an induced subgraph. A complete characterization of RAAGs with decidable subgroup membership problem is not, however, known; it is, for example, unknown whether $A(C_5)$ has decidable subgroup membership problem.

Inverse monoid presentations

We just give the essential definitions from combinatorial inverse semigroup theory that we need. We refer the reader to [41] and [31] for a more comprehensive treatment of the subject.

An inverse monoid M is a monoid with the property that for every $m \in M$ , there is a unique element $m^{-1} \in M$ satisfying $mm^{-1}m=m$ and $m^{-1}mm^{-1}=m^{-1}$ . For any alphabet A, the free inverse monoid over A is the monoid defined by the presentation

$$\begin{align*}\operatorname{Mon}\big\langle A \cup A^{-1}\:|\:uu^{-1}u=u,\ uu^{-1}vv^{-1}=vv^{-1}uu^{-1}\ (u,v\in\overline{A}^\ast) \big\rangle, \end{align*}$$

where $(a^{-1})^{-1} = a$ and $(a_1 \ldots a_k)^{-1} = a_k^{-1} \ldots a_1^{-1}$ . We use $\mathrm {FI_A}$ to denote the free inverse monoid on A. An inverse monoid presentation is a pair $\operatorname {Inv}\big \langle A\:|\:R \big \rangle $ , where A is an alphabet and the set of defining relations R is a subset of $(A \cup A^{-1})^\ast \times (A \cup A^{-1})^\ast $ . The presentation $\operatorname {Inv}\big \langle A\:|\:R \big \rangle $ defines the inverse monoid $\mathrm {FI_A}/\rho $ , where $\rho $ is the congruence on the free inverse monoid $\mathrm {FI_A}$ generated by R. By a special inverse monoid, we mean one defined by a presentation where all the defining relations in the presentation are of the form $r=1$ . The maximal group image of $\operatorname {Inv}\big \langle A\:|\:R \big \rangle $ is the group $\operatorname {Gp}\big \langle A\:|\:R \big \rangle $ defined by the same presentation, and the identity map on A defines a surjective homomorphism from the inverse monoid onto its maximal group image.

3 Membership problems in positive one-relator groups

In this section, we construct positive one-relator groups with undecidable submonoid membership problem. As discussed in the previous section, the following one-relator groups

$$\begin{align*}\operatorname{Gp}\big\langle a,b\:|\:[ab, ba] = 1 \big\rangle, \quad \text{resp.} \quad \big\langle a,b\:|\:[a^m, b^n] = 1 \big\rangle \: (m, n \geq 2), \end{align*}$$

were shown to have undecidable submonoid membership problem in work of Gray [14] and Nyberg-Brodda [47], respectively. However, it is a consequence of Lyndon’s identity theorem that none of these groups admits a positive one-relator presentation. Indeed, it follows from Lyndon’s identity theorem that any one-relator group of the form $\operatorname {Gp}\big \langle A\:|\:[u, v] = 1 \big \rangle $ has second homology group $H_2(G; \mathbb {Z}) \cong \mathbb {Z}$ , while on the other hand, any positive one-relator group has $H_2(G; \mathbb {Z}) = 0$ ; see [9, II.4, Example 3].

For $m,n \in \mathbb {N}$ , define a class of groups by the presentation

(1) $$ \begin{align} G_{m,n} = \operatorname{Gp}\big\langle x,y\:|\:x^m y^n = y^n x^{-m} \big\rangle. \end{align} $$

Remark 3.1 If $n=1$ , then $G_{m,1} = \operatorname {Gp}\big \langle x, y\:|\:y x^m y^{-1} = x^{-m} \big \rangle $ is the unimodular Baumslag-Solitar group $\operatorname {BS}(m, -m)$ which is known (see, for example, [47, paragraph preceding Prop. 3.9]) to be virtually a direct product of $\mathbb {Z}$ and a finite rank free group, and hence, $G_{m,1}$ has has decidable rational subset membership problem.

The key property of the groups $G_{m,n}$ is the following.

Lemma 3.2 The group $G_{m,n}$ has decidable submonoid membership problem if and only if $m =1$ or $n=1$ . Furthermore, if $m, n \geq 2$ , then $G_{m,n}$ contains a fixed finitely generated submonoid in which membership is undecidable.

Proof Decidability for $n = 1$ is discussed in Remark 3.1, while the case for $m=1$ will be covered in Remark 3.4. For $m,n \geq 2$ , we will obtain an injection $i \colon A(P_4) \longrightarrow G_{m,n}$ in Lemma 3.6. In [33], it is shown that $A(P_4)$ contains a fixed submonoid where membership is undecidable. So, if $m,n \geq 2$ , then the submonoid membership problem is undecidable in $G_{m,n}$ .

Thus, to prove the above lemma, we must prove Lemma 3.6. We do this by a Reidemeister–Schreier rewriting procedure.

Lemma 3.3 The subgroup $K_{m,n} = \operatorname {Gp}\big \langle y^{2n}, y^i x y^{-i} \text { for }0 \leq i \leq 2n - 1 \big \rangle $ of $G_{m,n}$ , has the following presentation:

$$\begin{align*}\operatorname{Gp}\big\langle \beta,\, \alpha_i \text{ for }0 \leq i \leq 2n - 1\:|\:\alpha_i^m \alpha_{i+n}^m=1,\, [\alpha_i^m, \beta]=1 \text{ for }0 \leq i \leq n - 1 \big\rangle, \end{align*}$$

where $\beta $ corresponds to $y^{2n}$ , and $\alpha _i$ corresponds to $y^i x y^{-i}$ for all $0 \leq i \leq 2n - 1$ .

Proof Note that $K = K_{m,n}$ is normal in $G = G_{m,n}$ , as it is closed under conjugation by both x and y, with quotient equal to

$$\begin{align*}G/K = \operatorname{Gp}\big\langle y\:|\:y^{2n}=1 \big\rangle \cong \mathcal{C}_{2n} = \text{ cyclic group of order }2n. \end{align*}$$

We proceed to find a presentation for K using the Reidemeister-Schreier procedure (see [34]) with

$$\begin{align*}G = \operatorname{Gp}\big\langle S\:|\:R \big\rangle, \text{ where } S = \{x,y\}, \text{ and } R = x^m y^n x^m y^{-n}. \end{align*}$$

A Schreier transversal for K in G is $T = \{\, y^i \mid 0 \leq i \leq 2n - 1 \,\}$ , giving a set of generators for K as $U = \{ts(\overline {ts})^{-1}\mid t\in T,\; s \in S,\; ts \not \in T \}$ where $\overline {w}$ is the representative of w in T.

Any $t\in T$ can be written as $y^i$ for $0 \leq i \leq 2n-1$ , so

$$\begin{align*}ts(\overline{ts})^{-1} = y^{i}s(\overline{y^{i}s})^{-1} = \begin{cases} y^{i}x(\overline{y^{i}x})^{-1} & \text{if } s = x,\\ y^{i}y(\overline{y^{i}y})^{-1} & \text{if } s = y. \end{cases} \end{align*}$$

As $x\in K$ , one has $\overline {y^{i}x} = y^i$ for all $0 \leq i \leq 2n-1$ . Also, $\overline {y^{i}y} = y^{i+1}$ for $0 \leq i \leq 2n-2$ and $\overline {y^{2n-1}y} = 1$ . One obtains $\beta = y^{2n}$ and $\alpha _i = y^ixy^{-i}$ for $0 \leq i \leq 2n-1$ as generators of K; hence,

$$\begin{align*}U = \{\, \beta = y^{2n},\, \alpha_i = y^ixy^{-i} \text{ for }0 \leq i \leq 2n-1\,\} \end{align*}$$

gives a set of generators for K.

To get relations for K, rewrite $tRt^{-1}$ for $t\in T$ and $R = x^m y^n x^m y^{-n}$ , using generators in U.

Write any $t\in T$ as $y^i$ for some $0 \leq i \leq 2n-1$ . One obtains

$$ \begin{align*} tRt^{-1} = y^i(x^m y^n x^m y^{-n})y^{-i} & = \begin{cases} (y^i x^m y^{-i}) (y^{i + n} x^m y^{-i - n}) & \text{if } 0 \leq i \leq n - 1 \\ (y^i x^m y^{-i}) y^{2n} (y^{i - n} x^m y^{-i + n}) y^{-2n} & \text{if } n \leq i \leq 2n - 1 \end{cases} \\ & = \begin{cases} \alpha_i^m \alpha_{i+n}^m & \text{if } 0 \leq i \leq n - 1, \\ \alpha_i^m \beta \alpha_{i-n}^m \beta^{-1} & \text{if } n \leq i \leq 2n - 1. \end{cases} \end{align*} $$

The first relation gives $\alpha _{i+n}^m = \alpha _i^{-m}$ for any $0 \leq i \leq n - 1$ ; substituting it in the second line, one obtains the relation $[\alpha _i^m, \beta ]$ for all $0 \leq i \leq n - 1$ .

So, $ V = \{\, \alpha _i^m \alpha _{i+n}^m,\, [\alpha _i^m, \beta ] \mid 0 \leq i \leq n - 1 \,\}$ gives the relations of K, as desired.

Remark 3.4 Note that for $m=1$ , the subgroup $K_{1,n}$ is actually a RAAG, isomorphic to $\mathbb {Z} \times F_n$ . In this case, the group $G_{1,n}$ is a finite extension of $\mathbb {Z} \times F_n$ , implying that it has decidable rational subset membership problem (so, a fortiori, also decidable submonoid membership problem); see [33]).

Section 3 of article [47] treats a class of groups called right-angled Baumslag-Solitar-Artin groups, for which the problem of decidable submonoid membership is studied. One particular example is the family $\operatorname {B}(S_{n,m})$ with $n,m \in \mathbb {Z}$ , where $m,n \geq 0$ , defined as

(2) $$ \begin{align} \operatorname{B}(S_{n,m}) = \operatorname{Gp}\big\langle d, c_i \text{ for }0 \leq i \leq n - 1\:|\:[c_i^m, d]=1 \text{ for }0 \leq i \leq n - 1 \big\rangle. \end{align} $$

Another example is the family $B(P_{3,m})$ with $m \in \mathbb {Z}$ where $m \geq 0$ , defined as

(3) $$ \begin{align} \operatorname{B}(P_{3,m}) = \operatorname{Gp}\big\langle w_0,w_1,w_2\:|\:[w_0,w_2]=1, [w_0,w_1^m]=1 \big\rangle. \end{align} $$

Lemma 3.5 The group $\operatorname {B}(S_{n,m})$ injects in $G_{m,n}$ . In particular, the map

(4) $$ \begin{align} \sigma \colon d \mapsto y^{2n}, c_i \mapsto y^ixy^{-i} \: (0 \leq i \leq n) \end{align} $$

defines an injective homomorphism $\sigma \colon \operatorname {B}(S_{n,m}) \to G_{m,n}$ .

Proof Recall from Lemma 3.3 that the subgroup

$$\begin{align*}K_{m,n} = \operatorname{Gp}\big\langle y^{2n}, y^i x y^{-i} \text{ for }0 \leq i \leq 2n - 1 \big\rangle\end{align*}$$

of $G_{m,n}$ , has the following presentation:

$$\begin{align*}\operatorname{Gp}\big\langle \beta,\, \alpha_i \text{ for }0 \leq i \leq 2n - 1\:|\:\alpha_i^m \alpha_{i+n}^m=1,\, [\alpha_i^m, \beta]=1 \text{ for }0 \leq i \leq n - 1 \big\rangle, \end{align*}$$

where $\beta $ corresponds to $y^{2n}$ , and $\alpha _i$ corresponds to $y^i x y^{-i}$ for all $0 \leq i \leq 2n - 1$ . Let $K \cong K_{m,n} $ denote the group defined by the above presentation, let $B = \operatorname {B}(S_{n,m})$ , and consider the two maps

$$ \begin{align*} s: B \longrightarrow K\, & \text{ given by } s(d) = \beta,\, s(c_i) = \alpha_i\, \text{ for any } 0 \leq i \leq n - 1,\\ \rho: K \longrightarrow B\, & \text{ given by } \rho(\beta) = d,\, \rho(\alpha_i) = c_i,\, \rho(\alpha_{i+n}) = c_i^{-1}\, \text{ for any } 0 \leq i \leq n - 1. \end{align*} $$

Obviously, both s and $\rho $ induce well-defined homomorphisms, as they respect the relations. Moreover, one has $\rho \circ s = \text {id}_B$ , which implies that s is injective. It follows that there is an injective homomorphism $\sigma :\operatorname {B}(S_{n,m}) \hookrightarrow G_{m,n}$ that maps $d \mapsto y^{2n}$ and $c_i \mapsto y^i x y^{-i}$ for all $0 \leq i \leq n - 1$ .

Lemma 3.6 There exists an embedding $i\colon A(P_4) \hookrightarrow G_{m,n}$ from

$$\begin{align*}A(P_4) = \operatorname{Gp}\big\langle A, B, C, D\:|\:AB = BA, BC = CB, CD = DC \big\rangle \end{align*}$$

into $G_{m,n}$ given by

$$\begin{align*}i(A) = y x^m y^{-1},\, i(B) = y^{2n},\, i(C) = x^m,\, i(D) = x y^{2n} x^{-1}. \end{align*}$$

Proof From the proof of Proposition 3.5 in [47] (see also Proposition 3.3 there), one obtains an embedding of $A(P_4)$ in $\operatorname {B}(S_{n,m})$ for $n, m \geq 2$ . One such embedding is the following:

$$\begin{align*}j: \operatorname{Gp}\big\langle A, B, C, D\:|\:AB = BA, BC = CB, CD = DC \big\rangle \hookrightarrow \operatorname{B}(S_{n,m}), \end{align*}$$

given by $j(A) = c_1^m,\, j(B) = d,\, j(C) = c_0^m,\, j(D) = c_0dc_0^{-1}$ . Indeed, to show that j is an embedding, we note that by Lemma 3.5, the group $\operatorname {B}(S_{n,m})$ injects into $G_{m,n}$ , where

$$\begin{align*}\operatorname{B}(S_{n,m}) = \operatorname{Gp}\big\langle d, c_i \text{ for }0 \leq i \leq n - 1\:|\:[c_i^m, d]=1 \text{ for }0 \leq i \leq n - 1 \big\rangle, \end{align*}$$

with $d \mapsto y^{2n}$ , and for all $0 \leq i \leq n - 1$ , one has $c_i \mapsto y^ixy^{-i}$ . In particular, the RABSAG $\operatorname {B}(S_{2,m})$ (in the sense of [47]) defined by the graph

injects in $\operatorname {B}(S_{n,m})$ . By [47, Proposition 3.5] and its proof, the group $\operatorname {B}(P_{3,m})$ injects into $\operatorname {B}(S_{n,m})$ , with one embedding being via the RABSAG defined by the graph

Here, we have abused notation by letting the vertices of the graph $P_{3,m}$ above be labeled by their images in $\operatorname {B}(S_{n,m})$ under the prescribed embedding. That is, inside $\operatorname {B}(S_{n,m})$ , defined as above, the elements $c_1^m, d$ , and $c_0$ generate an isomorphic copy of $\operatorname {B}(P_{3,m})$ where, in terms of the presentation given in equation (3), this isomorphism is given by mapping $w_0$ to d, $w_2$ to $c_1^m$ , and $w_1$ to $c_0$ . Continuing, and using the analogous slight abuse of notation also for RAAGs, the RAAG defined by the graph

now embeds in our chosen copy of $\operatorname {B}(P_{3,m})$ by unpacking the proof of [47, Proposition 3.3] together with the generalization of that result explained in [47] in the paragraph immediately after the proof of [47, Proposition 3.3]. That is, inside $\operatorname {B}(S_{n,m})$ as above, the elements $c_1^m, d, c_0^m$ , and $c_0dc_0^{-1}$ generate a copy of $A(P_4)$ . It follows that j is indeed an embedding of $A(P_4)$ into $\operatorname {B}(S_{n,m})$ .

Now the composition $i = \sigma \circ j$ where $\sigma $ is the injection $\sigma \colon \operatorname {B}(S_{n,m}) \hookrightarrow G_{m,n}$ defined by (4), from Lemma 3.5, gives the desired embedding $i\colon A(P_4) \hookrightarrow G_{m,n}$ .

Putting it all together, we have now shown Lemma 3.2. In particular, for every $m, n \geq 2$ , the one-relator group $G_{m,n}$ has undecidable submonoid membership problem. Importantly, these groups also have the following property:

Lemma 3.7 For every $m, n \geq 1$ , the group $G_{m,n}$ is a positive one-relator group.

Proof Consider the relation $x^m y^n x^m y^{-n}$ . We want to change it to an equivalent positive relation, so we introduce new generators $a,b$ with $y = a$ and $x = b a ^{n}$ . Now we write the group relation in terms of a and b as

$$ \begin{align*} (b a^{n})^m a^n (b a^{n})^m a^{-n} & = (b a^{n})^m a^n (b a^{n})^{m-1} (b a^{n}) a^{-n} \\ & = (b a^{n})^m a^n (b a^{n})^{m-1} b \\ & = (b a^{n})^m (a^{n} b)^m. \end{align*} $$

This way, we obtain another equivalent presentation for $G_{m,n}$ as

(5) $$ \begin{align} G_{m,n} \cong \operatorname{Gp}\big\langle a,b\:|\:(b a^n)^m(a^n b)^m = 1 \big\rangle. \end{align} $$

Thus, $G_{m,n}$ is a positive one-relator group.

We have proved the following, which is the main result of this section:

Theorem 3.8 For all $m,n \geq 2$ , the group

$$\begin{align*}G_{m,n} \cong \operatorname{Gp}\big\langle a,b\:|\:(b a^n)^m(a^n b)^m = 1 \big\rangle \end{align*}$$

is a positive one-relator group that contains a fixed finitely generated submonoid in which membership is undecidable. In particular, there are positive one-relator groups with undecidable submonoid membership problem.

Note that if $M_{m,n}$ denotes the monoid with the same defining relation as in (5), then b is invertible in $M_{m,n}$ , being both left- and right-invertible by virtue of the defining relation. By cyclically permuting the letters b from the ends of the defining relation, we similarly also conclude that a is invertible. Hence, $M_{m,n}$ is a group, so necessarily, $M_{m,n} = G_{m,n}$ . Thus, we conclude the following:

Corollary 3.9 There exists a one-relation monoid with undecidable submonoid membership problem. Furthermore, there exists such a monoid with a presentation of the form $\operatorname {Mon}\big \langle A\:|\:w=1 \big \rangle $ . Additionally, one can construct such monoids which contain a fixed finitely generated submonoid in which membership is undecidable.

Using this, it is now not difficult to find the following classification of right-angled Artin subgroups of one-relation monoids:

Theorem 3.10 Let $\Gamma $ be a finite graph and let $A(\Gamma )$ be the right-angled Artin group that it defines. Then the following are equivalent.

1. (i) $\Gamma $ is a forest;

2. (ii) $A(\Gamma )$ embeds into a one-relator group;

3. (iii) $A(\Gamma )$ embeds into a positive one-relator group;

4. (iv) $A(\Gamma )$ embeds into a one-relation monoid $\operatorname {Mon}\big \langle A\:|\:u=v \big \rangle $ ;

5. (v) $A(\Gamma )$ embeds into a one-relation monoid of the form $\operatorname {Mon}\big \langle A\:|\:w=1 \big \rangle $ .

Proof The equivalence of (i) and (ii) follows from [14, Remark 2.3].

(i) $\Rightarrow $ (iii): By [28, Theorem 1.8], if $\Gamma $ is a finite forest, then $A(\Gamma )$ embeds in $A(P_4)$ , which in turn embeds in a positive one-relator group by Lemma 3.6 and Lemma 3.7 above.

(iii) $\Rightarrow $ (v): This follows from the result of Perrin and Schupp [50] showing that any positive one-relator group admits a one-relation monoid presentation.

(v) $\Rightarrow $ (iv) is trivial.

(iv) $\Rightarrow $ (ii): If $A(\Gamma )$ embeds into $\operatorname {Mon}\big \langle A\:|\:u=v \big \rangle $ , then it must embed in a maximal subgroup of $\operatorname {Mon}\big \langle A\:|\:u=v \big \rangle $ , which by the results of [30] must itself be a one-relator group. Hence, $A(\Gamma )$ embeds in a one-relator group.

3.1 Positive one-relator groups and surface groups

The class of positive one-relator groups has received some attention in the literature. They were first studied by Baumslag [6] in 1971, who proved that the intersection of all terms in the lower central series in any positive one-relator group is trivial. While Perrin and Schupp [50] observed that not all positive one-relator groups are residually finite, Wise [58] later studied the residual finiteness of positive one-relator groups, proving that any positive one-relator group with torsion is residually finite (this result was later sharpened by Wise [59] by dropping the positivity condition). In general, classifying which positive one-relator groups have decidable submonoid membership problem seems difficult. It is even unknown whether every one-relator group with torsion has decidable submonoid membership problem [27, Questions 20.68 & 20.69]. One-relator groups with torsion are hyperbolic by the B. B. Newman Spelling Theorem; thus, a natural question in line with this was implicitly asked by Ivanov, Margolis, and Meakin [22, p. 110]:

Question 3.11 Is the submonoid/rational subset membership problem decidable in every surface group?

Here, a surface group G (of genus $g \geq 0$ ) is one which is the fundamental group of some compact $2$ -manifold; thus, either $G \cong \mathcal {N}_g$ or $G \cong \mathcal {S}_g$ , where

$$\begin{align*}\mathcal{N}_g = \operatorname{Gp}\big\langle a_1, \dots, a_g|a_1^2 a_2^2 \cdots a_g^2 = 1 \big\rangle\text{ and } \mathcal{S}_g = \operatorname{Gp}\big\langle a_1, b_1, \dots, a_g, b_g|\prod_{i=1}^g [a_i, b_i] = 1 \big\rangle. \end{align*}$$

We remark that the subgroup membership problem in all surface groups is, by contrast, well-known to be decidable [54], but in general, hyperbolic groups can even have undecidable subgroup membership problem by using the Rips construction [52]. Note further that $\mathcal {N}_2 \cong \operatorname {Gp}\big \langle a,b\:|\:a^2b^2 = 1 \big \rangle $ and $\mathcal {S}_1 \cong \mathbb {Z}^2$ are virtually abelian and hence have decidable rational subset membership problem [15]. All other surface groups are hyperbolic one-relator groups. If Gromov’s famous Surface Subgroup Conjecture holds for one-relator groups (see, for example, [13]), then any nonvirtually free one-relator group contains a subgroup $\mathcal {S}_g$ for some $g \geq 2$ . Hence, understanding membership problems for surface groups can be seen as a key first step to understanding membership problems in hyperbolic one-relator groups.

It is well-known (see, for example, [56, §4.3.7] or [17]) that the group $\mathcal {N}_3$ contains a finite index copy of every hyperbolic surface group. Consequently, Question 3.11 is equivalent to:

Question 3.12 Is the submonoid/rational subset membership problem decidable in the positive one-relator group $\mathcal {N}_3 = \operatorname {Gp}\big \langle a,b,c\:|\:a^2b^2c^2=1 \big \rangle $ ?

The word $a^2b^2c^2$ has length $6$ . It is easy to see that any one-relator group $G = \operatorname {Gp}\big \langle A\:|\:r=1 \big \rangle $ with $|r| < 6$ is either free or isomorphic to a free product of a free group by a two-generated one-relator group $H = \operatorname {Gp}\big \langle a,b\:|\:r=1 \big \rangle $ with $|r| < 6$ . There are only seven (non-free) isomorphism types of such H – namely, $C_2, C_3, C_4, C_5, \mathcal {N}_2, \mathbb {Z}^2$ , and the torus knot group $\operatorname {Gp}\big \langle a,b\:|\:a^2b^3=1 \big \rangle $ . All such groups have decidable rational subset membership problem (see [47]), and hence, as decidability of the rational subset membership problem is preserved by taking free products, we conclude that any G as above (with $|r| < 6$ ) has decidable rational subset membership problem. Thus, the group $\mathcal {N}_3$ is the smallest (in terms of relator word length) candidate for a one-relator group with undecidable rational subset membership problem.

4 Prefix membership problems

We say that a one-relator group G is quasi-positive if it is given by a presentation of the form $G = \operatorname {Gp}\big \langle A\:|\:uv^{-1}=1 \big \rangle $ , where $u, v \in A^+$ are positive words, and $uv^{-1}$ is a reduced word. As explained in the introduction, and summarized in the diagram of implications in Figure 1, both results of Guba [16] and work of Ivanov, Margolis, and Meakin [22] motivate the study of the prefix membership problem for quasi-positive one-relator groups. The main result of this section is:

Theorem 4.1 There exists a one-relator group $G = \operatorname {Gp}\big \langle A\:|\:uv^{-1}=1 \big \rangle $ , where $u, v \in A^+$ and $uv^{-1}$ is a reduced word, with an undecidable prefix membership problem.

Theorem 4.1 will be proved by encoding the submonoid membership problem for a positive one-relator group into the prefix membership problem for a quasi-positive one-relator group. The encoding uses a general construction that will also be used to establish other undecidability results in this paper (e.g., for inverse monoids), so we will explain it here so that it can be applied in each instance that it is needed.

Construction 4.2 Let G be a positive one-relator group and let Q be a finitely generated submonoid of G. Let $\operatorname {Mon}\big \langle A\:|\:q=1 \big \rangle \cong \operatorname {Gp}\big \langle A\:|\:q=1 \big \rangle $ be a one-relation monoid presentation for the group, which exists by [50] since G is a positive one-relator group, and let a denote the first letter of the word q. Let Q be a finitely generated submonoid of G. Let $X = \{w_1, \ldots , w_k \} \subseteq A^+$ be a set of positive words such that $Q = \operatorname {Mon}\big \langle w_1, \ldots , w_k \big \rangle \leq G$ . Such a set of positive words X exists since every element of G can be expressed by a positive word over A, as this is true in the monoid M. For any $w \in A^+$ , let $\overline {w} \in A^+$ such that $\overline {w} = w^{-1}$ in G (i.e., $w \overline {w} = \overline {w} w = 1$ in G). Let $z_i$ be word obtained from $w_i$ after replacing a with $tx$ for every letter a. Similarly, let $\overline {z_i}$ be the word obtained by replacing a with $tx$ in $\overline {w_i}$ for every occurrence of the letter a. Let r be the word obtained by replacing every occurrence of a with $tx$ in the word q. Let $B = A \setminus \{a\}$ . Then r, $z_i$ , and $\overline {z_i}$ for $1 \leq i \leq k$ are all positive words over $B \cup \{x,t\}$ , and r begins with $tx$ since the first letter of q is a. Write $r \equiv ts$ (i.e., making s the positive word obtained by deleting the first letter of r). In particular, s begins with the letter x.

Using the data above, we define a two-relator group presentation

$$\begin{align*}H_{G,X} = \operatorname{Gp}\big\langle B,x,t\:|\: r = 1, t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1 \big\rangle. \end{align*}$$

For future reference, we also use $M_{G,X}$ to denote the corresponding inverse monoid presentation

$$\begin{align*}M_{G,X} = \operatorname{Inv}\big\langle B,x,t\:|\: r = 1, t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1 \big\rangle. \end{align*}$$

To establish Theorem 4.1, we will first prove a general result which shows how the word problem in any finitely generated submonoid of a positive one-relator group can be encoded in the prefix membership problem in a quasi-positive one-relator group, and then we combine that with the examples from Section 3 to obtain Theorem 4.1. To prove this general result, we will make use of a related general result (Theorem 7.5) about the prefix membership problem for positive two-relator groups that will be proved in Section 7 below as an application of results proved there about the word problem for two-relator inverse monoids.

Theorem 4.3 Let G be a positive one-relator group, and let Q be any finitely generated submonoid of G. Then there exists a quasi-positive one-relator group $G'$ such that the membership problem for Q in G reduces to the prefix membership problem for $G'$ . Furthermore, $G'$ can be chosen such that $G' \cong G \ast \mathbb {Z}$ .

Proof Let

$$\begin{align*}H_{G,X} = \operatorname{Gp}\big\langle B,x,t\:|\: r = 1, t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1 \big\rangle \end{align*}$$

be the positive two-relator group given by Construction 4.2. Set $H = H_{G,X}$ , $Y = B \cup \{x,t\}$ , $u=r$ and $v = t z_1 s t\overline {z_1} s \ldots s t z_k s t\overline {z_k} s$ . It then follows from Theorem 7.5 and its proof that the membership problem for Q in G reduces to the prefix membership problem for H, that the identity map on Y induces an isomorphism $\operatorname {Gp}\big \langle Y\:|\:u=1, v=1 \big \rangle \rightarrow \operatorname {Gp}\big \langle Y\:|\:u=1 \big \rangle $ , and that $H \cong G \ast \mathbb {Z}$ . It follows that the identity map on Y induces an isomorphism

$$\begin{align*}\operatorname{Gp}\big\langle Y\:|\:u=1,v=1 \big\rangle \rightarrow \operatorname{Gp}\big\langle Y\:|\:vuv^{-1}=1 \big\rangle, \end{align*}$$

and this group is isomorphic to $G \ast \mathbb {Z}$ . Now since $v=1$ in this group, the prefix monoids of $\operatorname {Gp}\big \langle Y\:|\:u=1,v=1 \big \rangle $ and $\operatorname {Gp}\big \langle Y\:|\:vuv^{-1}=1 \big \rangle $ are both generated by $\operatorname {Pref}( u ) \cup \operatorname {Pref}( v )$ . Hence, the isomorphism induced by the identity map on Y maps the prefix monoid of $\operatorname {Gp}\big \langle Y\:|\:u=1,v=1 \big \rangle $ bijectively to the prefix monoid of $\operatorname {Gp}\big \langle Y\:|\:vuv^{-1}=1 \big \rangle $ . Therefore, if $\operatorname {Gp}\big \langle Y\:|\:vuv^{-1}=1 \big \rangle $ has decidable prefix membership problem, then so does $\operatorname {Gp}\big \langle Y\:|\:u=1,v=1 \big \rangle $ , which in turn by Theorem 7.5 implies that the membership problem for Q in G is decidable. The result then follows by taking $G'$ to be the one-relator group with generating set Y and defining relator the reduced form of $vuv^{-1}$ .

Applying this general result with our examples from earlier gives:

Proof of Theorem 4.1

By Theorem 3.8, there exists a positive one-relator group G with a fixed finitely generated submonoid Q such that the membership problem for Q in G is undecidable. Hence, by Theorem 4.3, there is a quasi-positive one-relator group $G'$ such that the membership problem for Q in G reduces to the prefix membership problem for $G'$ . Hence, $G'$ is a quasi-positive one-relator group with undecidable prefix membership problem.

5 Membership problems in one-relation monoids

The subgroup membership problem (also called the generalized word problem) is open in general for one-relator groups. The analogous question for monoids asks whether all one-relation monoids have decidable submonoid membership problem. As well as being a natural question, another reason for studying the membership problem in submonoids, and more generally rational subsets, of one-relation monoids comes from the left (resp. right) divisibility problem (i.e. the problem of deciding membership in the principal right (resp. left) ideal generated by a given element). By a classical result of Adian and Oganesian [4, Corollary 3], decidability of the divisibility problems in one-relation monoids $\operatorname {Mon}\big \langle A\:|\:u=v \big \rangle $ implies decidability of the word problem. Clearly, these principal one-sided ideals are rational subsets of the monoid. Furthermore, Guba [16] proved that for one-relation monoids of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ , the decidability of the membership problem in principal right ideals is equivalent to the word problem. This motivates the study of the membership problem for rational subsets of one-relation monoids. As outlined in the introduction above, several examples and families of one-relation monoid have been shown to have decidable rational subset membership problem, and in some sense, most of them do in the way that for a randomly chosen one-relation monoid this problem will be decidable [26]; cf. [45, p. 338] for a discussion.

Since every positive one-relator group admits a one-relation monoid presentation, the main result of §3 (Theorem 3.8) gave as a corollary (Corollary 3.9) the first known examples of one-relation monoids for which the submonoid membership problem is undecidable. Specifically, we have shown that the one-relation monoid

$$\begin{align*}M_{m,n} = \operatorname{Mon}\big\langle a,b\:|\:(b a^n)^m(a^n b)^m = 1 \big\rangle \end{align*}$$

with $m, n \geq 1$ has decidable submonoid membership problem (and rational subset membership problem) if and only if $m=1$ or $n=1$ . These are the first known examples of one-relation monoids with undecidable submonoid membership problem (and undecidable rational subset membership problem). Of course, all of these monoids are in fact groups. Thus arises the question: are there one-relation monoids that are not groups and have undecidable submonoid, or rational subset, membership? More generally, we have the following problem:

Problem: Classify the one-relation monoids $\operatorname {Mon}\big \langle A\:|\:u=v \big \rangle $ with decidable rational subset, or submonoid, membership problem.

Of course, this problem may well be difficult to answer given the fact that the word problem for one-relation monoids remains open but, motivated by the connection with the reduction results by Adian and Oganesian and Guba mentioned above, there is still strong motivation for developing a better understanding of the submonoid and rational subset membership problems in one-relation monoids.

The general study of one-relation monoids $\operatorname {Mon}\big \langle A\:|\:u=v \big \rangle $ typically splits into cases that, roughly speaking, give a measure of how far away the monoid is from being a group. In more detail, the study of one-relation monoids naturally divides into the investigation of so-called special, and more generally subspecial, monoids on the one hand, and those that are not subspecial, on the other. As we will explain in more detail below, associated with any one-relation subspecial monoid is a unique positive one-relator group that arises as a maximal subgroup of the monoid, and the algorithmic properties of the monoid (e.g., the word problem) are typically controlled by properties of this positive one-relator group.

All of the remaining one-relation monoids (i.e., those that are non-subspecial) are far away from being groups in the sense that the only idempotent such a monoid contains is its identity, and the group of units of the monoid is trivial. Recall from above that the word problem for one-relation monoids has been reduced to the problem of solving the word problem for one-relation monoids of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=aVa \big \rangle $ and of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ . All of the monoids in these two families are non-subspecial, and it is natural to ask whether the rational subset membership (or submonoid) problems are decidable in the non-subspecial case, and in particular for monoids in these two classes. It is not difficult to show that the word problem in such monoids, which are left cancellative, reduces to the left divisibility problem (i.e., the problem of deciding membership in the principal right ideals $wA^\ast $ ).

Any principal ideal is clearly a rational subset, so a better understanding of the membership problem in rational subsets of monoids of this form is important for the study of the word problem. We will see below how to construct monoids of both forms $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ and $\operatorname {Mon}\big \langle a,b\:|\:bUa=aVa \big \rangle $ with undecidable rational subset membership problem. Constructing such examples is more difficult than in the subspecial case since the monoids do not embed any subgroups (apart from the trivial group), so the usual approach of embedding the RAAG $A(P_4)$ is not available to us in those cases. This will be discussed in more detail below.

5.1 Special and subspecial monoids

As we have already seen above, the one-relation monoids that are groups all admit presentation of the form $\operatorname {Mon}\big \langle A\:|\:w=1 \big \rangle $ . These are usually called special one-relation monoids in the literature. It follows from results of Adian [2] that the group of units of any special one-relation monoid is a positive one-relator group, and there is an algorithm (called Adian’s overlap algorithm) that computes a presentation for the group of units of the monoid. In more detail, the algorithm computes a factorization $w \equiv u_1 \ldots u_k$ into nonempty words $u_i$ that all represent invertible elements of the monoid, and no proper nonempty prefix of $u_i$ represents an invertible element. The set of factors $\{u_i : 1 \leq i \leq k\}$ is overlap-free, in the sense that no nonempty prefix (resp. suffix) of a word in this set is equal to a nonempty suffix (resp. prefix) of another word in this set. This is called the decomposition of the relator into minimal invertible pieces, and the group of units of the monoid is then isomorphic to $\operatorname {Mon}\big \langle B\:|\:b_{u_1} \ldots b_{u_k} \big \rangle $ , where $B = \{ b_{u_i} : 1 \leq i \leq k \}$ . So the group of units $\operatorname {Mon}\big \langle B\:|\:b_{u_1} \ldots b_{u_k} \big \rangle $ of $M=\operatorname {Mon}\big \langle A\:|\:w=1 \big \rangle $ is a positive one-relator group, and if that group has undecidable submonoid, or rational subset, membership problem, then so does M. This gives the most straightforward way of using our results to construct non-group one-relation monoids with undecidable submonoid membership problem.

Proposition 5.1 Let $m, n \geq 2$ and let A be a finite alphabet and let $\alpha , \beta \in A^+$ such that $\{\alpha ,\beta \}$ is overlap-free. Then the group of units of

$$\begin{align*}N = \operatorname{Mon}\big\langle A\:|\:(\beta \alpha^n)^m(\alpha^n \beta)^m = 1 \big\rangle \end{align*}$$

is isomorphic to $M_{m,n}$ , and hence, N contains a fixed finitely generated submonoid in which membership is undecidable. The monoid N is a group if and only if $|\alpha | = |\beta | = 1$ .

Proof The fact that the group of units of N is $M_{m,n}$ follows by using the fact that $\{\alpha ,\beta \}$ are overlap-free and applying Adian’s overlap algorithm [2]. If $|\alpha | \geq 2$ , then the first letter of $\alpha $ is right-invertible but not left-invertible in N from which it follows that N is not a group; similarly if $|\beta | \geq 2$ .

For example taking $\alpha = xy$ and $\beta = xxyy$ in Proposition 5.1 gives that the following monoid, which is not a group since x is not invertible, has undecidable submonoid membership problem

$$\begin{align*}\operatorname{Mon}\big\langle x, y\:|\:(xxyy (xy)^n)^m((xy)^n xxyy)^m = 1 \big\rangle \end{align*}$$

for $m,n \geq 2$ .

More generally, a one-relation monoid $\operatorname {Mon}\big \langle A\:|\:u=v \big \rangle $ with $|v| \leq |u|$ is called subspecial if $u \in vA^* \cap A^*v$ . The following proposition follows from known results and explains the close connection between these one-relation monoids and the class of positive one-relator groups.

Proposition 5.2 Let M be a subspecial one-relation monoid (i.e., let $M=\operatorname {Mon}\big \langle A\:|\:u=v \big \rangle $ where $|v| \leq |u|$ and $u \in vA^* \cap A^*v$ ).

1. (i) If $v=1$ is the empty word, then M is a special monoid with group of units H isomorphic to a positive one-relator group.

2. (ii) If $v \neq 1$ , then the group of units is trivial, the monoid contains nontrivial idempotents, and there is a fixed positive one-relator group H such that the maximal subgroup (i.e., group $\mathscr {H}$ -class) associated to any nontrivial idempotent is isomorphic to H.

In both cases, there is an algorithm that computes a presentation and a generating set for the positive one-relator group H from the given presentation of M. In particular, if M has decidable submonoid (resp. rational subset) membership problem, then so does the positive one-relator group H.

There is evidence in the literature that the converse of this proposition should be true in the case of rational subset membership; that is, in both cases of Proposition 5.2, we expect that the monoid M will have decidable rational subset membership problem if and only if the positive one-relator group H does. For instance, if the group H is a virtually free group (and hence has decidable rational subset membership problem), then it was proved in [48, 43] that M has decidable rational subset membership problem. In this sense, we expect the problem of classifying subspecial monoids with decidable rational subset membership problem to be equivalent to the problem of classifying the positive one-relator groups with this property.

Given that we now have examples of positive one-relator groups with undecidable submonoid membership problem, Proposition 5.2 gives a recipe for constructing many more subspecial examples, by realizing our examples as the group H in the proposition. Rather than developing that theory in full here, we content ourselves by giving an example from which it should be clear that many other examples could be constructed using the same approach.

Example 5.3 For $m,n \geq 1$ define $T_{m,n}$ to be the monoid

$$\begin{align*}\operatorname{Mon}\big\langle z,t|((ztz^2t)^2(ztz^3t)^2 (ztz^2tztz^3t)^n)^m((ztz^2tztz^3t)^n (ztz^2t)^2(ztz^3t)^2 )^m = zt \big\rangle. \end{align*}$$

If we compress this monoid (in the sense of [30, 29]) with respect to $zt$ , we obtain the monoid

$$\begin{align*}\operatorname{Mon}\big\langle x, y\:|\:(xxyy (xy)^n)^m((xy)^n xxyy)^m = 1 \big\rangle, \end{align*}$$

and from above, the group of units of this monoid is isomorphic to

$$\begin{align*}M_{m,n} = \operatorname{Mon}\big\langle a,b\:|\:(b a^n)^m(a^n b)^m = 1 \big\rangle. \end{align*}$$

It then follows from [30] that $T_{m,n}$ contains non-identity idempotents, and the maximal subgroup of any of these idempotents is isomorphic to the positive one-relator group $M_{m,n}$ . It follows that for all $m, n \geq 2$ , the monoid $T_{m,n}$ embeds the group $A(P_4)$ and hence contains a fixed finite generated submonoid in which membership is undecidable.

5.2 Non-subspecial monoids

As explained in the beginning of this section, all of the remaining one-relation monoids (i.e., those that are non-subspecial) are far away from being groups, containing no nontrivial subgroups. These non-subspecial monoids will be the topic of the remainder of this section, and also the next section where we develop new methods for constructing examples of these forms with undecidable rational subset membership problem. We now turn our attention to the class of monadic one-relation monoids $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ discussed in the introduction to this paper. As explained there, one major motivation for the work done in this paper is the work of Guba [16], which reduces the word problem in these monoids to the membership problem in certain submonoids of particular positive one-relator groups. In the next section, we will give an infinite family of monadic one-relation monoids $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ , each of which has undecidable rational subset membership problem.

In his paper [16], Guba associates with any $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ a positive one-relator group G such that the word problem in $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ reduces to solving the membership problem within a certain submonoid of G. Of course, if G has decidable submonoid membership problem, then $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ will have decidable word problem, so the only cases of interest now are those where the positive one relator group G does not have decidable submonoid membership problem. We now know from the results above that such positive one-relator groups G do exist, so the next step is to seek monoids $\operatorname {Mon}\big \langle a,b\:|\:bUa=a \big \rangle $ such that the associated positive one-relator groups arising from Guba’s theory are isomorphic to the positive groups $G_{m,n}$ that we defined and investigated above. We will now identify one such class of monadic one-relation monoids and give some of their basic properties before going on to study rational subset membership in this class in depth in the next section (§6).

Let $G_{m,n} = \operatorname {Gp}\big \langle x,y\:|\:x^my^nx^my^{-n} \big \rangle $ . By Remark 3.6, the subgroup

$$\begin{align*}H = \operatorname{Gp}\big\langle yx^my^{-1}, y^{2n}, x^m,xy^{2n}x^{-1} \big\rangle \end{align*}$$

is isomorphic to $A(P_4)$ in $G_{m,n}$ .

The substitution $y \mapsto a, x \mapsto ba^n$ defines an isomorphism between $G_{m,n}$ and the group:

$$\begin{align*}M_{m,n} = \operatorname{Mon}\big\langle a, b\:|\:(b a^n)^m(a^n b)^m = 1 \big\rangle. \end{align*}$$

We know from the results in §3 that $M_{m,n}$ is a one-relator group defined by a positive word and with an undecidable submonoid membership problem.

In the new presentation, the subgroup H is given as

$$\begin{align*}H = \operatorname{Gp}\big\langle a(ba^n)^ma^{-1}, a^{2n}, (ba^n)^m, ba^{2n}b^{-1} \big\rangle. \end{align*}$$

Let $W_{m,n} \equiv (b a^n)^m(a^n b)^m$ , and let $Q_{m,n}$ be the longest proper suffix of $W_{m,n}$ (i.e., $W_{m,n} \equiv b Q_{m,n}$ ). Consider the monoid

$$\begin{align*}R_{m,n} = \text{Mon}\langle \, a,\, b \mid a = bQ_{m,n}a \,\rangle. \end{align*}$$

Applying Oganesian’s algorithm (see [16]) to the monoid $R_{m,n}$ , we see that the suffix monoid of $R_{m,n}$ embeds in the one-relator group

$$\begin{align*}G_{m,n} = \text{Gp}\langle \, a,\, b \mid (b a^n)^m(a^n b)^m = 1\,\rangle = M_{m,n}. \end{align*}$$

Indeed, the suffixes of $Q_{m,n}a$ that start with a are left-divisible by a (which is the first suffix), while the suffixes of $Q_{m,n}a$ that start with b, start with $ba$ as well; so, these suffixes are left-divisible by $ba$ (which is the second suffix). Moreover, as $a = bQ_{m,n}a \equiv (ba^n)^m(a^nb)^m$ , a is left-divisible by $ba$ . By Oganesian’s algorithm, this suffices to show that the suffix monoid of $R_{m,n}$ embeds in $G_{m,n}$ .

In the next section, we will prove the undecidability of the rational subset membership problem in the monoid $R_{m,n}$ . Before doing so, we will solve the word problem in $R_{m,n}$ . We will do so by means of a finite complete rewriting system. First, note that the word $bQ_{m,n}a$ has self-overlaps; in fact, all the words of the form $(ba^n)^i ba$ (for $0 \leq i \leq m-1$ ) are both a prefix and a suffix. Thus, while the rewriting system $bQ_{m,n}a \rightarrow a$ defines $R_{m,n}$ , it is not complete. It can, however, be completed to one:

Lemma 5.4 The monoid $R_{m,n}$ admits a finite complete rewriting system S on the alphabet $\{a, b\}$ , and with the following rules:

1. (i) $(ba^n)^m (a^nb)^{m} a \longrightarrow a$ ,

2. (ii) $(ba^n)^m (a^nb)^{m-i} a^n a \longrightarrow (a^nb)^{m-i} a^n (a^n b)^{m} a \: (1 \leq i \leq m)$ .

We will denote rule (i) as $\alpha _0 \to \beta _0$ , and (ii) as $\alpha _i \to \beta _i$ ( $1 \leq i \leq m$ ), respectively. To show that the system S in Lemma 5.4 is complete, it is enough to show that it is Noetherian and locally confluent by Newman’s Lemma (see, for example [18, Lemma 12.15]). Obviously, it is Noetherian, as can be seen by using the shortlex order. We must therefore only show that our system is locally confluent. For this, we use the following lemma:

Lemma 5.5 (Lemma 12.17 in [18])

The system S is locally confluent if and only if for all pairs of rules $(l_1, r_1), (l_2, r_2) \in S$ , the following conditions are satisfied:

1. (i) If $l_1 = us$ and $l_2 = sv$ with $u, s, v \in \{a,b\}^*$ and $s \neq \varepsilon $ , then there exists $w \in \{a,b\}^*$ with $r_1 v \rightarrow ^* w$ , and $u r_2 \rightarrow ^* w$ .

2. (ii) If $l_1 = usv$ and $l_2 = s$ with $u, s, v \in \{a,b\}^*$ and $s \neq \varepsilon $ , then there exists $w \in \{a,b\}^*$ with $r_1 \rightarrow ^* w$ , and $ur_2v \rightarrow ^* w$ .

Proof of Lemma 5.4

Note that the second condition of Lemma 5.5 does not apply to our system, as none of the $\alpha _i$ is a subword of another $\alpha _j$ .

Note also that the first condition of Lemma 5.5 can only be applied for $l_1 = \alpha _0$ and $l_2 = \alpha _i$ for $0 \leq i \leq m$ , because other pairings do not overlap.

For $l_1 = \alpha _0$ and $l_2 = \alpha _i$ , set $s_j = (ba^n)^j ba$ for $0 \leq j \leq m-1$ . We want $\alpha _0 = u_js_j$ and $\alpha _i = s_j v_{i,j}$ , so, $u_j = (ba^n)^m (a^nb)^{m-1-j}a^n$ ; $v_{0,j} = a^{n-1}(ba^n)^{m-1-j}(a^nb)^{m}a$ ; while for all other $i> 0$ , one has $v_{i,j} = a^{n-1}(ba^n)^{m-1-j}(a^nb)^{m-i}a^n a$ .

Now we want to find a word $w_{i,j}$ with $\beta _0 v_{i,j} \rightarrow ^* w_{i,j}$ , and $u_j \beta _i \rightarrow ^* w_{i,j}$ . Recall that $\beta _0 = a$ , and $\beta _i = (a^nb)^{m-i} a^n (a^n b)^{m} a$ . Actually, one can see that $w_{i,j} = \beta _0 v_{i,j} = a v_{i,j}$ ; that is, $w_{i,j} = \beta _0 v_{i,j}$ is reduced with respect to our system, and $u_j \beta _i$ gets reduced to $w_{i,j}$ .

6 Undecidability in monadic one-relation monoids

The goal of this section is to prove the following result, the proof of which will use the results of the previous sections.

Theorem 6.1 For all $m,n \geq 2$ , the monoid

$$\begin{align*}R_{m,n}= \operatorname{Mon}\big\langle a, b\:|\:(b a^n)^m(a^n b)^ma = a \big\rangle \end{align*}$$

contains a fixed rational subset in which membership is undecidable.

Since the first letters of the two sides of the defining relation are distinct, the monoid $R_{m,n}$ is left-cancellative by Adian [1, Theorem 3], so the only idempotent in $R_{m,n}$ is the identity. The group of units in $R_{m,n}$ is trivial since the defining relation is not of the form $w=1$ . Hence, $R_{m,n}$ does not contain any nontrivial groups; in particular, $R_{m,n}$ does not embed $A(P_4)$ . So Theorem 6.1 cannot be proved by embedding $A(P_4)$ , or embedding any other group for that matter. Theorem 6.1 gives the first known examples of non-subspecial one-relation monoids with undecidable rational subset membership problem.

To prove the theorem, we will need to introduce a new approach which involves embedding the trace monoid $T(P_4)$ into $R_{m,n}$ in a certain way. It is not the case that every left-cancellative monoid that embeds $T(P_4)$ has undecidable rational subset membership problem. For example, $T(P_4)$ itself is left-cancellative (it is even group-embeddable) and has decidable rational subset membership problem [11]. So the way in which the trace monoid embeds into $R_{m,n}$ will be vital.

Recall [19, Chapter II] that two elements x, y in a monoid T are said to be $\mathcal {L}$ -related if $Tx = Ty$ . Also note that it is immediate from the definition that $\mathcal {L}$ is a right congruence (i.e. if $x \mathcal {L} y$ , then $xz \mathcal {L} yz$ for any $z \in T$ ). This will be used implicitly throughout our proofs below. We will prove the following general result and then show that the hypotheses are satisfied by the one-relation monoid $R_{m,n}$ above.

Theorem 6.2 Let M be a finitely generated left-cancellative monoid and let $U \subseteq M$ such that $u v \mathcal {L} v$ for all $u, v \in U$ . If $\operatorname {Mon}\big \langle U \big \rangle $ is isomorphic to the trace monoid $T(P_4)$ , then M contains a fixed rational subset in which membership is undecidable.

By the trace semigroup of $P_4$ , we mean the semigroup defined by the semigroup presentation $\operatorname {Sgp}\big \langle a,b,c,d\:|\:ab=ba, bc=cb, cd=dc \big \rangle $ .

Corollary 6.3 If a left-cancellative monoid embeds a copy of the trace semigroup of $P_4$ that is contained in a single $\mathcal {L}$ -class of the monoid, then the monoid contains a fixed rational subset in which membership is undecidable.

In addition to applying to our one-relation monoid example, the general result Theorem 6.2 also has the following application to groups, since in a group, every pair of elements are clearly $\mathcal {L}$ -related.

Corollary 6.4 If G is a finitely generated group which embeds the trace monoid $T(P_4)$ , then G contains a fixed rational subset in which rational subset membership is undecidable.

Given this, a natural question is whether a group can embed $T(P_4)$ but not $A(P_4)$ ; this will be discussed at the end of this section.

Before proving Theorem 6.2, we will show how it can be applied to prove Theorem 6.1. For that, we need the following lemma about the $\mathcal {L}$ -relation in one-relation monoids of the same form as our example.

Lemma 6.5 Let

$$\begin{align*}M = \operatorname{Mon}\big\langle a,b\:|\:ba^{i_1}ba^{i_2} \ldots ba^{i_k} b a =a \big\rangle \end{align*}$$

with $i_j \geq 1$ for all $1 \leq j \leq k $ . Then $w \mathcal {L} a$ in M for every word $w \in \{a,ba\}^+$ .

Proof Set $r \equiv ba^{i_1}ba^{i_2} \ldots ba^{i_k} b a$ . Since r begins and ends with $ba$ , we can write $r \equiv \alpha ba \equiv ba \gamma $ . As $a=r=ba\gamma $ in M and $\gamma $ ends in the letter a, it follows that $a \gamma \mathcal {L} a$ . In M, we have $ a \gamma = \alpha ba \gamma = \alpha a $ ; hence, $\alpha a \mathcal {L} a$ . Since $r \equiv \alpha ba$ and $i_k \geq 1$ , it follows that the last letter of $\alpha $ equals a, so we can write $\alpha \equiv \alpha ' a$ . But now, $\alpha a \mathcal {L} a$ implies $\alpha ' a^2 \mathcal {L} a$ so $\delta \alpha ' a^2 = a$ for some word $\delta $ . It follows that $a^2 \mathcal {L} a$ in M.

Next, observe that $ba \mathcal {L} a$ since $ba$ is a suffix of r, from which it follows that $ba(ba) \mathcal {L} a(ba)$ and also $ba(a) \mathcal {L} a(a)$ . Also $aba \mathcal {L} a$ since $aba$ is a suffix of r. We have shown $aa \mathcal {L} a$ , $a(ba) \mathcal {L} a$ , $(ba)(ba) \mathcal {L} aba \mathcal {L} a$ , and $(ba)a \mathcal {L} aa \mathcal {L} a$ ; that is, all two-factor products of the words $\{a,ba\}$ are $\mathcal {L}$ -related to a. Now the result follows by induction since setting $w_1 \equiv a$ , $w_2 \equiv ba$ , for any product $ w_{i_1} w_{i_2} \ldots w_{i_k} $ with $k \geq 3$ from above, we have $w_{i_1} w_{i_2} \mathcal {L} a$ from which, since $\mathcal {L}$ is a right congruence, it follows that $ w_{i_1} w_{i_2} w_{i_3} \ldots w_{i_k} \mathcal {L} a w_{i_3} \ldots w_{i_k} $ where by induction, $a w_{i_3} \ldots w_{i_k} \equiv w_1 w_{i_3} \ldots w_{i_k} \mathcal {L} a$ .

The key to applying Theorem 6.2 to $R_{m,n}$ is to find an appropriately embedded copy of the trace monoid $T(P_4)$ . This is achieved in the following lemma.

Lemma 6.6 For all $m, n \geq 2$ the submonoid $T_4 = \operatorname {Mon}\big \langle X \big \rangle $ of $R_{m,n}$ generated by

$$\begin{align*}X = \{ a(ba^n)^{m-1} b a^{n-1}, \; a^{2n}, \; (ba^n)^m, \; ba^n a^{2n} (ba^n)^{m-1} \} \end{align*}$$

is isomorphic to the trace monoid $T(P_4)$ .

Proof Set

$$\begin{align*}\alpha =a(ba^n)^{m-1} b a^{n-1}, \; \beta =a^{2n}, \; \gamma =(ba^n)^m, \; \mu =ba^n a^{2n} (ba^n)^{m-1}. \end{align*}$$

Let $H = \operatorname {Gp}\big \langle a(ba^n)^ma^{-1}, a^{2n}, (ba^n)^m, ba^{2n}b^{-1} \big \rangle \leqslant M_{m,n}$ , and denote by $A, B, C, D$ its $4$ generators, in the given order, recalling that $M_{m,n} = \operatorname {Gp}\big \langle a, b\:|\:(b a^n)^m(a^n b)^ma = a \big \rangle $ . In Section 3, Remark 3.6 was applied to show that $H \cong A(P_4)$ with A, B, C, and D corresponding to the vertices in the path $P_4$ in this order. It then follows from a sequence of easy Tietze transformations that $\operatorname {Gp}\big \langle \alpha ,\beta ,\gamma ,\mu \big \rangle \leq M_{m,n}$ is also isomorphic to $A(P_4)$ since $\alpha = a(ba^n)^{m-1} b a^{n-1}$ is equal to A in $M_{m,n}$ , $\beta = B$ , $\gamma = C$ , and

$$\begin{align*}\mu = ba^n a^{2n} (ba^n)^{m-1} = ba^{2n}a^n (ba^n)^{m-1} = ba^{2n}b^{-1}(ba^n)^m = DC \end{align*}$$

is equal to $DC$ in $M_{m,n}$ . Since any trace monoid naturally embeds in its corresponding right-angled Artin group, it follows that $\operatorname {Mon}\big \langle \alpha ,\beta ,\gamma ,\mu \big \rangle \leq M_{m,n}$ is isomorphic to the trace monoid $T(P_4)$ , where $\alpha $ , $\beta $ , $\gamma $ , $\mu $ correspond to the vertices on the path $P_4$ in this order. Let $\phi $ be the homomorphism $\phi : R_{m,n} \rightarrow M_{m,n}$ induced by the identity map on $\{a,b\}$ . Then

$$\begin{align*}\phi(T_4) = \phi(\operatorname{Mon}\big\langle X \big\rangle) = \operatorname{Mon}\big\langle \phi(X) \big\rangle = \operatorname{Mon}\big\langle \alpha,\beta,\gamma,\mu \big\rangle \leq M_{m,n} \end{align*}$$

is isomorphic to the trace monoid $T(P_4)$ , where $T_4 = \operatorname {Mon}\big \langle X \big \rangle = \operatorname {Mon}\big \langle \alpha ,\beta ,\gamma ,\mu \big \rangle \leq R_{m,n}$ . So $\phi $ induces a surjective homomorphism from $T_4$ onto $\phi (T_4) \leq M_{m,n}$ . To show that this defines an isomorphism between $T_4$ and $\phi (T_4)$ , we need to show that $\phi $ is injective on the set $T_4$ which, since $\phi (T_4)$ is isomorphic to $T(P_4)$ , means we need to show that the defining relations of the trace monoid hold between the generators of $T_4$ in the monoid $R_{m,n}$ . Hence, to complete the proof, we just need to show that $\alpha \beta = \beta \alpha $ , $\beta \gamma = \gamma \beta $ and $\gamma \mu = \mu \gamma $ all hold in $R_{m,n}$ .

Using the rewriting rule (ii) for $i = m$ from Lemma 5.4, we obtain

(6) $$ \begin{align} (ba^n)^m a^n a = a^n (a^n b)^{m} a. \end{align} $$

Multiplying Equation (6) by $a^{n-1}$ on the right, we obtain $(ba^n)^m a^{2n} = a^{2n} (ba^n)^{m}$ ; that is, $\gamma \beta = \beta \gamma $ in $R_{m,n}$ . Multiplying Equation (6) by a on the left and $a^{n-2}$ on the right (note that $n \geq 2$ ), and writing $m = (m-1) + 1$ , we obtain

$$\begin{align*}[a(ba^n)^{m-1} ba^{n-1}]a^{2n}= a^{2n} [a(ba^n)^{m} ba^{n-1}], \end{align*}$$

which means that $\alpha \beta = \beta \alpha $ in $R_{m,n}$ . Lastly, note that $\gamma = (ba^n)^m$ commutes with all the words $ba^{n}$ , $a^{2n}$ , and $(ba^n)^{m-1}$ . So we obtain

$$\begin{align*}\mu \gamma = [ba^n a^{2n} (ba^n)^{m-1}] \gamma = \gamma [ba^n a^{2n} (ba^n)^{m-1}] = \gamma \mu, \end{align*}$$

as required.

We are now in a position to prove the main result of this section, which we presented at the very beginning.

Proof of Theorem 6.1

Let $m,n \geq 2$ , and set $R_{m,n}= \operatorname {Mon}\big \langle a, b\:|\:(b a^n)^m(a^n b)^ma = a \big \rangle $ . By Lemma 6.6, the submonoid $T_4 = \operatorname {Mon}\big \langle X \big \rangle $ of $R_{m,n}$ generated by

$$\begin{align*}X = \{ a(ba^n)^{m-1} b a^{n-1}, \; a^{2n}, \; (ba^n)^m, \; ba^n a^{2n} (ba^n)^{m-1} \} \end{align*}$$

is isomorphic to the trace monoid $T(P_4)$ , and since every word in X belongs to $\{a,ba\}^+$ , it follows from Lemma 6.5 that all nonempty products of elements of X are $\mathcal {L}$ -related to each other, since they are all $\mathcal {L}$ -related to a. Since M is left cancellative by Adian [1, Theorem 3], the result now follows by applying Theorem 6.2.

The remainder of this section will be devoted to proving Theorem 6.2 and then discussing some of its other consequences.

First, the following result identifies a sufficient condition for constructing rational subsets of left-cancellative monoids in which membership is undecidable.

Theorem 6.7 Let M be a left-cancellative monoid with a finite generating set A. Suppose that there exist rational languages $L, K, \overline {L} \subseteq A^*$ , a surjective map $\alpha : L \longrightarrow \overline {L}$ with $\alpha (l) = \overline {l}$ , and a fixed word $w \in A^*$ , satisfying the following properties:

1. (i) $\overline {l} l w = w$ in M, for all $l \in L$ , and

2. (ii) it is undecidable whether there exists a pair $(l,k) \in L \times K$ satisfying $lw^i = k$ in M, for a given $i \in \mathbb {N}$ .

Then the rational language $\overline {L}K \subseteq A^*$ defines a fixed rational subset of M in which membership is undecidable.

Proof The language $\overline {L}K \subseteq A^*$ is clearly rational as both $\overline {L}$ and K are.

Let $i \in \mathbb {N}$ . Since M is left cancellative, it follows that for any $(l,k) \in L \times K$ , we have $lw^i = k$ in M if and only if $\overline {l}lw^i = \overline {l}k$ . Applying condition (i) gives $\overline {l}lw^i = \overline {l}lww^{i-1} = w^i$ ; hence, $lw^i = k$ in M if and only if $w^i = \overline {l}k$ .

It follows that for a given $i \in \mathbb {N}$ , there exists $(l,k) \in L \times K$ satisfying $lw^i = k$ if and only if there exists $(l,k) \in L \times K$ satisfying $w^i = \overline {l}k$ which is true if and only if $w^i \in \overline {L} K$ , since $\alpha $ being surjective implies that $\overline {L} = \{\overline {l} : l \in L \}$ . But the former problem is undecidable by assumption (ii), and hence, the latter problem must also be undecidable (i.e., membership in the rational subset $\overline {L}K$ of M is undecidable).

Condition (ii) in the above theorem comes from the following result of Lohrey and Steinberg [33] about the trace monoid $T(P_4)$ .

Lemma 6.8 (Corollary of Proof of Theorem 2 in [33])

Let T be the trace monoid of $P_4$ defined by

$$\begin{align*}T = \operatorname{Mon}\big\langle u_1, u_2, u_3, u_4\:|\: u_1u_2 = u_2u_1, u_2u_3 = u_3u_2, u_3u_4 = u_4u_3 \big\rangle. \end{align*}$$

Then there are two fixed rational subsets $Q, R \subseteq \{u_1, u_2, u_3, u_4\}^*$ , with Q not containing the empty word, such that it is undecidable whether there exists a pair $(x,y) \in Q \times R$ satisfying $x(u_2)^i = y$ in T, for a given $i \in \mathbb {N}$ .

Proof In the paper [33, Proof of Theorem 2], the authors take $\Sigma = \{a,b,c,d\}$ and work in the trace monoid $S = \operatorname {Mon}\big \langle \Sigma \:|\:ab=ba, bc=cb, cd=dc \big \rangle $ . They show that there is a fixed rational language $L \subseteq \Sigma ^*$ and a family of languages $K_{m,n}$ with $m, n \in \mathbb {N}$ such that it is undecidable whether $K_{m,n} \cap L \neq \varnothing $ for given $m, n \in \mathbb {N}$ . For our purposes, the important thing is that $K_{m,n} = b^{2^m3^n} \Omega $ , where $\Omega \subseteq \Sigma ^*$ is a certain fixed rational language with the property that $\Omega $ does not contain the empty word. ² Their argument shows that it is undecidable whether $b^{2^m3^n} \Omega \cap L \neq \varnothing $ for given $m, n \in \mathbb {N}$ . It follows from the defining relations in the trace monoid S that for any two words $u, v \in \Sigma ^*$ , we have $u=v$ in S if and only if $\mathrm {rev}(u) = \mathrm {rev}(v)$ in S where $\mathrm {rev}$ denotes the reverse of a word. Hence, if we set $\Omega ' = \{ \mathrm {rev}(u) : u \in \Omega \}$ and $L' = \{ \mathrm {rev}(l) : l \in L \}$ , then $\Omega '$ and $L'$ are rational subsets of $\Sigma ^*$ , since word reversal clearly preserves the property of being a regular language. Furthermore, $\Omega '$ and $L'$ have the property that it is undecidable whether $\Omega ' b^{2^m3^n} \cap L' \neq \varnothing $ for given $m, n \in \mathbb {N}$ . In particular, this means that there are fixed rational subsets $\Omega ', L' \subseteq \Sigma ^*$ such that it is undecidable whether $\Omega ' b^{i} \cap L' \neq \varnothing $ for given $i \in \mathbb {N}$ . Finally, if we translate this into the notation of the trace monoid as defined in the statement of the lemma by substituting $a \mapsto u_1$ , $b \mapsto u_2$ , $c \mapsto u_3$ , and $d \mapsto u_4$ , we obtain the result, where Q does not contain the empty word since $\Omega $ does not.

We will also need the following lemma about a certain mapping on words that preserves the property of being a regular language.

Lemma 6.9 Let $A = \{a_1, \ldots , a_n \}$ and for every pair $(i,j)$ of natural numbers with $i,j \in \{1, \ldots , n \}$ , choose and fix some $b_{i,j} \in A^*$ . For every word $w = a_{i_1} a_{i_2} \ldots a_{i_{k-1}} a_{i_k}\in A^*$ of length at least two, define

$$\begin{align*}\phi(a_{i_1} a_{i_2} \ldots a_{i_{k-1}} a_{i_k}) = b_{i_{k-1},i_k} b_{i_{k-2},i_{k-1}} \ldots b_{i_2,i_3} b_{i_1,i_2}. \end{align*}$$

If $L \subseteq A^*$ is a regular language, and every word in L has length at least two, then $\phi (L) \subseteq A^*$ is also a regular language.

Proof Let $L \subseteq A^*$ be a regular language, and suppose that every word in L has length at least two. Let $\sigma :A^* \rightarrow A^*$ be the homomorphism defined by $a_i \mapsto a_i^2$ and set $L_1 = \sigma (L)$ . Since the class of regular languages is closed under taking homomorphisms, it follows that $L_1$ is a regular language. Since every word in L has length at least two, it follows that every word in $L_1$ has length at least four. Now let $L_2$ be the language obtained by taking each word from $L_1$ and deleting the first letter and the last letter. Note that every word in $L_2$ has even length and has length at least two. Since the left or right quotient of a regular language is again regular, and deletion of the last resp. first letter is an example of taking a left resp. right quotient of a language by a regular language, it follows that $L_2$ is a regular language. Let $g:L_1 \rightarrow L_2$ be the map that deletes the first and last letter of the input word, and $L_3$ the reversal of the language $L_2$ (i.e., the language obtained by reversing every word).

Now define a new alphabet $C = \{ c_{i,j} : 1 \leq i,j \leq n \}$ and a homomorphism $\theta :C^* \rightarrow A^*$ defined by $c_{i,j} \mapsto a_i a_j$ . Note that the homomorphism $\theta $ is clearly injective with image the set of all word in $A^*$ of even length. Since regularity is preserved under taking inverse images of homomorphisms, it follows that for any regular language $W \subseteq A^*$ , the language $\theta ^{-1}(W) \subseteq C^*$ is regular. Let $\rho :C^* \rightarrow C^*$ be the word reversing map which also preserves regularity.

Now, given any word $w = a_{i_1} a_{i_2} \ldots a_{i_{k-1}} a_{i_k}\in A^*$ of length at least two, we have

$$\begin{align*}g(\sigma(w)) = a_{i_1} a_{i_2} a_{i_2} a_{i_3} a_{i_3} \ldots a_{i_{k-2}} a_{i_{k-2}} a_{i_{k-1}} a_{i_{k-1}} a_{i_k} \end{align*}$$

is a nonempty word of even length and then

$$\begin{align*}(\rho \circ \theta^{-1} \circ g \circ \sigma)(w) = c_{i_{k-1},i_k} c_{i_{k-2},i_{k-1}} \ldots c_{i_2,i_3} c_{i_1,i_2}. \end{align*}$$

Finally, let $\gamma :C^* \rightarrow A^*$ be the homomorphism defined by $c_{i,j} \mapsto b_{i,j}$ , so that

$$\begin{align*}(\gamma \circ \rho \circ \theta^{-1} \circ g \circ \sigma) (a_{i_1} a_{i_2} \ldots a_{i_{k-1}} a_{i_k}) = b_{i_{k-1},i_k} b_{i_{k-2},i_{k-1}} \ldots b_{i_2,i_3} b_{i_1,i_2}. \end{align*}$$

It follows that the mapping $\phi $ in the statement of the lemma satisfies $\phi = \gamma \circ \rho \circ \theta ^{-1} \circ g \circ \sigma $ , and since as explained above, all of the maps in this composition preserve regularity of follows that $\phi (L)$ is a regular language.

We now have everything we need to prove our general theorem.

Proof of Theorem 6.2

Let M be a finitely generated left-cancellative monoid and let $U \subseteq M$ such that $u v \mathcal {L} v$ for all $u, v \in U$ , and $\operatorname {Mon}\big \langle U \big \rangle $ is isomorphic to the trace monoid $T(P_4)$ . Since every generating set of $T(P_4)$ must contain the four standard generators of the monoid that correspond to the four vertices of the path $P_4$ (this follows from the fact that the relations in the presentation of $T(P_4)$ are length preserving so one cannot recover the letters as products of words of greater length), it follows that U contains a subset $Y = \{u_1, u_2, u_3, u_4\}$ corresponding to the standard generators of the trace monoid. Since the rational subsets of a monoid do not depend on the choice of finite generating sets, without loss of generality, we can take the generating set A for M in the statement of the theorem to be a finite generating set for M so that it contains the subset $Y \subseteq A$ . So $Y \subseteq A$ with $Y = \{u_1, u_2, u_3, u_4\}$ , where $T = \operatorname {Mon}\big \langle Y \big \rangle $ is isomorphic to the trace monoid $T(P_4)$ with the generators $u_1, u_2, u_3, u_4$ corresponding to the vertices in the path $P_4$ with $u_i$ adjacent to $u_{i+1}$ for all i, and by the assumptions in the statement of the theorem $u_i u_j \mathcal {L} u_j$ for all $u_i, u_j \in Y$ .

Next, for every pair $i, j \in \{1,2,3,4\}$ , we fix a word $v_{i,j} \in A^*$ such that $v_{i,j}u_iu_j = u_j$ . This is possible since $u_iu_j \mathcal {L} u_j$ . Then for any nonempty word $w = u_{i_1}u_{i_2} \ldots u_{i_n} \in Y^*$ , we define

$$\begin{align*}\overline{w} = v_{i_n,2} v_{i_{n-1},i_{n}} v_{i_{n-2},i_{n-1}} \ldots v_{i_3,i_4} v_{i_2,i_3} v_{i_1,i_2} \end{align*}$$

and observe that

$$\begin{align*}\overline{w} w u_2 = v_{i_n,2} v_{i_{n-1},i_{n}} v_{i_{n-2},i_{n-1}} \ldots v_{i_3,i_4} v_{i_2,i_3} v_{i_1,i_2} u_{i_1} u_{i_2} \ldots u_{i_n} u_2 = v_{i_n,2} u_{i_n} u_2 = u_2 \end{align*}$$

in M.

By Theorem 6.8, there are two fixed rational subsets $Q, R \subseteq Y^*$ , with Q not containing the empty word, such that it is undecidable whether there exists a pair $(x,y) \in Q \times R$ satisfying $x(u_2)^i = y$ in M, for a given $i \in \mathbb {N}$ . Since $Y \subseteq A$ , it follows that $Q, R$ are also rational subsets of $A^*$ satisfying this property.

Set $\overline {Q} = \{ \overline {w} : w \in Q \}$ . We claim that $\overline {Q}$ is a rational subset of $A^*$ . To see this, note that Q is a rational subset of $A^*$ not containing the empty word, from which it follows that $Qu_2$ is a rational subset of $A^*$ in which every word has length at least two. For every word $w = u_{i_1} u_{i_2} \ldots u_{i_{k-1}} u_{i_k}\in A^*$ of length at least two, define

$$\begin{align*}\phi(u_{i_1} u_{i_2} \ldots u_{i_{k-1}} u_{i_k}) = v_{i_{k-1},i_k} v_{i_{k-2},i_{k-1}} \ldots v_{i_2,i_3} v_{i_1,i_2}. \end{align*}$$

Since $Qu_2$ is a rational subset of $A^*$ , it follows from Lemma 6.9 that $\phi (Qu_2)$ is a rational subset of $A^*$ . But $\overline {Q} = \phi (Qu_2)$ , and hence, $\overline {Q}$ is a rational subset of $A^*$ , completing the proof of the claim.

Hence, we have a left-cancellative monoid M with finite generating set A, rational languages $Q, R, \overline {Q} \subseteq A^*$ , a surjective map $\alpha : Q \longrightarrow \overline {Q}$ with $\alpha (x) = \overline {x}$ , and a fixed word $u_2 \in A^*$ , satisfying the following properties:

1. (i) $\overline {x} x u_2 = u_2$ in M, for all $x \in Q$ ,

2. (ii) it is undecidable whether there exists a pair $(x,y) \in Q \times R$ satisfying $x(u_2)^i = y$ in M, for a given $i \in \mathbb {N}$ .

Then by Theorem 6.7, the rational language $\overline {Q}R \subseteq A^*$ defines a fixed rational subset of M in which membership is undecidable.

A natural question is the following:

Question 6.10 If $m=1$ or $n=1$ , then does $R_{m,n}=\operatorname {Mon}\big \langle a, b\:|\:(b a^n)^m(a^n b)^ma = a \big \rangle $ have decidable rational subset membership problem?

We know from above that the group with the same presentation does have decidable rational subset membership problem when $m=1$ or $n=1$ .

Remark 6.11 We have seen that for all $m,n \geq 2$ , the monoid $R_{m,n}$ contains a fixed rational subset in which membership is undecidable. There are easy modifications of this example that can be used to obtain monoids of the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=aVa \big \rangle $ with the same property. One simple way to do this would be to replace a by $aaa$ and b by $bbb$ to obtain the family of monoids

$$\begin{align*}\operatorname{Mon}\big\langle a, b\:|\:[bbb (aaa)^n]^m[(aaa)^n bbb]^m aaa = aaa \big\rangle. \end{align*}$$

It is straightforward to show that the submonoid of this monoid generated by $\{aaa,bbb \}$ is isomorphic to $R_{m,n}$ , and hence, for every $m,n \geq 2$ , this monoid contains a fixed rational subset in which membership is undecidable, and this monoid has the form $\operatorname {Mon}\big \langle a,b\:|\:bUa=aVa \big \rangle $ .

Remark 6.12 In a very similar way to Example 5.3, the monadic examples constructed above can be combined with the theory of compression [30, 29] to obtain many more examples of non-subspecial monoids with undecidable rational subset membership problem. Indeed, it is not difficult to show that one-step compression by an overlap-free word (in the sense of Kobayashi [29]) preserves the property of having decidable rational subset membership problem. So if a monoid compresses in finitely many steps to one of our monadic examples above with undecidable rational subset membership problem, then the original monoid will have the same property. To give an example, for $m,n \geq 1$ , the monoid

$$\begin{align*}T = \operatorname{Mon}\big\langle x, y\:|\:(xyyxy (xyxxy)^n)^m((xyxxy)^n xyyxy)^m xyxxy= xyxxy \big\rangle \end{align*}$$

is sealed by the self-overlap free word $xy$ , and when we perform one-step compression with respect to this, we obtain the monoid

$$\begin{align*}R_{m,n}= \operatorname{Mon}\big\langle a, b\:|\:(b a^n)^m(a^n b)^ma = a \big\rangle. \end{align*}$$

It follows that for $m,n \geq 2$ , the monoid T above contains a fixed rational subset in which membership is undecidable. Clearly, T is not a subspecial monoid. There is evidence that the converse should be true; that is, a compressible one-relation monoid has decidable rational subset membership problem if and only if its full compression does. Combining this with the comments above on subspecial monoids, the authors believe that the problem of classifying one-relation monoids with decidable rational subset membership problem should reduce to solving the problem for positive one-relator groups (for the subspecial case) and solving it for incompressible monoids (in the non-subspecial case).

6.1 An application to the rational subset membership problem in groups

Corollary 6.4 shows that if G is a finitely generated group which embeds the trace monoid $T(P_4)$ , then G contains a fixed rational subset in which rational subset membership is undecidable. Currently, all known examples of one-relator groups with undecidable rational subset membership problem embed $A(P_4)$ . This motivates the following question:

Question 6.13 Is there a one-relator group which embeds the trace monoid $T(P_4)$ but does not embed $A(P_4)$ ?

If such an example exists, it would show that for one-relator groups, embeddability of $A(P_4)$ is sufficient but not necessary for undecidability of the rational subset membership problem.

In the following proposition, we will give an example of a group H with a finite subset X such that $\operatorname {Mon}\big \langle X \big \rangle $ is isomorphic to the trace monoid $T(P_4)$ but $\operatorname {Gp}\big \langle X \big \rangle $ is not isomorphic to $A(P_4)$ . In particular, since H is a group embedding $T(P_4)$ , it follows from Corollary 6.4 that H contains a rational subset in which membership is undecidable. We do not know whether the group H embeds $A(P_4)$ . And the only way we know of proving that H has undecidable rational subset membership problem is by using the fact that it embeds $T(P_4)$ . This shows that Corollary 6.4 can be usefully applied to examples.

Proposition 6.14 Let

$$\begin{align*}H = \operatorname{Gp}\big\langle x,y,z,t\:|\:tx=xt, xz=zx, zy=yz, y^2x = xy \big\rangle, \end{align*}$$

and set $X = \{ t,x,z,xy\}$ . Then

1. (i) $\operatorname {Mon}\big \langle X \big \rangle $ is isomorphic to the trace monoid $T(P_4)$ , while

2. (ii) $\operatorname {Gp}\big \langle X \big \rangle $ is not isomorphic to the right-angled Artin group $A(P_4)$ .

In particular, the group H contains a rational subset in which membership is undecidable.

Proof (i) Let $K = \operatorname {Gp}\big \langle x,y,z\:|\:xz=zx, yz=zy, y^2x = xy \big \rangle $ . Then $T = \operatorname {Mon}\big \langle x,y,z\:|\: xz=zx, yz=zy, y^2x = xy \big \rangle $ naturally embeds in the group K.

To see this, observe that with $K_1 = \operatorname {Gp}\big \langle z\:|\: \big \rangle $ and $K_2 = \operatorname {Gp}\big \langle x,y\:|\:y^2x = xy \big \rangle $ , we have

$$\begin{align*}K = K_1 \times K_2 \cong \mathbb{Z} \times BS(1,2), \end{align*}$$

while setting $T_1 = \operatorname {Mon}\big \langle z\:|\: \big \rangle $ and $T_2 = \operatorname {Mon}\big \langle x,y\:|\:y^2x = xy \big \rangle $ , we have

$$\begin{align*}T = T_1 \times T_2 \cong \mathbb{N}_0 \times \operatorname{Mon}\big\langle x,y\:|\:y^2x = xy \big\rangle. \end{align*}$$

Both $T_1$ and $T_2$ are group embeddable; $T_1$ is free, and $T_2$ is left and right cycle-free, and so is group-embeddable [1, Theorem 5]. Hence, the natural maps $\phi _i: T_i \rightarrow K_i$ for $i=1,2$ define injective homomorphisms. But then it follows that the map $\phi \colon T_1 \times T_2 \rightarrow K_1 \times K_2 $ defined by $(t_1,t_2) \mapsto (\phi _1(t_1), \phi _2(t_2))$ defines an injective homomorphism from T into K. Hence, T is group embeddable, and thus, T embeds naturally into the group with the same presentation; that is, the identity map on $\{x,y,z\}$ defines an injective homomorphism from T into K.

Then $T = \operatorname {Mon}\big \langle x,y,z\:|\:xz=zx, yz=zy, y^2x = xy \big \rangle $ is a finite complete presentation for the monoid T, and if we consider the submonoid of T generated by $\{x, xy, z\}$ , we see that the reduced form of any word in $\{x, xy, z\}^*$ belongs to the set $\{z\}^*\{x,xy\}^*$ since the rewrite rule $y^2x = xy$ can never be applied to a word in $\{x, xy, z\}^*$ . We conclude that the submonoid of T, and hence also of K, generated by $\{x, xy, z\}$ is isomorphic to $\mathbb {N}_0 \times \{c,d\}^*$ ; that is, it is isomorphic to the trace monoid $T(P_3)$ , where the vertices of $P_3$ are $x, z, xy$ in that order (with z being the middle vertex of the path).

Now apply Theorem 6.15 below to the HNN-extension H of K, where

$$\begin{align*}H = \operatorname{Gp}\big\langle x,y,z, t\:|\:xz=zx, zy=yz, y^2x = xy, txt^{-1}=x \big\rangle. \end{align*}$$

From the previous paragraph, the submonoid of K generated by $\{x, z, xy\}$ is isomorphic to the trace monoid $\operatorname {Mon}\big \langle x,b,c\:|\:xb=bx, bc=cb, cd=dc \big \rangle $ .

Then by Theorem 6.15, it follows that the submonoid of H generated by $X = \{ t,x,z,xy\}$ is isomorphic to $\operatorname {Mon}\big \langle t,x,b,c\:|\:tx=xt, xb=bx, bc=cb, cd=dc \big \rangle \cong T(P_4)$ , as required.

(ii) $\operatorname {Gp}\big \langle X \big \rangle \cong H$ which has abelianisation $\mathbb {Z}^3$ and hence cannot be isomorphic to $A(P_4)$ which has abelianisation $\mathbb {Z}^4$ .

The proof of Proposition 6.14 uses the following general result about submonoids of HNN extensions of groups, which is also of independent interest.

Theorem 6.15 Let $G \cong \operatorname {Gp}\big \langle B\:|\:Q \big \rangle $ , let $A \subseteq B$ , fix $a \in A$ , and set

$$\begin{align*}H = \operatorname{Gp}\big\langle B,t\:|\:Q, tat^{-1}=a \big\rangle, \end{align*}$$

which is an HNN-extension of G with respect to the automorphism fixing the cyclic subgroup of G generated by a. Let M be the submonoid $\operatorname {Mon}\big \langle A \big \rangle $ of G generated by A, and let $\operatorname {Mon}\big \langle A\:|\:R \big \rangle $ be a presentation for M with respect to the generating set A. Then

$$\begin{align*}\operatorname{Mon}\big\langle M \cup \{ t \} \big\rangle \cong \operatorname{Mon}\big\langle A,t\:|\:R, at=ta \big\rangle. \end{align*}$$

Before giving the proof, we recall the normal form in HNN-extensions, which is an immediate consequence of Britton’s Lemma (see [34, Ch. IV]):

Lemma 6.16 (cf. Lemma 6.2 in [12])

An equality of two reduced forms

$$\begin{align*}g_0 t^{\varepsilon_1} g_1 t^{\varepsilon_2} \cdots t^{\varepsilon_n} g_n = h_0 t^{\delta_1} h_1 t^{\delta_2} \cdots t^{\delta_m} h_m \end{align*}$$

holds in the $\operatorname {HNN}$ -extension $G*_{t, \Phi : N_1 \rightarrow N_2}$ if and only if $n = m, \varepsilon _i = \delta _i$ for all $1 \leq i \leq n$ , and there exist $1 = \alpha _0, \alpha _1, \ldots , \alpha _n, \alpha _{n+1} = 1 \in N_1 \cup N_2$ such that for all $0 \leq i \leq n$ , we have $\alpha _i \in N_1$ if $\varepsilon _i = -1$ , $\alpha _i \in N_2$ if $\varepsilon _i = 1$ , and

$$\begin{align*}h_i = \alpha_i^{-1} g_i (t^{\varepsilon_{i+1}} \alpha_{i+1}t^{-\varepsilon_{i+1}}). \end{align*}$$

Proof of Theorem 6.15

Set $N = \operatorname {Mon}\big \langle A,t\:|\:R, at=ta \big \rangle $ . There is an obvious morphism $j\colon N \rightarrow H$ , given by $j(a) = a$ for any $a \in A$ , and $j(t) = t$ .

Moreover, the image $j(N)$ in H is equal to $\operatorname {Mon}\big \langle M \cup \{ t \} \big \rangle $ . To prove the result, it is enough to show that j is injective as well. Let

(7) $$ \begin{align} g_0 t g_1 t \cdots t g_n = h_0 t h_1 t \cdots t h_m \end{align} $$

be an equality of elements in $j(N) = \operatorname {Mon}\big \langle M \cup \{ t \} \big \rangle $ , where $M = \operatorname {Mon}\big \langle A \big \rangle $ ; that is, $g_i, h_j \in M$ for all $0 \leq i \leq n$ , and $0 \leq j \leq m$ .

Equality (7) holds in the group H as well, so we can use Lemma 6.16 for $G \cong \operatorname {Gp}\big \langle B\:|\:Q \big \rangle $ , $N_1 = N_2 = \langle a \rangle \cong \mathbb {Z}$ , $H = G*_{t, \Phi : \langle a \rangle \overset {id}{\longrightarrow } \langle a \rangle }$ , and we obtain

$$ \begin{align*} n = m, \text{and there are} 1 = \alpha_0, \alpha_1, \ldots, \alpha_n, \alpha_{n+1} = 1 \in \langle a \rangle \text{with} h_i = \alpha_i^{-1} g_i (t \alpha_{i+1}t^{-1}). \end{align*} $$

Since $t \alpha t^{-1} = \alpha $ for any $\alpha \in \langle a \rangle $ , we obtain $h_i = \alpha _i^{-1} g_i \alpha _{i+1}$ in H.

Claim Let $\alpha _{i+1} = a^s$ for some $0 \leq i \leq n$ . The following equalities hold in N:

$$\begin{align*}\begin{array}{lcll} h_0 t h_1 t \cdots t h_i & = & g_0 t g_1 t \cdots t g_i \alpha_{i+1}, & \text{ if }s \geq 0; \\ h_0 t h_1 t \cdots t h_i \alpha_{i+1}^{-1} & = & g_0 t g_1 t \cdots t g_i, & \text{ if }s < 0. \end{array} \end{align*}$$

Proof of Claim

From the equality $h_i = \alpha _i^{-1} g_i \alpha _{i+1}$ in H, for $i=0$ , one obtains $h_0 = g_0 \alpha _1$ . Multiplying by t on the right and using $\alpha _1 t = t \alpha _1$ (because $\alpha _1 \in \langle a \rangle $ ), we obtain the desired conclusion for $i = 0$ .

Assume the result holds for a given $i < n$ . We want to show that it holds for $i + 1$ as well. Set $\alpha _{i+2} = a^s$ .

1. (1) Assume first that $h_0 t h_1 t \cdots t h_i = g_0 t g_1 t \cdots t g_i \alpha _{i+1}$ in N. Multiplying by $th_{i + 1}$ , and using the commutation $\alpha _{i+1} t = t \alpha _{i+1}$ we obtain

   (8) $$ \begin{align} h_0 t h_1 t \cdots t h_i th_{i + 1} = g_0 t g_1 t \cdots t g_i t \alpha_{i+1} h_{i + 1} \end{align} $$

   1. (a) If $s \geq 0$ , one has $\alpha _{i+1} h_{i+1} = g_{i+1} \alpha _{i+2}$ in N, which substituting in Equation (8), gives the desired conclusion.

   2. (b) If $s < 0$ , one has $\alpha _{i+1} h_{i+1}\alpha _{i+2}^{-1} = g_{i+1}$ in N. Multiplying Equation (8) by $\alpha _{i+2}^{-1}$ on the right and substituting $\alpha _{i+1} h_{i+1}\alpha _{i+2}^{-1}$ by $g_{i+1}$ , we obtain again the desired equality for $i+1$ .

2. (2) Assume now that $h_0 t h_1 t \cdots t h_i \alpha _{i+1}^{-1} = g_0 t g_1 t \cdots t g_i$ in N. Multiplying by $tg_{i + 1}$ , and using the commutation $\alpha _{i+1}^{-1} t = t \alpha _{i+1}^{-1}$ , we obtain

   (9) $$ \begin{align} h_0 t h_1 t \cdots t h_i t \alpha_{i+1}^{-1} g_{i + 1} = g_0 t g_1 t \cdots t g_i t g_{i + 1} \end{align} $$

   1. (a) If $s \geq 0$ , one has $h_{i+1} = \alpha _{i+1}^{-1} g_{i+1} \alpha _{i+2}$ in N. Multiplying Equation (9) by $\alpha _{i+2}$ on the right and substituting $\alpha _{i+1}^{-1} g_{i+1} \alpha _{i+2}$ by $h_{i+1}$ , we obtain again the desired equality for $i+1$ .

   2. (b) If $s < 0$ , one has $h_{i+1}\alpha _{i+2}^{-1} = \alpha _{i+1}^{-1} g_{i+1}$ in N, which substituting in Equation (9), gives the desired conclusion.

This shows the proof of our claim.

Now the proof of the theorem is obtained by taking $i = n$ in our claim.

7 The word problem for positive special inverse monoids

It is an open question whether the word problem is decidable for all one-relation inverse monoids $\operatorname {Inv}\big \langle A\:|\:w=1 \big \rangle $ where w is a reduced word. This problem is important since if the answer is yes, then it would solve positively the longstanding open question of whether all one-relation monoids have decidable word problem. In particular, this question is open in the case when $w \in A^+$ is a positive word. Interesting examples of positive one-relator special inverse monoids with counterintuitive behavior have been studied in the literature (e.g., the O’Hare monoid [39], and subsequent simpler examples [46]). Given that the question for positive one-relator inverse monoids remains open, it is natural to consider what happens in the case of two positive relators. Further motivation for studying positive two relator inverse monoids comes from the fact that for any pair of positive words $u, v \in A^+$ , there is an isomorphism

$$\begin{align*}\operatorname{Inv}\big\langle A\:|\:uv^{-1}=1 \big\rangle \cong \operatorname{Inv}\big\langle A,t\:|\:ut=1, vt=1 \big\rangle \end{align*}$$

which is a positive two-relator inverse monoid, and it follows from [22] that the word problem for one-relation monoids reduces to the word problem for inverse monoids of this form. So the word problem for one-relation monoids reduces to the word problem for positive two-relator inverse monoids of the above form. While that question remains open, in this section, we will show that in general, the word problem for two-relator inverse monoids is not decidable.

Theorem 7.1 There is a positive two-relator inverse monoid $\operatorname {Inv}\big \langle A\:|\:u=1, v=1 \big \rangle $ , where $u, v \in A^+$ , with an undecidable word problem. Furthermore, the example may be chosen to be E-unitary.

Remark 7.2 Given that the word problem for two-relator groups is open, and also for two-relator monoids is open, it is natural to ask whether the groups or monoids defined by the presentations given by Theorem 7.1 have decidable word problem. It is a consequence of the proof of Theorem 7.1 that the corresponding groups are in fact isomorphic to one-relator and hence have decidable word problem by Magnus’ theorem. It is less obvious whether the corresponding two relator special monoids have decidable word problem, but by Makanin [37, 44], they have groups of units that are two-relator groups, and the word problem reduces to that of the group of units. So those monoids are likely to have decidable word problem, else we would have an example of a two-relator group with undecidable word problem (namely, the group of units of the monoid), and the word problem for two-relator groups is a famous open problem; cf. [27, Problem 9.29]

The following standard lemma will be helpful in proving the main result of this section; for a proof see, for example, [14, Corollary 3.2].

Lemma 7.3 Let $M = \operatorname {Inv}\big \langle A\:|\:R \big \rangle $ . If $xaa^{-1}y \in (A \cup A^{-1})^*$ is right-invertible in M, where $a \in A \cup A^{-1}$ and $x, y \in (A \cup A^{-1})^*$ , then $xaa^{-1}y=xy$ in M.

The main result of this section, Theorem 7.1, will follow from the following general result that shows how to encode the submonoid membership problem in any positive one-relator group into a positive two-relator inverse monoid.

Theorem 7.4 Let G be a positive one-relator group, and let Q be any finitely generated submonoid of G. Then there exists a positive two-relator inverse monoid $M=\operatorname {Inv}\big \langle A\:|\:u=1, v=1 \big \rangle $ , with $u, v \in A^+$ , such the membership problem for Q in G reduces to the word problem of M. Furthermore, M can be chosen to be E-unitary and have maximal group image isomorphic to $G \ast \mathbb {Z}$ .

Proof Let M be the inverse monoid defined by the two-relator positive presentation

$$\begin{align*}M = M_{G,X} = \operatorname{Inv}\big\langle B,x,t\:|\: r = 1, t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1 \big\rangle \end{align*}$$

given by Construction 4.2. We claim that if M has decidable word problem, then the membership problem for Q within G is decidable. Furthermore we shall show that M is E-unitary and has maximal group image isomorphic to $G \ast \mathbb {Z}$ .

To establish this, we will perform a series of Tietze transformations on the presentation. This will come in two stages. First, we will apply a set of Tietze transformations to prove that $M \cong T$ where

$$\begin{align*}T = \operatorname{Inv}\big\langle B,x,t\:|\: r= 1, (t z_1 t^{-1}) (t z_1^{-1} t^{-1}) = 1, \ldots, (t z_k t^{-1}) (t z_k^{-1} t^{-1}) = 1 \big\rangle. \end{align*}$$

Since $\operatorname {Mon}\big \langle A\:|\:q=1 \big \rangle $ is a group, it follows that every letter from a is invertible in this monoid. From this, it follows that in the monoid $\operatorname {Mon}\big \langle B,x,t\:|\:r=1 \big \rangle $ , where r is the word defined above obtained from q by replacing a by $tx$ everywhere it appears, the element $tx$ is invertible. Indeed, the map $a \mapsto tx$ and identity on every other letter defines a homomorphism from $\operatorname {Mon}\big \langle A\:|\:q=1 \big \rangle $ to $\operatorname {Mon}\big \langle B,x,t\:|\:r=1 \big \rangle $ which must map units to units, and since a is a unit in the former monoid, $tx$ is a unit in the latter monoid.

Since $tx$ is a unit in $\operatorname {Mon}\big \langle B,x,t\:|\:r=1 \big \rangle $ , it follows that $tx$ is a unit in the inverse monoid M, since M has $r=1$ as a defining relation. The fact that $tx$ is invertible in M implies $(tx)^{-1} = x^{-1} t^{-1}$ is also invertible in the inverse monoid M. The first letter of s is x, so $t z_1 x$ is right-invertible in M since it is a prefix of the second defining relator; hence, the product $t z_1 xx^{-1} t^{-1} $ of two right-invertible elements is right-invertible, and hence, by Lemma 7.3, it is equal in M to $t z_1 t^{-1} $ . We conclude that $t z_1 t^{-1} $ is right-invertible in M.

Now $w_1 \overline {w_1} \kern1.3pt{=}\kern1.3pt \overline {w_1} w_1 \kern1.3pt{=}\kern1.3pt 1$ in $\operatorname {Mon}\big \langle A\:|\:q\kern1.3pt{=}\kern1.3pt1 \big \rangle $ implies $z_1 \overline {z_1} \kern1.3pt{=}\kern1.3pt \overline {z_1} z_1 \kern1.3pt{=}\kern1.3pt 1$ in ${\operatorname {Mon}\big \langle B,x,t\:|\:r\kern1.3pt{=}\kern1.3pt1 \big \rangle }$ since the map between these monoids given by $a \mapsto xt$ , and identity on all other generators, defines a homomorphism with $z_1$ the image of $w_1$ under this homomorphism, and $\overline {z_1}$ is the image of $\overline {w_1}$ . Since $r=1$ in M, it then follows that $z_1 \overline {z_1} = \overline {z_1} z_1 = 1$ in M; hence $z_1^{-1} = \overline {z_1}$ in M. Since $t z_1 t^{-1} $ is right-invertible in M, we have $ t z_1 t^{-1} t z_1^{-1} t^{-1} = 1 $ in M. Then since $z_1^{-1} = \overline {z_1}$ in M, and $r=1$ in M, it follows that $ t z_1 t^{-1} r t \overline {z_1} t^{-1} r = 1 $ in M. Since this word equals $1$ , it is right-invertible, and hence, by Lemma 7.3, it is equal in M to the word obtained by canceling the $t^{-1}$ with the first letters of r. It follows that

$$\begin{align*}t z_1 s t\overline{z_1} s = t z_1 t^{-1} r t \overline{z_1} t^{-1} r = 1 \end{align*}$$

in M. Hence,

$$\begin{align*}t z_2 s t\overline{z_2} s \ldots s t z_k s t\overline{z_k} s = t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1 \end{align*}$$

in M. It follows that $t z_2 x$ is right-invertible since s begins with x, and we can repeat the argument above to deduce that $t z_2 t^{-1} $ is right-invertible in M and

$$\begin{align*}t z_2 s t\overline{z_2} s = t z_2 t^{-1} r t \overline{z_2} t^{-1} r = 1 \end{align*}$$

in M. Repeating this for all j, we can prove that $t z_j t^{-1} $ is right-invertible in M, and we have

$$\begin{align*}t z_j s t\overline{z_j} s = t z_j t^{-1} r t \overline{z_j} t^{-1} r = 1 \end{align*}$$

in M. In particular, since $t z_j t^{-1} $ is right-invertible in M, this means that the defining relations $ (t z_j t^{-1}) (t z_j^{-1} t^{-1}) = 1 $ from the presentation for T all hold in M for $1 \leq j \leq k$ .

Conversely, since $z_j \overline {z_j} = \overline {z_j} z_j = 1$ in $\operatorname {Mon}\big \langle B,x,t\:|\:r=1 \big \rangle $ , and $r=1$ in T, it follows that $z_j^{-1} = \overline {z_j}$ in T for all $1 \leq j \leq k$ . It follows that

$$\begin{align*}(t z_1 t^{-1}) (t\overline{z_1} t^{-1}) \ldots (t z_k t^{-1}) (t\overline{z_k} t^{-1}) = (t z_1 t^{-1}) (tz_1^{-1} t^{-1}) \ldots (t z_k t^{-1}) (tz_k^{-1} t^{-1}) = 1 \end{align*}$$

in T which, since $r=1$ , implies that

$$\begin{align*}(t z_1 t^{-1}) r (t\overline{z_1} t^{-1}) r \ldots r (t z_k t^{-1}) r (t\overline{z_k} t^{-1}) r = 1 \end{align*}$$

holds in T. Since the word equals one and so right is invertible by Lemma 7.3, we can reduce canceling the $t^{-1} t$ in each subword $t^{-1}r$ and deduce that the following relation holds in T:

$$\begin{align*}t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1. \end{align*}$$

We have proved the second defining relator of M holds in T, and the second defining relator of T holds in M. Since the first defining relators are the same, and the generating sets are the same, we conclude that $M \cong T$ . In fact, we have proved that these are equivalent presentations in the sense that the identity map on $B \cup \{x,t\}$ induces an isomorphism between them.

To complete the proof, we now prove a second sequence of Tietze transformations to the presentation for T to obtain a presentation to which the main construction from [14] can then be applied to finish the proof. To do this, we first we add a redundant generator a and relation $a=tx$ to obtain

$$\begin{align*}\operatorname{Inv}\big\langle B,a,x,t\:|\: r= 1, (t z_1 t^{-1}) (t z_1^{-1} t^{-1}) = 1, \; \ldots, \; (t z_k t^{-1}) (t z_k^{-1} t^{-1}) = 1, \; a=tx \big\rangle. \end{align*}$$

Next, in every $z_i$ and in r, we can replace every occurrence of $xt$ by the letter a obtaining, since $A = B \cup \{a\}$ , the presentation

$$\begin{align*}\operatorname{Inv}\big\langle A,x,t\:|\: q= 1, \; (t w_1 t^{-1}) (t w_1^{-1} t^{-1}) = 1, \; \ldots, \; (t w_k t^{-1}) (t w_k^{-1} t^{-1}) = 1, \; a=tx \big\rangle. \end{align*}$$

By assumption, the relations $aa^{-1}=1$ and $a^{-1}a=1$ are both consequences of $q=1$ ; hence, from $a=tx$ , we can deduce that $1 = a^{-1}a = a^{-1}tx$ in this inverse monoid. Hence, we can deduce $x = t^{-1}a$ in this inverse monoid, giving the following presentation:

$$\begin{align*}\big\langle A,x,t \:|\: q= 1, (t w_1 t^{-1}) (t w_1^{-1} t^{-1}) = 1, \ldots, (t w_k t^{-1}) (t w_k^{-1} t^{-1}) = 1,a=tx, x = t^{-1}a \big\rangle. \end{align*}$$

Now the relation $(t w_1 t^{-1}) (t w_1^{-1} t^{-1}) = 1$ implies that $tt^{-1}=1$ in this inverse monoid, and so from $x = t^{-1}a$ , we can deduce the relation $tx = tt^{-1}a = a$ . Since this relation is a consequence of the others, we can now remove it obtaining the presentation

$$\begin{align*}\operatorname{Inv}\big\langle A,x,t\:|\: q= 1, \; (t w_1 t^{-1}) (t w_1^{-1} t^{-1}) = 1, \; \ldots, (t w_k t^{-1}) (t w_k^{-1} t^{-1}) = 1, \; x = t^{-1}a \big\rangle \end{align*}$$

for the same monoid. Now x is a redundant generator which can be removed. This has no impact on the other relations since neither x nor $x^{-1}$ appears in any of those words. Hence, we arrive at the following presentation

$$\begin{align*}\operatorname{Inv}\big\langle A,t\:|\: q= 1, (t w_1 t^{-1}) (t w_1^{-1} t^{-1}) = 1, \ldots, (t w_k t^{-1}) (t w_k^{-1} t^{-1}) = 1 \big\rangle \end{align*}$$

for T. Finally, by assumption, the relations $cc^{-1}=1$ and $c^{-1}c=1$ for $c \in A$ are all consequences of $q=1$ , so we can add them to obtain

$$\begin{align*}&\big\langle A,t \:|\: q= 1, \; cc^{-1}=1, \ c^{-1}c=1 \; (c \in A), (t w_1 t^{-1}) (t w_1^{-1} t^{-1}) = 1, \\&\qquad \ldots, (t w_k t^{-1}) (t w_k^{-1} t^{-1}) = 1 \big\rangle. \end{align*}$$

Now it follows from [14, Theorem 3.8] that $M \cong T$ is an E-unitary inverse monoid, and if $M \cong T$ has decidable word problem, then the membership problem for $Q = \operatorname {Mon}\big \langle w_1, \ldots , w_k \big \rangle \leq G$ within G is decidable. The fact that [14, Theorem 3.8] applies to the presentation above follows from [14, Lemma 3.3] (see line three of the proof of Theorem 3.8 in [14]). The maximal group image of T is isomorphic to

$$\begin{align*}&\big\langle A,t \:|\: q= 1, \; cc^{-1}=1, \ c^{-1}c=1 \; (c \in A), (t w_1 t^{-1}) (t w_1^{-1} t^{-1}) = 1, \\&\qquad\ldots, (t w_k t^{-1}) (t w_k^{-1} t^{-1}) = 1 \big\rangle, \end{align*}$$

which is isomorphic to $\operatorname {Gp}\big \langle A\:|\:q=1 \big \rangle \ast FG(t) \cong G \ast \mathbb {Z}$ , completing the proof of the theorem.

By combining this general theorem with the earlier results from this paper, we can now prove the main result of this section.

Proof of Thoerem 7.1. Let G be a positive one-relator group and let Q be a finitely generated submonoid in which the membership problem is undecidable; such examples exist by Theorem 3.8. Then by Theorem 7.4, there is a E-unitary positive two-relator inverse monoid $M=\operatorname {Inv}\big \langle A\:|\:u=1, v=1 \big \rangle $ , with $u, v \in A^+$ , such that decidability of the word problem for M would imply decidability of the membership problem for Q in G. Hence, M is an E-unitary positive two-relator inverse monoid with undecidable word problem.

As a second application, we now show how Theorem 7.4 can be used to relate the membership problem in positive one-relator groups to the prefix membership problem in positive two-relator groups. It remains an open question whether there is a one-relator group presentation with cyclically reduced relator and undecidable prefix membership problem [7, Question 13.10]. In particular, it is not known whether there are positive one-relator groups with undecidable prefix membership problem. Using Theorem 7.1 and its proof, we will show that if one allows two relators, then examples with positive relators do exist. The following result is also the key ingredient used in the proof of Theorem 4.1 above that shows there are quasi-positive one-relator groups with undecidable prefix membership problem.

Theorem 7.5 Let G be a positive one-relator group, and let Q be any finitely generated submonoid of G. Then there is a positive two-relator group $H=\operatorname {Gp}\big \langle A\:|\:u=1, v=1 \big \rangle $ , where $u, v \in A^+$ , such that the membership problem for Q in G reduces to the prefix membership problem for H. Furthermore, the group H may be chosen such that the identity map on A induces an isomorphism $\operatorname {Gp}\big \langle A\:|\:u=1, v=1 \big \rangle \rightarrow \operatorname {Gp}\big \langle A\:|\:u=1 \big \rangle $ , and such that $H \cong G \ast \mathbb {Z}$ .

Proof Let K be the group defined by the two-relator positive presentation

$$\begin{align*}K = H_{G,X} = \operatorname{Gp}\big\langle B,x,t\:|\: r = 1, t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1 \big\rangle \end{align*}$$

given by Construction 4.2. We claim if the prefix membership problem for the positive two-relator group K is decidable, then the membership problem for Q in G is decidable. To see this, note that it is shown in the proof of Theorem 7.4 that

$$\begin{align*}M = \operatorname{Inv}\big\langle B,x,t\:|\: r = 1, t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1 \big\rangle \end{align*}$$

is E-unitary, and if M has decidable word problem, then the membership problem for Q in G is decidable. It is also shown there that the inverse monoid M has maximal group image isomorphic to $G \ast \mathbb {Z}$ which is a one-relator group and thus has decidable word problem by Magnus’ Theorem. It then follows from [22, Theorem 3.3] that M has decidable word problem. But in Theorem 7.4, it is proved that decidability of the word problem for M implies decidability of the membership problem for Q in G; hence, the membership problem for Q in G is decidable, as claimed.

In the proof of Theorem 7.4, it is shown that the identity map on $B\cup \{x,t\}$ induces an isomorphism between the inverse monoids

$$\begin{align*}M = \operatorname{Inv}\big\langle B,x,t\:|\: r = 1, t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1 \big\rangle \end{align*}$$

and

$$\begin{align*}T = \operatorname{Inv}\big\langle B,x,t\:|\: r= 1, (t z_1 t^{-1}) (t z_1^{-1} t^{-1}) = 1, \ldots, (t z_k t^{-1}) (t z_k^{-1} t^{-1}) = 1 \big\rangle. \end{align*}$$

It follows that the identity map induces an isomorphism between the maximal group images of these inverse monoids

$$\begin{align*}\operatorname{Gp}\big\langle B,x,t\:|\: r = 1, t z_1 s t\overline{z_1} s \ldots s t z_k s t\overline{z_k} s = 1 \big\rangle \rightarrow \operatorname{Gp}\big\langle B,x,t\:|\:r=1 \big\rangle. \end{align*}$$

(In general, if the identity map induces an isomorphism $\operatorname {Inv}\big \langle A\:|\:R \big \rangle \rightarrow \operatorname {Inv}\big \langle A\:|\:S \big \rangle $ , then for any additional set of relations T, the identity map will also induce an isomorphism between $\operatorname {Inv}\big \langle A\:|\:R \cup T \big \rangle \rightarrow \operatorname {Inv}\big \langle A\:|\:S \cup T \big \rangle $ since S and R are consequence of each other, and hence, the same is true of $S \cup T$ and $R \cup T$ . And so in particular, it is true when T is the set of relations $aa^{-1}= 1 = aa^{-1}$ added to get the maximal group image.) Now set $u \equiv r$ and $v \equiv t z_1 s t\overline {z_1} s \ldots s t z_k s t\overline {z_k} s $ and $Y = B \cup \{x,t\}$ . Then the identity map on Y induces isomorphisms

$$\begin{align*}\operatorname{Gp}\big\langle Y\:|\:u=1,v=1 \big\rangle \rightarrow \operatorname{Gp}\big\langle Y\:|\:u=1 \big\rangle. \end{align*}$$

It follows from Theorem 7.4 that the maximal group image of M is isomorphic to $G \ast \mathbb {Z}$ . But the group $\operatorname {Gp}\big \langle Y\:|\:vuv^{-1}=1 \big \rangle $ we have constructed is isomorphic to the maximal group image $\operatorname {Gp}\big \langle Y\:|\:u=1,v=1 \big \rangle $ of M, so this completes the proof of the theorem.

Corollary 7.6 There is a positive two-relator group $\operatorname {Gp}\big \langle A\:|\:u=1, v=1 \big \rangle $ , where $u, v \in A^+$ , with an undecidable prefix membership problem.

Proof This follows from Theorem 7.5 together with Theorem 3.8 that shows there are positive one-relator groups containing finitely generated submonoids in which membership is undecidable.