On the word problem for weakly compressible monoids

Abstract

We study the language-theoretic properties of the word problem, in the sense of Duncan & Gilman, of weakly compressible monoids, as defined by Adian & Oganesian. We show that if C is a reversal-closed super-$\text{AFL}$, as defined by Greibach, then M has word problem in C if and only if its compressed left monoid L(M) has word problem in C. As a special case, we may take C to be the class of context-free or indexed languages. As a corollary, we find many new classes of monoids with decidable rational subset membership problem. Finally, we show that it is decidable whether a one-relation monoid containing a non-trivial idempotent has context-free word problem. This answers a generalization of a question first asked by Zhang in 1992.

Keywords:

• Context-free groups
• monoids
• word problem
• semigroup presentations

2020 Mathematics Subject Classification:

• Primary: 20M05
• Secondary: 20F10
• 20M35
• 68Q45

1 Introduction

The word problem for finitely presented monoids was introduced in 1914 by Thue [39]. Though this problem would eventually turn out to be undecidable in general, via the remarkable work by Markov [31] and Post [38], there are many tractable cases. Particularly the word problem for one-relation monoids has garnered a great deal of attention. Though it remains a tantalizing open problem whether this problem is decidable, much can be said (see especially the recent survey [35]). Thue himself studied this problem, and solved the problem for some cases when the single defining relation is of the form w = 1. Such monoids are known as special one-relation monoids. Adian [1, 2] studied special monoids in-depth, and proved that the word problem is decidable for all special one-relation monoids, via a reduction to the word problem for one-relator groups; this latter problem is decidable by Magnus’ famous theorem [26]. Adian’s student Makanin [28, 29, 33] later extended this to show that the word problem for any special k-relation monoid reduces to the word problem for some k-relator group. The author has recently proved similar language-theoretic reductions for special monoids [36].

The work by Adian on special monoids would later be extended by Adian and his student Oganesian in the joint work [3]. They defined a form of “compression,” which is called weak compression by the author in [35]. A monoid M with defining relations u_i = v_i (for $1\le i\le k$) is called weakly compressible if there is some non-empty word α such that every u_i and v_i begins and ends with α. Associated to any weakly compressible monoid is a “compressed” left monoid L(M), in which the sum of the lengths of the defining relations are shorter than in the original monoid. The main idea is that the word problem for M can be reduced to the word problem for L(M). In particular, by combining this with Adian’s result, this solves the word problem in the class of subspecial one-relation monoids, being the class of monoids which can be compressed to a special one-relation monoid. Subspecial monoids were studied already by Lallement [24], and are (essentially) the one-relation monoids containing a non-trivial idempotent.

Weak compression of subspecial monoids has received some further attention in the past few decades. Zhang [41] extended the above results on the word problem to solve the conjugacy problem in certain subspecial monoids. Kobayashi [22] used compression to prove that all one-relation monoids satisfy the topological finiteness condition $\text{FDT}$, for which the subspecial case was the only outstanding case. Building on this, Gray & Steinberg showed that all one-relation monoids satisfy the homological finiteness property ${\text{FP}}_{\infty }$, at the same time studying the algebraic properties of subspecial monoids [14].

In another direction, a highly successful approach to studying the word problem for groups came through the methods of formal language theory. Such methods were introduced to group theory by An i¯s i¯mov [5], and focus on the language-theoretic properties of the set of all words representing the identity element, calling this set the word problem of the group (its properties are generally independent of the finite generating set chosen). An i¯s i¯mov showed that the word problem of a group is a regular language if and only if the group is finite, and that the class of groups with context-free word problem is closed under free products. A little over ten years later, Muller & Schupp (supplemented by [12]) gave a remarkable algebraic charactersiation, generally referred to as the Muller–Schupp theorem: a finitely generated group has context-free word problem if and only if it is virtually free [32].

The language of words representing the identity element in a monoid is generally not very enlightening (though for special monoids it is [36], as in the case of groups). To remedy this, Duncan & Gilman introduced a new language which encodes equality in a monoid [11]. This set, which is also termed the word problem for the monoid, has many of the attractive properties of the analogous set for groups, such as invariance under generating set chosen. Furthermore, it is easy to show that a monoid has regular word problem if and only if it is finite, mimicking An i¯s i¯mov’s result. The word problem also generally behaves well under taking free products [9, 37]. This notion of the word problem has also been studied in e.g. [17, 18].

This paper seeks to study the language-theoretic properties of Adian & Oganesian’s weak compression. We will paint a fairly complete picture. The main theorem of this article (Theorem 1.1) will involve classes of languages C which are super- $\text{AFL}$s, as introduced by Greibach [15]. Such classes generalize the context-free languages and the indexed languages; roughly speaking, a full $\text{AFL}$ is a super-$\text{AFL}$ if it is closed under “recursion” (see Section 2.2 for details). We will prove the following main theorem:

Theorem 1.1.

Let M be a weakly compressible monoid, and let L(M) be its left monoid. Let C be a reversal-closed super- $\text{AFL}$. Then M has word problem in C if and only if L(M) has word problem in C.

An overview of the article is as follows. In Section 2 we give some notation, useful concepts, and define two language-theoretic operations from [37]. In Section 3, we define weak compression, amalgamating several authors’ definitions and notations. In Section 4, we prove Theorem 1.1. Finally, in Section 5 we give some corollaries of Theorem 1.1, particularly focused on context-free monoids. In particular, we will obtain many monoids for which the rational subset membership problem is decidable (Corollary 5.1); and that it is decidable whether a one-relation monoid containing a non-trivial idempotent has context-free word problem (Theorem 5.4).

This article is a condensed form of Chapter 4 of the author’s PhD thesis [34].

2 Notation and auxiliary results

We assume the reader is familiar with the fundamentals of formal language theory. In particular, a full $\text{AFL}$ (abstract family of languages) is a class of languages closed under homomorphism, inverse homomorphism, intersection with regular languages, union, concatenation, and the Kleene star. For some background on this, and other topics in formal language theory, we refer the reader to standard books on the subject [6, 16, 19]. The paper also assumes familiarity with the basics of the theory of semigroup, monoid, and group presentations, which will be written as $\text{Sgp}〈A|\mathcal{R}〉,\text{Mon}〈A|\mathcal{R}〉$, and $\text{Gp}〈A|\mathcal{R}〉$, respectively. For further background see e.g. [2, 10, 25, 27]. We also refer the reader to [36, 37].

2.1 Monoids, words, rewriting

Let A be a finite alphabet, and let $A^{\ast }$ denote the free monoid on A, with identity element denoted ε or 1, depending on the context. Let A⁺ denote the free semigroup on A, i.e. $A^{+}=A^{\ast }-\left\{\epsilon \right\}$. For $u,v\in A^{\ast }$, by $u\equiv v$ we mean that u and v are the same word. For $w\in A^{\ast }$, we let $\left|w\right|$ denote the length of w, i.e. the number of letters in w. We have $\left|\epsilon \right|=0$. If $w\equiv a_1{a}_2\cdots a_n$ for $a_i\in A$, then we let $w^{\text{rev}}$ denote the reverse of w, i.e. the word $a_n{a}_{n-1}\cdots a_1$. For a language L, we define $L^{\text{rev}}$ as the collection of all words $w^{\text{rev}}$ where $w\in L$. We say that a class of languages C is reversal-closed if for every $L\in \mathbf{C}$, we have $L^{\text{rev}}\in \mathbf{C}$. We say that the word $w\in A^{\ast }$ is self-overlap free if it is empty, or else if it is non-empty and none of the proper non-empty prefixes of w is also a proper non-empty suffix of w. Thus xyxyy is self-overlap free, but xyxyx is not. If the words $u,v\in A^{\ast }$ are equal in the monoid $M=\text{Mon}〈A|\mathcal{R}〉$, then we denote this $u{=}_{M}v$. Finally, when we say that a monoid M is generated by a finite set A, we mean that there exists a surjective homomorphism $\pi :A^{\ast }\to M$. In this case, $u{=}_{M}v$ will be used synonymously with $\pi (u)=\pi (v)$.

We give some notation for rewriting systems. For an in-depth treatment and further explanations of the terminology, see e.g. [8, 21]. A rewriting system $\mathcal{R}$ on A is a subset of $A^{\ast }\times A^{\ast }$. An element of $\mathcal{R}$ is called a rule. The system $\mathcal{R}$ induces several relations on $A^{\ast }$. We will write $u{\stackrel{}{\to }}_{\mathcal{R}}v$ if there exist $x,y\in A^{\ast }$ and a rule $(\mathcal{l},r)\in \mathcal{R}$ such that $u\equiv x\mathcal{l}y$ and $v\equiv \mathit{xry}$. We let ${\stackrel{}{\to }}_{\mathcal{R}}^{\ast }$ denote the reflexive and transitive closure of ${\stackrel{}{\to }}_{\mathcal{R}}$. We denote by ${\stackrel{*}{\leftrightarrow }}_{\mathcal{R}}$ the symmetric, reflexive, and transitive closure of ${\stackrel{}{\to }}_{\mathcal{R}}$. The relation ${\stackrel{*}{\leftrightarrow }}_{\mathcal{R}}$ defines the least congruence on $A^{\ast }$ containing $\mathcal{R}$. For $X\subseteq A^{\ast }$, we let ${〈X〉}_{\mathcal{R}}$ denote the set of ancestors of X, i.e. ${〈X〉}_{\mathcal{R}}=\{w\in A^{\ast }|\exists x\in X\text{ such that }w{\stackrel{}{\to }}_{\mathcal{R}}^{\ast }x\}$. The monoid $\text{Mon}〈A|\mathcal{R}〉$ is identified with the quotient $A^{\ast }/{\stackrel{*}{\leftrightarrow }}_{\mathcal{R}}$. For a rewriting system $\mathcal{T}\subseteq A^{\ast }\times A^{\ast }$ and a monoid $M=\text{Mon}〈A|\mathcal{R}〉$, we say that $\mathcal{T}$ is M-invariant if for every rule $(u,v)\in \mathcal{T}$, we have $u{=}_{M}v$. That is, $\mathcal{T}$ is M-invariant if and only if ${\stackrel{*}{\leftrightarrow }}_{\mathcal{T}}\subseteq {\stackrel{*}{\leftrightarrow }}_{\mathcal{R}}$.

A rewriting system $\mathcal{R}\subseteq A^{\ast }\times A^{\ast }$ is said to be monadic if $(u,v)\in \mathcal{R}$ implies $\left|u\right|\ge \left|v\right|$ and $v\in A\cup \left\{\epsilon \right\}$. We say that $\mathcal{R}$ is special if $(u,v)\in \mathcal{R}$ implies $v\equiv \epsilon$. Every special system is monadic. Let C be a class of languages. A monadic rewriting system $\mathcal{R}$ is said to be C if for every $a\in A\cup \left\{\epsilon \right\}$, the language $\left\{u\right|(u,a)\in \mathcal{R}\}$ is in C. Thus, we may speak of e.g. monadic C-rewriting systems or monadic context-free rewriting systems.

Let M be a monoid with a finite generating set A. One way of encoding the structure of M as a language is by using the identity problem of M (with respect to A), defined as(2.1) $${\text{IP}}_A^M=\{w\in A^{\ast }|w{=}_{M}1\}.$$(2.1)

When M is a group, this is the standard definition of the language-theoretic word problem, appearing e.g. in Muller & Schupp [32] and Anisimov [5]. However, for general monoids, (2.1) is generally not very useful. Instead, the central definition of this article will be the following. The (monoid) word problem of M (with respect to A) is defined as the language(2.2) $${\text{WP}}_A^M:=\{u\#v^{\text{rev}}|u,v\in A^{\ast },u{=}_{M}v\},$$(2.2) where $\#$ is some fixed symbol not in A. For a class of languages C, we say that M has C-word problem if ${\text{WP}}_A^M$ is in C. If C is closed under inverse homomorphism, then M having C-word problem does not depend on the finite generating set A chosen for M (see e.g. [17]). The above definition (2.2) is due to Duncan and Gilman [11, p. 522]. We will throughout this article use $A_{\#}$ as a short-hand for the set $A\cup \{\#\}$.

2.2 Super-$\text{AFL}$ s

The theorems in this paper involve a special type of classes of languages, called super- $\text{AFL}$s. These were introduced by Greibach [15], using nested iterated substitutions. In [37], the author gave an equivalent characterization of super-$\text{AFL}$ s, which we shall use here. We begin with a simple definition. Recall that for a language L and a rewriting system $\mathcal{R}$, the language ${〈L〉}_{\mathcal{R}}$ denotes the language of ancestors of L under $\mathcal{R}$, i.e. the set of words which can be rewritten to some word in L.

Definition 1.

Let C be a class of languages. Let $\mathcal{R}\subseteq A^{\ast }\times A^{\ast }$ be a rewriting system. Then we say that $\mathcal{R}$ is C-ancestry preserving if for every $L\subseteq A^{\ast }$ with $L\in \mathbf{C}$, we have ${〈L〉}_{\mathcal{R}}\in \mathbf{C}$. If every monadic C-rewriting system is C-ancestry preserving, then we say that C has the monadic ancestor property.

Example 1.

If $\mathcal{R}\subseteq A^{\ast }\times A^{\ast }$ is a monadic context-free rewriting system, and $L\subseteq A^{\ast }$ is a context-free language, then ${〈L〉}_{\mathcal{R}}$ is a context-free language [7, Theorem 2.2]. That is, if we let CF denote the class of context-free languages, then every monadic CF-rewriting system is CF-ancestry preserving; in other words, the class of context-free languages has the monadic ancestor property.

Definition 2.

Let C be a full $\text{AFL}$. Then C is said to be a super- $\text{AFL}$ if C has the monadic ancestor property.

For example, the class CF of context-free languages forms a super-$\text{AFL}$ by [23, Theorem 1.2], and the class IND of indexed languages is also a super-$\text{AFL}$ [4, 13]. Both are closed under reversal. On the other hand, neither the classes REG nor DCF of regular, resp. deterministic context-free, languages are super-$\text{AFL}$ s. Indeed, if C is a super-$\text{AFL}$, then $\mathbf{CF}\subseteq \mathbf{C}$, by [15, Theorem 2.2]. For more examples and generalizations, we refer the reader to the so-called hyper- $\text{AFL}$s defined by Engelfriet [13], all of which are super-$\text{AFL}$ s.

We remark that Greibach [15] originally defines super-$\text{AFL}$s via “nested iterated substitutions”, which behave similarly to taking ancestors under monadic rewriting systems. The author [37, Proposition 2.2] has proved that the above definition, using rewriting systems, is equivalent to Greibach’s, and so we will use her results about super-$\text{AFL}$s without restriction.

2.3 Alternating products and bipartisan ancestry

With general definitions taken care of, we will now turn to give some useful auxiliary language-theoretic results.

We first define an operation (the alternating product) on certain languages, which mimics the operation of the free product of semigroups. This operation appears in [37]. Fix an alphabet A and let $\#$ be a symbol not in A. Let $L\subseteq A^{\ast }\#A^{\ast }$ be any language. We say that L is concatenation-closed (with respect to $\#$) if(2.3) $$u_1\#v_1\in L\text{ and }{u}_2\#v_2\in L\Rightarrow u_1{u}_2\#v_2{v}_1\in L,$$(2.3) where $u_1,v_1,u_2,v_2\in A^{\ast }$. The word problem of any finitely generated monoid is always a concatenation-closed language.

Let $X:\mathbb{N}\to \{1,2\}$ be a parametrisation such that either $X(2j)=1$ and $X(2j+1)=2$, or else $X(2j)=2$ and $X(2j+1)=1$, for all $j\in \mathbb{N}$. A parametrisation X of this form will be called standard. Given two concatenation-closed languages in $A^{\ast }\#A^{\ast }$, we now present an operation for combining them. Let $L_1,L_2\subseteq A^{\ast }\#A^{\ast }$ be concatenation-closed. Then the alternating product $L_1\star L_2$ of L₁ and L₂ is defined as the language consisting of all words of the form:(2.4) $$u_1{u}_2\cdots u_k\#v_k\cdots v_2{v}_1,$$(2.4) where for all $1\le i\le k$ we have $u_i\#v_i\in L_{X(i)}$, where X is a standard parametrisation. In particular, $\#\in L_1\star L_2$ if and only if $\#\in L_1$ or $\#\in L_2$. Alternating products are modeled on the (semigroup) free product, as the following example shows.

Example 2.

Let $L_1=\{a^n\#a^n|n\ge 0\}$ and $L_2=\{b^n\#b^n|n\ge 0\}$. Then, of course, $L_1={\text{WP}}_{\left\{a\right\}}^{{\left\{a\right\}}^{\ast }}$ and $L_2={\text{WP}}_{\left\{b\right\}}^{{\left\{b\right\}}^{\ast }}$. Now both languages L₁ and L₂ are concatenation-closed, and it is easy to see that we have$$L_1\star L_2=\{a^{n_1}{b}^{n_2}\cdots a^{n_k}\#a^{n_k}\cdots b^{n_2}{a}^{n_1}|k\ge 0;n_1,n_2,\dots ,n_{k-1}\ge 1;n_k\ge 0\}.$$

Thus $L_1\star L_2=\{w\#w^{\text{rev}}|w\in {\{a,b\}}^{\ast }\}={\text{WP}}_{\{a,b\}}^{{\{a,b\}}^{\ast }}$.

Using the monadic ancestor property, one can prove the following useful statement.

Proposition 2.1.

[37, Proposition 2.3] Let C be a super- $\text{AFL}$. Let $L_1,L_2\subseteq A^{\ast }\#A^{\ast }$ be concatenation-closed languages. Then $L_1,L_2\in \mathbf{C}\Rightarrow L_1\star L_2\in \mathbf{C}$.

We will require another operation with useful preservation properties, also introduced in [37]. Let ${\mathcal{R}}_1,{\mathcal{R}}_2\subseteq A^{\ast }\times A^{\ast }$ be two rewriting systems. Let $L\subseteq A^{\ast }\#A^{\ast }$. Then we define the bipartisan $({\mathcal{R}}_1,{\mathcal{R}}_2)$-ancestor of L as the language(2.5) $${}^{{\mathcal{R}}_1}{L}^{{\mathcal{R}}_2}=\{w_1\#w_2|\exists u_1\#u_2\in L\text{ such that }{w}_i\in {〈u_i〉}_{{\mathcal{R}}_i}\text{ for }i=1,2\}.$$(2.5)

Bipartisan ancestors can, informally speaking, manipulate the left and the right side (of $\#$ in words in L) using ${\mathcal{R}}_1$ resp. ${\mathcal{R}}_2$, and these manipulations can be independent of one another. We give an example of this independence.

Example 3.

Let $A=\{a,b\}$, and let $L=\{a\#a\}$. Let ${\mathcal{R}}_1$ be the rewriting system with the rules $(b^n,a)$ for all $n\ge 1$. Then$${}^{{\mathcal{R}}_1}{L}^{{\mathcal{R}}_1}=\{b^{n_1}\#b^{n_2}|n_1,n_2\ge 1\}\cup \{b^n\#a|n\ge 1\}\cup \{a\#b^n|n\ge 1\}\cup \{a\#a\}.$$

In particular, we have $b^{n_1}\#b^{n_2}{\in }^{{\mathcal{R}}_1}{L}^{{\mathcal{R}}_1}$ even if $n_1\ne n_2$.

Proposition 2.2.

[37, Proposition 2.5] Let C be a class of languages closed under rational transductions. Let $L\subseteq A^{\ast }\#A^{\ast }$, and let ${\mathcal{R}}_1,{\mathcal{R}}_2\subseteq A^{\ast }\times A^{\ast }$ be rewriting systems. If ${\mathcal{R}}_1,{\mathcal{R}}_2$ are C-ancestry preserving, then $L\in \mathbf{C}{\Rightarrow }^{{\mathcal{R}}_1}{L}^{{\mathcal{R}}_2}\in \mathbf{C}$.

Bipartisan ancestors are useful in describing the language theory of monoid (and group) free products. See [37] for further details. Alternating products and bipartisan ancestors are the language-theoretic tools we shall require for this article. We now turn to the main subject of the article.

3 Weak compression

We present weak compression as it is defined in the survey [35, Section 3.1] by the author. This is an amalgamation of other approaches [3, 14, 22, 24, 41].

Let A be an alphabet. We say that a pair (u, v) of words is sealed by $w\in A^{+}$ if $u,v\in w{A}^{\ast }\cap A^{\ast }w$. If a pair is sealed by some word, then it is clearly sealed by a unique self-overlap free word α. For example, (xyxpxyx, xyxqxyx) is sealed by xyx, but also by the self-overlap free word x.

Let M be the monoid defined by the presentation(3.1) $$\text{Mon}〈A|u_i=v_i(1\le i\le p)〉.$$(3.1)

Definition 3.

We say that the monoid defined by (3.1) is weakly compressible (with respect to α) if there is some self-overlap free word $\alpha \in A^{+}$ such that for all $1\le i\le p$, the pair (u_i , v_i ) is sealed by α.

If M is not weakly compressible, then we say that M is incompressible. Any special monoid is incompressible by default (in particular groups are incompressible).

Let M be a weakly compressible monoid defined by (3.1). We will assume $\left|A\right|>1$, for otherwise M is a finite cyclic monoid, and all is trivial. A word $w\in A^{\ast }$ is called a left α-conjugator if $w\in \alpha A^{\ast }$. Let ${\Sigma }_{\ast }(\alpha )$ be the set of left α-conjugators which contain exactly one occurrence of α, i.e. ${\Sigma }_{\ast }(\alpha )=\alpha (A^{\ast }-A^{\ast }\alpha A^{\ast })$. For ease of notation, we write ${\Sigma }_{\ast }$ instead of ${\Sigma }_{\ast }(\alpha )$. Clearly, ${\Sigma }_{\ast }$ is a countably infinite suffix code (as $\left|A\right|>1$), and ${\Sigma }_{\ast }^{+}$ is the set of all left α-conjugators. Enumerate the words of ${\Sigma }_{\ast }$ as $\{w_1,w_2,\dots \}$ and fix a set ${\Gamma }_{\ast }(\alpha )={\Gamma }_{\ast }$ of symbols $\{{\gamma }_{w_1},{\gamma }_{w_2},\dots \}$ in bijective correspondence with ${\Sigma }_{\ast }$ via the map $\phi :w_i\mapsto {\gamma }_{w_i}$. As ${\Sigma }_{\ast }$ is a suffix code, we can extend $\phi$ to an isomorphism of the free monoids ${\Sigma }_{\ast }^{\ast }$ and ${\Gamma }_{\ast }^{\ast }$.

Every defining relation u_i = v_i in (3.1) is sealed by α, and as α is self-overlap free, we have $u_i,v_i\in {\Sigma }_{\ast }^{\ast }\alpha$. We factor u_i , v_i uniquely over the suffix code ${\Sigma }_{\ast }$, yielding(3.2) $$u_i\equiv u_{i,1}{u}_{i,2}\cdots u_{i,m_i}\alpha ,\hspace{1em}\text{and}\hspace{1em}{v}_i\equiv v_{i,1}{v}_{i,2}\cdots v_{i,n_i}\alpha .$$(3.2)

Any word $u_{i,j}$ or $v_{i,k}$ appearing in the factorizations (3.2) for some $1\le i\le p$ is called a left piece of M. The set of all left pieces of M is denoted $\Sigma (\alpha )$, which will be shortened to Σ. As M is finitely presented, Σ is a finite set of words. We let $\Gamma =\Gamma (\alpha )$ be the set $\phi (\Sigma )$ of symbols from ${\Gamma }_{\ast }$.

From the factorization (3.2), we define a new presentation(3.3) $$\text{Mon}〈{\Gamma }_{\ast }|\phi (u_{i,1}{u}_{i,2}\cdots u_{i,m_i})=\phi (v_{i,1}{v}_{i,2}\cdots v_{i,n_i})(1\le i\le p)〉.$$(3.3)

Definition 4.

The monoid defined by the presentation (3.3) is called the extended left monoid associated to the monoid M (defined by (3.1)), and is denoted $L_{\ast }(M)$. The submonoid of $L_{\ast }(M)$ generated by Γ is the left monoid associated to M, and is denoted L(M).

It is obvious from (3.3) that $L_{\ast }(M)=\mathcal{F}\ast L(M)$, where * denotes the monoid free product, and $\mathcal{F}$ is a free monoid of countably infinite rank, freely generated by ${\Gamma }_{\ast }-\Gamma$. We emphasize that it is always decidable to compute the presentation (3.3) starting from the weakly compressible (3.1), as it only requires computing with regular languages. Of course, L(M) is finitely presented, with the same defining relations as in (3.3). Furthermore, the sum of the lengths of the defining relations in L(M) is strictly shorter than the corresponding sum for M. In particular, setting $L^1(M)=L(M)$ and $L^i(M)=L(L^{i-1}(M))$ for i > 1, there exists some $n\ge 1$ such that $L^n(M)$ is incompressible.¹

We give an example. One can easily verify that if(3.4) $$M_1=\text{Mon}〈x,y|\mathit{xyyxxxyxxyyxxxy}=xy〉,$$(3.4) then the defining relation of M₁ is sealed by xy. Factorizing both sides of the defining relation, we find $\Sigma =\{\mathit{xyx},\mathit{xyyxx}\}$ and hence $\Gamma =\{{\gamma }_{\mathit{xyx}},{\gamma }_{\mathit{xyyxx}}\}$. Thus(3.5) $$L(M_1)=\text{Mon}〈{\gamma }_{\mathit{xyx}},{\gamma }_{\mathit{xyyxx}}|{\gamma }_{\mathit{xyyxx}}{\gamma }_{\mathit{xyx}}{\gamma }_{\mathit{xyyxx}}=1〉.$$(3.5)

This (special) monoid is incompressible. It is isomorphic to $\text{Mon}〈a,b|\mathit{aba}=1〉$, which is isomorphic to the infinite cyclic group $\mathbb{Z}$ by removing the redundant generator b.

We return to the general case, and present the normal form results from [3, 24]. First, note that it is obvious that if two words $u,v\in A^{\ast }$ are equal in M, then u contains an occurrence of the self-overlap free word α if and only if v does; and furthermore, if neither u nor v contain α, then $u{=}_{M}v$ if and only if $u\equiv v$. Second, given any $u\in A^{\ast }\alpha A^{\ast }$, there exist unique $u\prime ,u″\in A^{\ast }-A^{\ast }\alpha A^{\ast }$ and $u^{†}\in \alpha A^{\ast }\cap A^{\ast }\alpha$ such that $u\equiv u\prime u^{†}u″$. We call such a factorization the canonical form of u, and $u^{†}$ is called the α-part of u. Write $u^{†}\equiv u_{\mathcal{l}}^{†}\alpha$, where $u_{\mathcal{l}}^{†}\in {\Sigma }_{\ast }^{\ast }$. The word $\phi (u_{\mathcal{l}}^{†})$ is called the γ-part of u. The following theorem is fundamental to weakly compressible monoids.

Theorem 3.1

(Adian & Oganesian, Lallement). Let M be a weakly compressible monoid defined by (3.1). Let $u,v\in A^{\ast }\alpha A^{\ast }$ have canonical forms $u\prime u^{†}u″$ and $v\prime v^{†}v″$, respectively. Let ${\gamma }_u,{\gamma }_v$ be the γ-parts of u and v, respectively. Then $u{=}_{M}v$ if and only if (1) $u\prime \equiv v\prime$ and $u″\equiv v″$; and (2) ${\gamma }_u={\gamma }_v$ in $L_{\ast }(M)$. Furthermore, (2) is equivalent to (2’) $u^{†}{=}_M{v}^{†}$.

Remark 1.

The above result appears as [24, Lemma 3.2] and [3, Theorem 3.2] only in the case of one defining relation. However, the proofs of these results use no properties of one-relation monoids, and can, mutatis mutandis, also be used to prove the above result.

In particular, the word problem for M is decidable if and only if the word problem for L(M) is decidable. Furthermore, one can without much difficulty show that the left (right) divisibility problem for M reduces to the word and left (right) divisibility problems in L(M). In particular this solves the word and divisibility problems in the monoid M₁ defined by (3.4).

4 Proof of Theorem 1.1

Let M be a weakly compressible (with respect to some self-overlap free word α) monoid defined by (3.1), and let $\phi ,{\Sigma }_{\ast },{\Gamma }_{\ast },\Sigma$, and Γ be as in Section 3. We will now prove that the language-theoretic properties of the monoid M defined by (3.1) can be reduced to the properties of the left monoid L(M). Let C be a reversal-closed super-$\text{AFL}$, which will remain fixed throughout this section.

To simplify some technical notation we shall sometimes consider Σ, rather than Γ, as a finite generating set for the monoid L(M), as there exists a surjective homomorphism ${\pi }_{\Sigma }$ from ${\Sigma }^{\ast }$ onto L(M) given by the composition ${\pi }_{\Sigma }={\pi }_{\Gamma }°\phi$, where ${\pi }_{\Gamma }:{\Gamma }^{\ast }\to L(M)$ is the natural surjective homomorphism. However, it is important to notice that if $u,v\in {\Sigma }^{\ast }$, then generally ${\pi }_{\Sigma }(u)={\pi }_{\Sigma }(v)$ is very distinct from $u{=}_{M}v$, unlike what Theorem 3.1 may seem to suggest. Instead, using the canonical forms we find that we have(4.1) $${\pi }_{\Sigma }(u)={\pi }_{\Sigma }(v)\hspace{1em}\iff \hspace{1em}u\alpha {=}_{M}v\alpha .$$(4.1)

By the first remark preceding Theorem 3.1, it follows that the language ${\text{WP}}_A^M$ is a union $\text{WP}{[\alpha ]}_A^M\cup {\mathrm{W}}_{\alpha }^{-}$ of the two disjoint languages(4.2) $$\text{WP}{\left[\alpha \right]}_A^M=\{w_1\#w_2^{\text{rev}}|w_1,w_2\in A^{\ast }\alpha A^{\ast }\text{ such that }{w}_1{=}_M{w}_2\},$$(4.2) (4.3) $${\mathrm{W}}_{\alpha }^{-}=\{w\#w^{\text{rev}}|w\in A^{\ast }-A^{\ast }\alpha A^{\ast }\}.$$(4.3)

The language ${\mathrm{W}}_{\alpha }^{-}$ defined by (4.3) is the intersection of the context-free language ${\text{WP}}_A^{A^{\ast }}$ with the regular language $(A^{\ast }-A^{\ast }\alpha A^{\ast })\#{(A^{\ast }-A^{\ast }\alpha A^{\ast })}^{\text{rev}}$. In particular, ${\mathrm{W}}_{\alpha }^{-}$ is a context-free language. Any super-$\text{AFL}$ contains the class of context-free languages [15, Theorem 2.2]. It follows that as C is a super-$\text{AFL}$, we have that $\text{WP}{[\alpha ]}_A^M\in \mathbf{C}$ implies ${\text{WP}}_A^M\in \mathbf{C}$, as C is closed under union.

Having reduced the language-theoretic properties of ${\text{WP}}_A^M$ to those of $\text{WP}{[\alpha ]}_A^M$, we perform another reduction, which will yield Lemma 4.1. Let(4.4) $$\text{WP}{\left[\alpha \sqcap \alpha \right]}_A^M=\{w_1\#w_2^{\text{rev}}|w_1,w_2\in \alpha A^{\ast }\cap A^{\ast }\alpha \text{ such that }{w}_1{=}_M{w}_2\}.$$(4.4)

Of course, we have the strict inclusions$$\text{WP}{\left[\alpha \sqcap \alpha \right]}_A^M\subset \text{WP}{\left[\alpha \right]}_A^M\subset {\text{WP}}_A^M.$$

Using this new language, we define the rewriting system(4.5) $${\mathcal{R}}_{\alpha }=\{(w_1\#w_2^{\text{rev}}\to \#)|w_1\#w_2^{\text{rev}}\in \text{WP}{\left[\alpha \sqcap \alpha \right]}_A^M\cup {\text{WP}}_A^{A^{\ast }}\}.$$(4.5)

This is a monadic rewriting system. As C is a super-$\text{AFL}$, if we now have $\text{WP}{[\alpha \sqcap \alpha ]}_A^M\in \mathbf{C}$, then it follows that ${\mathcal{R}}_{\alpha }$ is a C-rewriting system.

Lemma 4.1.

If $\text{WP}{[\alpha \sqcap \alpha ]}_A^M\in \mathbf{C}$, then ${\text{WP}}_A^M\in \mathbf{C}$.

Proof.

Suppose $\text{WP}{[\alpha \sqcap \alpha ]}_A^M\in \mathbf{C}$. By the remarks following (4.2) and (4.3), it suffices to show that $\text{WP}{[\alpha ]}_A^M\in \mathbf{C}$. We claim that(4.6) $$\text{WP}{\left[\alpha \right]}_A^M={〈{\text{WP}}_A^{A^{\ast }}〉}_{{\mathcal{R}}_{\alpha }}\cap (A^{\ast }\alpha A^{\ast }\#A^{\ast }{\alpha }^{\text{rev}}{A}^{\ast }).$$(4.6)

This suffices to establish that $\text{WP}{[\alpha ]}_A^M\in \mathbf{C}$, as C is closed under intersection with regular languages; ${\text{WP}}_A^{A^{\ast }}$ is a context-free language and hence in C; and C has the monadic ancestor property.

Note first that for every rule $(s,t)\in {\mathcal{R}}_{\alpha }$ we have $s,t\in {\text{WP}}_A^M$. Hence, if $w\in {〈{\text{WP}}_A^{A^{\ast }}〉}_{{\mathcal{R}}_{\alpha }}$, then it is clear by induction on the number of ${\mathcal{R}}_{\alpha }$-rewritings necessary to transform w into an element of ${\text{WP}}_A^{A^{\ast }}$ that $w\in {\text{WP}}_A^M$. Hence the inclusion $\supseteq$ in (4.6) is proved.

Second, if $w\in \text{WP}{[\alpha ]}_A^M$, then $w\equiv u\#v^{\text{rev}}$ for some $u,v\in A^{\ast }\alpha A^{\ast }$ with $u{=}_{M}v$. Let $u\prime u^{†}u″$ and $v\prime v^{†}v″$ be the canonical forms of u and v, respectively. By Theorem 3.1, we have $u\prime \equiv v\prime ,u″\equiv v″$, and $u^{†}{=}_M{v}^{†}$. Hence$$u\prime \#{(v\prime )}^{\text{rev}},u″\#{(v″)}^{\text{rev}}\in {\text{WP}}_A^{A^{\ast }}.$$

Furthermore, $u^{†}\#{(v^{†})}^{\text{rev}}\in \text{WP}{[\alpha \sqcap \alpha ]}_A^M$. Thus from (4.5) we find$$(s,\#)\in {\mathcal{R}}_{\alpha }\hspace{1em}\text{for all}\hspace{1em}s\in \{u\prime \#{(v\prime )}^{\text{rev}},u″\#{(v″)}^{\text{rev}},u^{†}\#{(v^{†})}^{\text{rev}}\}.$$

It follows that$$w\equiv u\#v^{\text{rev}}\equiv u\prime u^{†}u″\#{(v″)}^{\text{rev}}{(v^{†})}^{\text{rev}}{(v\prime )}^{\text{rev}}{\stackrel{}{\to }}_{{\mathcal{R}}_{\alpha }}^{\ast }\#.$$

Thus $w\in {〈\#〉}_{{\mathcal{R}}_{\alpha }}\subseteq {〈{\text{WP}}_A^{A^{\ast }}〉}_{{\mathcal{R}}_{\alpha }}$. As w was arbitrary, and as both u and v contain α, we have proved the inclusion $\subseteq$ in (4.6). This establishes the desired equality (4.6). □

Thus, to prove (the hard direction of) the main theorem, it suffices to show that the properties of $\text{WP}{[\alpha \sqcap \alpha ]}_A^M$ reduce to the properties of L(M). This is non-trivial; a reduction to the properties of $L_{\ast }(M)$ is suggested by Theorem 3.1, but $L_{\ast }(M)$ is not a finitely generated monoid, being a free product of L(M) by an infinite rank free monoid $\mathcal{F}$. However, the word problem of $\mathcal{F}$ is, informally speaking, essentially the context-free language ${\mathcal{L}}_{\mathcal{F}}={\text{WP}}_A^{A^{\ast }}\cap ({\Sigma }_{\ast }-\Sigma )\#{({\Sigma }_{\ast }-\Sigma )}^{\text{rev}}$. We will show that $\text{WP}{[\alpha \sqcap \alpha ]}_A^M$ is, up to technical details, describable as an alternating product of the word problem of L(M) by this language ${\mathcal{L}}_{\mathcal{F}}$, together with an appropriate amount of ancestry.² By the preservation results for alternating products and ancestry, this yields the proof strategy for reducing $\text{WP}{[\alpha \sqcap \alpha ]}_A^M$ to L(M).

Lemma 4.2.

If L(M) has word problem in C, then $\text{WP}{[\alpha \sqcap \alpha ]}_A^M\in \mathbf{C}$.

Before giving the proof of this key lemma, we need some setup and auxiliary lemmas. We introduce some notation for convenience. Let ${\Sigma }_1=\Sigma$, and let ${\Sigma }_2={\Sigma }_{\ast }-\Sigma$. Obviously ${\Sigma }_1\cap {\Sigma }_2=\varnothing$. Let ${\Gamma }_i=\phi ({\Sigma }_i)$ for i = 1, 2. As Σ_i is a suffix code, it follows that $\phi ({\Sigma }_i^{\ast })=\phi {({\Sigma }_i)}^{\ast }={\Gamma }_i^{\ast }$, for i = 1, 2. For further ease of notation, we write $M_1={〈{\Gamma }_1〉}_{L_{\ast }(M)}=L(M)$, and $M_2={〈{\Gamma }_2〉}_{L_{\ast }(M)}=\mathcal{F}$. Then $L_{\ast }(M)=M_1\ast M_2$, where * denotes the monoid free product. In this new notation, it follows directly from Theorem 3.1 that if $u,v\in {\Sigma }_1^{\ast }$, then(4.7) $$u\alpha {=}_{M}v\alpha \hspace{1em}\iff \hspace{1em}\phi (u){=}_{M_1}\phi (v),$$(4.7) as in this case $\phi (u),\phi (v)\in {\Gamma }_1^{\ast }$, and all defining relations of the presentation (3.3) of $L_{\ast }(M)$ are pairs of words over the alphabet ${\Gamma }_1$. Analogously, if $u,v\in {\Sigma }_2^{\ast }$, then(4.8) $$u\alpha {=}_{M}v\alpha \hspace{1em}\iff \hspace{1em}u\equiv v.$$(4.8)

We define two rewriting systems on ${\Sigma }_1^{\ast }$ resp. ${({\Sigma }_1^{\text{rev}})}^{\ast }$. Let(4.9) $$I_{\alpha }=\{(w\alpha ,\alpha )|w\in {\Sigma }_1^{+}:w\alpha {=}_M\alpha \},$$(4.9) (4.10) $$I_{\alpha }^r=\{({(w\alpha )}^{\text{rev}},{\alpha }^{\text{rev}})|w\in {\Sigma }_1^{+}:w\alpha {=}_M\alpha \}.$$(4.10)

Let now $u\in {({\Sigma }_1\cup {\Sigma }_2)}^{\ast }$ be any word, factorized uniquely as $u_0{u}_1\cdots u_n$ with $u_i\in {\Sigma }_{X(i)}^{+}$ for all $0\le i<n$ and $u_n\in {\Sigma }_{X(n)}^{\ast }$, where X is a standard parametrisation. We say that (this factorization of) u is reduced if $u\equiv \alpha$ or $u\equiv \epsilon$; or if $u_i\alpha {\ne }_M\alpha$ for all $0\le i\le n$. Obviously, any irreducible descendant of u modulo $I_{\alpha }$ is reduced, and any reduced word is clearly irreducible modulo $I_{\alpha }$. Furthermore, as $I_{\alpha }$ is M-invariant, if $u{\stackrel{}{\to }}_{I_{\alpha }}^{\ast }u\prime$, then $u{=}_{M}u\prime$, so we conclude that every word $u\in {({\Sigma }_1\cup {\Sigma }_2)}^{\ast }$ is equal in M to some reduced word $u\prime$ (though this is generally not unique). Given any reduced $u\prime$, we can uniquely factorize it as a reduced factorization $u_0^{\prime }{u}_1^{\prime }\cdots u_k^{\prime }$, where $u_i^{\prime }\in {\Sigma }_{Y(i)}^{\ast }$ for $0\le i\le k$, where Y is a standard parametrisation. This factorization $u_0^{\prime }{u}_1^{\prime }\cdots u_k^{\prime }$ of $u\prime$ is called the normal form of the reduced word $u\prime$.

Lemma 4.3.

Let $u,v\in {({\Sigma }_1\cup {\Sigma }_2)}^{\ast }$. Let $u\prime$, resp. $v\prime$, be any reduced forms of u, resp. v, with normal forms $u\prime \equiv u_0^{\prime }{u}_1^{\prime }\cdots u_m^{\prime }$ and $v\prime \equiv v_0^{\prime }{v}_1^{\prime }\cdots v_n^{\prime }$ respectively. Then $u\alpha {=}_{M}v\alpha$ if and only if (1) n = m, and (2) $u_i^{\prime },v_i^{\prime }\in {\Sigma }_{X(i)}^{\ast }$ and $u_i^{\prime }\alpha {=}_M{v}_i^{\prime }\alpha$ for all $0\le i\le n$, for some standard parametrisation X.

Proof.

The “if” direction follows by induction on n, and the simple observation that if $u_i,v_i,u_{i+1},v_{i+1}\in {\Sigma }^{+}$, then as $u_{i+1}$ and $v_{i+1}$ begin with α we have$$(u_i\alpha {=}_M{v}_i\alpha \text{ and }{u}_{i+1}\alpha {=}_M{v}_{i+1}\alpha )\hspace{1em}\Rightarrow \hspace{1em}{u}_i{u}_{i+1}\alpha {=}_M{v}_i{v}_{i+1}\alpha .$$

For the “only if” direction, by Theorem 3.1, it follows that $u\alpha {=}_{M}v\alpha$ if and only if $\phi (u\prime ){=}_{M_1\ast M_2}\phi (v\prime )$. Now $\phi (u\prime )\equiv \phi (u_0^{\prime })\phi (u_1^{\prime })\cdots \phi (u{\prime }_m)$. As $\phi (u_i^{\prime }){=}_{M_1\ast M_2}1$ if and only $u_i^{\prime }\alpha {=}_M\alpha$, it follows from the fact that $u\prime$ is reduced that $\phi (u\prime )$ is reduced with respect to the monoid free product $M_1\ast M_2$, i.e. no non-empty subword of $\phi (u\prime )$ equals 1 in $M_1\ast M_2$. The analogous statement is true for $\phi (v\prime )$. Hence, as $\phi (u\prime ){=}_{M_1\ast M_2}\phi (v\prime )$, it follows from the usual normal form lemma for monoid free products (see [20, Section 8.2] or [37, Section 1]) that (1) n = m; and that (2) $\phi (u_i^{\prime }),\phi (v_i^{\prime })\in {\Gamma }_{X(i)}^{\ast }$ and $\phi (u_i^{\prime }){=}_{M_{X(i)}}\phi (v_i^{\prime })$ for $0\le i\le n$, where X is some standard parametrisation. As $u_i^{\prime }\alpha {=}_M{v}_i^{\prime }\alpha$ if and only $\phi (u_i^{\prime }){=}_{M_{X(i)}}\phi (v_i^{\prime })$, the result follows. □

The rewriting systems $I_{\alpha }$ and $I_{\alpha }^r$ defined in (4.9) and (4.10) are close to being monadic. We show that, via appropriate rational transductions, we can extend the monadic ancestor property to also apply to these rewriting systems, using the self-overlap free property of α in a non-trivial way.

Lemma 4.4.

If L(M) has word problem in C, then $I_{\alpha }$ and $I_{\alpha }^r$ are C-ancestry preserving.

Proof.

Let $L\subseteq {({\Sigma }_1\cup {\Sigma }_2)}^{\ast }$ be an arbitrary language with $L\in \mathbf{C}$. To prove that $I_{\alpha }$ is C-ancestry preserving, it suffices to show that ${〈L〉}_{I_{\alpha }}\in \mathbf{C}$. Let $I_{\alpha }^{+}$ be the set of left-hand sides of rules in $I_{\alpha }$. We claim $I_{\alpha }^{+}\in \mathbf{C}$. Indeed, $w\in {\Sigma }_1^{\ast }$ is such that $w\alpha {=}_M\alpha$ if and only if $\phi (w){=}_{L(M)}1$ by (4.7). Recalling the definition of ${\text{IP}}_A^M$ from (2.1), it follows that(4.11) $$I_{\alpha }^{+}={\phi }^{-1}({\text{IP}}_{{\Gamma }_1}^{M_1})\alpha -\left\{\alpha \right\}={\phi }^{-1}({\text{IP}}_{{\Gamma }_1}^{M_1})\alpha \cap {\Sigma }_1^{+}\alpha .$$(4.11)

As L(M) has word problem in C, it follows that ${\text{IP}}_{{\Gamma }_1}^{M_1}\in \mathbf{C}$, by an easy transduction (cf. [37, Lemma 3.5]). As C is a full $\text{AFL}$ and $\phi$ is a homomorphism, it hence follows from (4.11) that $I_{\alpha }^{+}\in \mathbf{C}$.

Let now $\diamond$ be a new symbol. Let $A_{\diamond }=A\cup \{\diamond \}$, and define the homomorphism ${\sigma }_{\diamond }:A_{\diamond }^{\ast }\to A^{\ast }$ by $a\mapsto a$ for all $a\in A$, and $\diamond \mapsto \alpha$. Define a new rewriting system$$I_{\alpha }^{\diamond }=\{(W\to \diamond )|W\in {\sigma }_{\diamond }^{-1}(I_{\alpha }^{+})\cap (A_{\diamond }^{\ast }-A_{\diamond }^{\ast }\alpha A_{\diamond }^{\ast })\}.$$

Clearly $I_{\alpha }^{\diamond }$ is a monadic rewriting system. The language of left-hand sides of $\diamond$ in $I_{\alpha }^{\diamond }$ is the intersection ${\sigma }_{\diamond }^{-1}(I_{\alpha }^{+})\cap (A_{\diamond }^{\ast }-A_{\diamond }^{\ast }\alpha A_{\diamond }^{\ast })$, and as $I_{\alpha }^{+}\in \mathbf{C}$ it follows from the closure of C under rational transduction that $I_{\alpha }^{\diamond }$ is a C-rewriting system.

Now, as α is self-overlap free, ${\Sigma }_1$ is a suffix code, so for any word $u\in A^{\ast }\alpha A^{\ast }$ we can uniquely factor u as $u_0\alpha u_1\alpha \cdots \alpha u_k$, where $u_i\in A^{\ast }-A^{\ast }\alpha A^{\ast }$ for $0\le i\le k$. Hence there is exactly one word $u_{\diamond }\in A_{\diamond }^{\ast }$ with the properties that (1) $u_{\diamond }$ does not contain α; and (2) ${\sigma }_{\diamond }(u_{\diamond })=u$. The uniqueness of this word depends on the fact that α is self-overlap free.³ Of course, for any $u\in A^{\ast }-A^{\ast }\alpha A^{\ast }$, there is also a unique such $u_{\diamond }$, namely $u_{\diamond }\equiv u$. Let $L_{\diamond }$ be the language $\left\{w_{\diamond }\right|w\in L\}$. Then ${\sigma }_{\diamond }(L_{\diamond })=L$. Furthermore, by the above uniqueness argument, we have(4.12) $$L_{\diamond }={\sigma }_{\diamond }^{-1}(L)\cap (A_{\diamond }^{\ast }-A_{\diamond }^{\ast }\alpha A_{\diamond }^{\ast }).$$(4.12)

Hence, from $L\in \mathbf{C}$ we conclude $L_{\diamond }\in \mathbf{C}$.

We now claim that ${〈L〉}_{I_{\alpha }}={\sigma }_{\diamond }({〈L_{\diamond }〉}_{I_{\alpha }^{\diamond }})$. The right-hand side is the image under the homomorphism ${\sigma }_{\diamond }$ of the ancestor of $L_{\diamond }$ under the monadic C-rewriting system $I_{\alpha }^{\diamond }$. As C is a super-$\text{AFL}$, the right-hand side is in C, and thus we would conclude that $I_{\alpha }$ is C-ancestry preserving. The desired equality is easy to prove. Indeed, it follows directly from the fact that if $w\in A^{\ast }$ and $u\in L$, then $w{\stackrel{}{\to }}_{I_{\alpha }}^{\ast }u$ if and only if $w_{\diamond }{\stackrel{}{\to }}_{I_{\alpha }^{\diamond }}^{\ast }{u}_{\diamond }$. This latter fact is proved by an easy induction on the number of rules applied, and we omit this proof. We conclude that $I_{\alpha }$ is C-ancestry preserving.

The case of $I_{\alpha }^r$ is symmetric, bearing in mind that (1) C is reversal-closed; (2) ${\alpha }^{\text{rev}}$ is self-overlap free if and only if α is self-overlap free, and (3) ${\Sigma }_1^{\text{rev}}$ is a prefix code, rather than a suffix code (factorization over ${\Sigma }_1^{\text{rev}}$ is still unique). We omit the details. □

One more step is needed before proving Lemma 4.2. Let ${\mathcal{P}}_2=\{w\#w^{\text{rev}}|w\in {\Sigma }_2^{\ast }\}$, where the $\mathcal{P}$ abbreviates “palindrome.” By (4.8), we have(4.13) $${\text{WP}}_A^M\cap ({\Sigma }_2^{\ast }\#{({\Sigma }_2^{\text{rev}})}^{\ast })={\mathcal{P}}_2.$$(4.13)

Clearly ${\mathcal{P}}_2$ is a context-free language, as ${\Sigma }_2$ is regular, so ${\mathcal{P}}_2\in \mathbf{C}$. Let ${\tau }_{\#}:A_{\#}^{\ast }\to A_{\#}^{\ast }$ be defined by ${\tau }_{\#}(a)=a$ for all $a\in A$, and ${\tau }_{\#}(\#)=\alpha \#{\alpha }^{\text{rev}}$. We define the (rather complicated-looking) language(4.14) $${\mathcal{L}}_{\alpha }{=}^{I_{\alpha }}{({\tau }_{\#}({\text{WP}}_{{\Sigma }_1}^{L(M)}\star {\mathcal{P}}_2))}^{I_{\alpha }^r}.$$(4.14)

We shall see in the below proof of Lemma 4.2 that ${\mathcal{L}}_{\alpha }=\text{WP}{[\alpha \sqcap \alpha ]}_A^M$. We first prove that ${\mathcal{L}}_{\alpha }$ is a language encoding the language-theoretic properties of L(M).

Lemma 4.5.

If L(M) has word problem in C, then ${\mathcal{L}}_{\alpha }\in \mathbf{C}$.

Proof.

If L(M) has word problem in C, we have ${\text{WP}}_{{\Sigma }_1}^{L(M)}\in \mathbf{C}$ (cf. also the remark preceding (4.1)). This is a concatenation-closed language, as it is a word problem. Furthermore, ${\mathcal{P}}_2$ is a context-free language and is easily checked to be concatenation-closed. Hence by Proposition 2.1, the alternating product ${\text{WP}}_{{\Sigma }_1}^{L(M)}\star {\mathcal{P}}_2$ is in C, as is its image under the homomorphism ${\tau }_{\#}$. By Lemma 4.4, $I_{\alpha }$ and $I_{\alpha }^r$ are C-ancestry preserving, so by Proposition 2.2, we have ${\mathcal{L}}_{\alpha }\in \mathbf{C}$. □

Proof of Lemma 4.2.

It suffices, by Lemma 4.5, to prove that $\text{WP}{[\alpha \sqcap \alpha ]}_A^M={\mathcal{L}}_{\alpha }$. We prove the inclusions one at a time.

$(\subseteq )$. Let $w\in \text{WP}{[\alpha \sqcap \alpha ]}_A^M$ be arbitrary. Then we can write $w\equiv u\alpha \#{(v\alpha )}^{\text{rev}}$ with $u,v\in {({\Sigma }_1\cup {\Sigma }_2)}^{\ast }$ and $u\alpha {=}_{M}v\alpha$. Let $u\prime ,v\prime$ be reduced forms of u resp. v such that $u{\stackrel{}{\to }}_{I_{\alpha }}^{\ast }u\prime$ and $v{\stackrel{}{\to }}_{I_{\alpha }}^{\ast }v\prime$. As $I_{\alpha }$ is M-invariant, we have $u{=}_{M}u\prime$ and $v{=}_{M}v\prime$. Then by Lemma 4.3 we can write$$u\prime \equiv u_0^{\prime }{u}_1^{\prime }\cdots u_m^{\prime }\hspace{1em}\text{and}\hspace{1em}v\prime \equiv v_0^{\prime }{v}_1^{\prime }\cdots v_n^{\prime },$$with n = m, $u_i^{\prime },v_i^{\prime }\in {\Sigma }_{X(i)}^{\ast }$ and $u_i^{\prime }\alpha {=}_M{v}_i^{\prime }\alpha$ for all $0\le i\le n=m$, for some standard parametrisation X. Let X be such a parametrisation. Let(4.15) $$w\prime \equiv u_1^{\prime }{u}_2^{\prime }\cdots u_n^{\prime }\#{(v_n^{\prime })}^{\text{rev}}\cdots {(v_2^{\prime })}^{\text{rev}}{(v_1^{\prime })}^{\text{rev}}.$$(4.15)

Now for every $0\le i\le n$, we have $u_i^{\prime }\alpha {=}_M{v}_i^{\prime }\alpha$ if and only if $\phi (u_i^{\prime }){=}_{M_{X(i)}}\phi (v_i^{\prime })$. When X(i) = 1, then by (4.1) and (4.7) it follows that ${\pi }_{{\Sigma }_1}(u_i^{\prime })={\pi }_{{\Sigma }_1}(v_i^{\prime })$, so $u_i^{\prime }\#{(v_i^{\prime })}^{\text{rev}}\in {\text{WP}}_{{\Sigma }_1}^{L(M)}$. When X(i) = 2, then by (4.8) we have $u_i^{\prime }\equiv v_i^{\prime }$, so $u_i^{\prime }\#{(v_i^{\prime })}^{\text{rev}}\in {\mathcal{P}}_2$. It follows that the right-hand side of (4.15) is an element of the alternating product of ${\text{WP}}_{{\Sigma }_1}^{L(M)}$ by ${\mathcal{P}}_2$, and hence so too is $w\prime$. Let $\mathcal{Q}={\text{WP}}_{{\Sigma }_1}^{L(M)}\star {\mathcal{P}}_2$, i.e. we just proved $w\prime \in \mathcal{Q}$. Let(4.16) $$w″\equiv u_1^{\prime }{u}_2^{\prime }\cdots u_n^{\prime }\alpha \#{\alpha }^{\text{rev}}{(v_n^{\prime })}^{\text{rev}}\cdots {(v_2^{\prime })}^{\text{rev}}{(v_1^{\prime })}^{\text{rev}}\equiv u\prime \#{(v\prime )}^{\text{rev}}.$$(4.16)

Then $w″\equiv {\tau }_{\#}(w\prime )$. We have $u{\stackrel{}{\to }}_{I_{\alpha }}^{\ast }u\prime$, so of course $u\alpha {\stackrel{}{\to }}_{I_{\alpha }}^{\ast }u\prime \alpha$. As $v{\stackrel{}{\to }}_{I_{\alpha }}^{\ast }v\prime$, we have $v^{\text{rev}}{\stackrel{}{\to }}_{I_{\alpha }^r}^{\ast }{(v\prime )}^{\text{rev}}$ and so also ${\alpha }^{\text{rev}}{v}^{\text{rev}}{\stackrel{}{\to }}_{I_{\alpha }^r}^{\ast }{\alpha }^{\text{rev}}{(v\prime )}^{\text{rev}}$. Hence, by the definition of $(I_{\alpha },I_{\alpha }^r)$-ancestors, we have(4.17) $$u\alpha \#{\alpha }^{\text{rev}}{v}^{\text{rev}}{\in }^{I_{\alpha }}{({\tau }_{\#}(\mathcal{Q}))}^{I_{\alpha }^r}.$$(4.17)

But $u\alpha \#{\alpha }^{\text{rev}}{v}^{\text{rev}}$ is just w; and the right-hand side of (4.17) is ${\mathcal{L}}_{\alpha }$, so we are done.

$(\supseteq )$ This argument is similar to the direction $(\subseteq )$, and differs only in that it uses the M-invariance of $I_{\alpha }$. The proof is therefore only sketched here (but is detailed in the author’s Ph.D. thesis [34, Lemma 4.2.13]).

Consider any word $u\#v\in {\mathcal{L}}_{\alpha }$. Two things must be proved; first, that (1) $u,v^{\text{rev}}\in \alpha A^{\ast }\cap A^{\ast }\alpha$; and second, that (2) $u{=}_M{v}^{\text{rev}}$. For (1), it suffices to note that any word in ${\tau }_{\#}({\text{WP}}_{{\Sigma }_1}^{L(M)}\star {\mathcal{P}}_2)$ is of the form $U\#V$ with $U,V^{\text{rev}}\in \alpha A^{\ast }\cap A^{\ast }\alpha$. As $I_{\alpha }$ is M-invariant, any ancestor $U\prime$ of $U\in \alpha A^{\ast }\cap A^{\ast }\alpha$ will be equal to U in M; hence, in particular, we will also have $U\prime \in \alpha A^{\ast }\cap A^{\ast }\alpha$ by Theorem 3.1. The analogous argument for V implies that (1) holds.

For (2), since $u\#v\in {\mathcal{L}}_{\alpha }$, there is some $u\prime \#v\prime \in {\text{WP}}_{{\Sigma }_1}^{L(M)}\star {\mathcal{P}}_{{\Sigma }_2}$ such that$$\begin{array}{c}u{\stackrel{}{\to }}_{I_{\alpha }}^{\ast }u\prime \alpha ,\\ v{\stackrel{}{\to }}_{I_{\alpha }^r}^{\ast }v\prime \alpha ,\end{array}$$as ${\tau }_{\#}(u\prime \#v\prime )\equiv (u\prime \alpha )\#({\alpha }^{\text{rev}}v\prime )$. By the M-invariance of $I_{\alpha }$, we have $u{=}_{M}u\prime \alpha$, and analogously also $v{=}_{M}v\prime \alpha$. Thus to show that $u\#v$ satisfies (2), it suffices to show $u\prime \alpha {=}_M{(v\prime )}^{\text{rev}}\alpha$. But that this is the case can be easily seen by writing out $u\prime \#v\prime$ as an element of the alternating product ${\text{WP}}_{{\Sigma }_1}^{L(M)}\star {\mathcal{P}}_{{\Sigma }_2}$. □

By combining Lemmas 4.1 and 4.2, we conclude that if L(M) has word problem in C, then M has word problem in C. This is the difficult direction of the proof of Theorem 1.1. It remains to prove the converse:

Lemma 4.6.

If M has word problem in C, then L(M) has word problem in C.

Proof.

Indeed, as before let the homomorphism ${\tau }_{\#}:A_{\#}^{\ast }\to A_{\#}^{\ast }$ be defined by ${\tau }_{\#}(a)=a$ for all $a\in A$, and ${\tau }_{\#}(\#)=\alpha \#{\alpha }^{\text{rev}}$. Then it is easy to check, using (4.1), that(4.18) $${\tau }_{\#}\left({\text{WP}}_{{\Sigma }_1}^{L(M)}\right)={\text{WP}}_A^M\cap ({\Sigma }_1^{\ast }\alpha \#{\alpha }^{\text{rev}}{({\Sigma }_1^{\text{rev}})}^{\ast }).$$(4.18)

Now ${\tau }_{\#}$ is an injective homomorphism, as $A\cup \{\alpha \#{\alpha }^{\text{rev}}\}$ is a code, implying that any word in the image of ${\tau }_{\#}$ can be decoded by finding all the occurrences of ${\tau }_{\#}$, which must be surrounded by non-overlapping occurrences of α, and the remaining letters are then decoded as themselves. In particular, ${\tau }_{\#}^{-1}°{\tau }_{\#}(L)=L$ for any language L. Hence, applying ${\tau }_{\#}^{-1}$ to both sides in (4.18), we find that ${\text{WP}}_{{\Sigma }_1}^{L(M)}$ is a rational transduction of ${\text{WP}}_A^M$. As C is closed under rational transductions, it follows that L(M) has word problem in C. □

This completes the proof of Theorem 1.1.

5 Corollaries of Theorem 1.1

In this section, we present some corollaries of Theorem 1.1. In particular, we will show that it is decidable whether a one-relation monoid containing a non-trivial idempotent has context-free word problem (Theorem 5.4). This answers a generalisation of a question first asked by Zhang in 1992, which was answered affirmatively by the author in [36]. We begin by applying the result to the rational subset membership problem for monoids.

5.1 Rational subset membership problem

Throughout this section we will fix a weakly compressible monoid M, defined by the presentation (3.1), which is compressible with respect to α. As the class of context-free (resp. indexed) languages is a super-$\text{AFL}$ closed under reversal, it of course follows from Theorem 1.1 that: M has context-free (resp. indexed) word problem if and only if L(M) does.

One of the direct consequences for a monoid having context-free word problem is decidability of its rational subset membership problem. Recall that for a finitely generated monoid M, generated by a finite set A and with associated surjective homomorphism $\pi :A^{\ast }\to M$, this decision problem asks: given a regular language $R\subseteq A^{\ast }$ and a word $w\in A^{\ast }$, can one decide whether $\pi (w)\in \pi (R)$? The rational subset membership problem clearly specializes to the submonoid membership problem, the divisibility problems, and the word problem for M. It is easy to check that any context-free monoid has decidable rational subset membership problem; indeed, if $\pi (w)\in \pi (R)$ if and only if w is equal to some word in R, i.e. if and only if $w\in {\text{WP}}_A^M/\#R^{\text{rev}}$, where $/$ denotes the right quotient. As $\#R^{\text{rev}}$ is a regular language, and ${\text{WP}}_A^M$ is a context-free language, the quotient is a context-free language; and membership in context-free languages is well-known to be (uniformly) decidable (cf. also [36, Theorem 3.5]). We conclude:

Corollary 5.1.

Let M be a weakly compressible monoid. If L(M) has context-free word problem, then the rational subset membership problem for M is decidable.

Example 4.

Let $n,k,{\beta }_1,\dots ,{\beta }_n$ be natural numbers such that n > 1, $1\le k\le n$, and ${\beta }_i\ge 1$ for all $1\le i\le n$. Let $\Pi =\Pi (n,k,{\left\{{\beta }_i\right\}}_{i=1}^n)$ be the monoid defined by$$\text{Mon}〈a_1,a_2,\dots ,a_n|a_1^{{\beta }_1}{a}_2^{{\beta }_2}\cdots a_n^{{\beta }_n}=a_k〉.$$

Then as the rewriting system with the single rule $(a_1^{{\beta }_1}{a}_2^{{\beta }_2}\cdots a_n^{{\beta }_n},a_k)$ is complete, monadic, context-free, and defines Π, it follows that Π has context-free word problem [7, Corollary 3.8]. Hence, by Theorem 1.1 any monoid which compresses to Π has context-free word problem. Let now A be a new alphabet, let $\alpha \in A^{\ast }$ be self-overlap free, and let $w_i\in \alpha (A^{\ast }-A^{\ast }\alpha A^{\ast })$ for $1\le i\le n$ be pairwise distinct words. Let τ be the homomorphism defined by mapping $a_i\mapsto w_i$ for all $1\le i\le n$. Let $\Pi \prime =\Pi \prime (n,k,{\left\{{\beta }_i\right\}}_{i=1}^n,{\left\{w_i\right\}}_{i=1}^n)$ be the monoid defined by(5.1) $$\Pi \prime =\text{Mon}〈A|\tau (a_1^{{\beta }_1}{a}_2^{{\beta }_2}\cdots a_n^{{\beta }_n})\alpha =\tau (a_k)\alpha 〉.$$(5.1)

Then one readily sees that $L(\Pi \prime )=\Pi$. Hence $\Pi \prime$ has context-free word problem, for any choice of $n,k,{\beta }_i$ and w_i ($1\le i\le n$). As a concrete example, if $A=\{x,y\}$ and $\alpha =xy$, then the monoid $\Pi \prime =\Pi \prime (3,2,\{2,3,4\},\{xy,\mathit{xyx},\mathit{xyy}\})$ defined by(5.2) $$\text{Mon}〈x,y|{(xy)}^2{(\mathit{xyx})}^3{(\mathit{xyy})}^{4}xy=\mathit{xyxxy}〉$$(5.2) has context-free word problem, as it compresses to the monoid $\Pi (3,2,\{2,3,4\})$ defined by$$\text{Mon}〈a_1,a_2,a_3|a_1^2{a}_2^3{a}_3^4=a_2〉.$$

Verifying directly that (5.2) has context-free word problem appears to be somewhat tedious.

We conclude that the monoid (5.2) has decidable rational subset membership problem, and more generally so too does any monoid of the form (5.1).

5.2 Subspecial one-relation monoids

We turn to the case when M in (3.1) is defined by a single relation u = v. Assume without loss of generality that $\left|u\right|\ge \left|v\right|$. We say that M is subspecial if $u\in v{A}^{\ast }\cap A^{\ast }v$. Any special monoid (i.e. when the defining relation is u = 1) is obviously subspecial. An element $e\in M$ is called an idempotent if $e^2=e$. Of course, the identity element 1 is always a (trivial) idempotent. Associated to any idempotent e is a maximal subgroup, being the set of elements which are invertible with respect to this idempotent (alternatively, the group $\mathcal{H}$-class of e). Lallement [24] proved that a one-relation monoid M contains a non-trivial idempotent if and only if (1) M is special, and not right cancellative; (2) $\left|u\right|>\left|v\right|>0$ and M is subspecial. By using Adian’s overlap algorithm (see [36]), it is decidable whether a one-relation special monoid is right cancellative. Hence it is decidable whether a one-relation monoid M contains a non-trivial idempotent.

As M is subspecial, it is clearly weakly compressible. Furthermore, it is not hard to see that L(M) is also subspecial (see e.g. [22, Lemma 5.4]). Thus to any subspecial monoid M we can associate a special monoid $L_s(M)$, obtained by iterating weak compression until we arrive at a special monoid. Hence M has context-free word problem if and only if $L_s(M)$ does, by Theorem 1.1 (of course, the same is also true for any reversal-closed super-$\text{AFL}$). Using the structural results about maximal subgroups of subspecial monoids by Gray & Steinberg [14], we can prove the following extension of the Muller–Schupp theorem:

Theorem 5.2.

Let M be a subspecial (one-relation) monoid. Then M has context-free word problem if and only if all of its maximal subgroups are virtually free.

Proof.

First, assume M is special. Then, by a result due to Malheiro [30, Theorem 4.6], all maximal subgroups of M are isomorphic to the group of units U(M) of M. The main theorem of [36] states that M has context-free word problem if and only if U(M) is virtually free. The result thus follows in this case.

Suppose that M is subspecial, but not special. By [14, Lemma 5.2], the maximal subgroups of M are all isomorphic to the group of units of $L_s(M)$, with the exception of the group of units of M, which is trivial (and hence virtually free). Let G be one of the non-trivial maximal subgroups of M, so that $G\cong U(L_s(M))$. Now $L_s(M)$ is a finitely generated one-relation special monoid. Hence, by classical results (cf. [36]), G is a finitely generated one-relator group.

Assume now that M has context-free word problem. Then, as G is a finitely generated subsemigroup of M, it follows from [17, Proposition 8(b)] that G has context-free word problem. Hence, by the Muller–Schupp theorem, G is virtually free, as desired. For the converse, assume G is virtually free. By the easy direction of the Muller–Schupp theorem, G has context-free word problem. Then, by the main theorem of [36], $L_s(M)$ has context-free word problem. Hence, by the main theorem of the present paper, M has context-free word problem. □

This gives a complete algebraic characterization of the subspecial monoids with context-free word problem, extending the Muller–Schupp theorem to this class.

Corollary 5.3.

Let M be a subspecial one-relation monoid such that all of its maximal subgroups are virtually free. Then M has decidable rational subset membership problem.

For example, one can check that the subspecial monoid(5.3) $$M_3=\text{Mon}〈x,y|\mathit{xyxyyxyx}=x〉$$(5.3) compresses (in a single step) to $L_s(M_3)\cong \text{Mon}〈a,b,c|\mathit{abca}=1〉$. Now it follows from [2] that the group of units of $L_s(M_3)$ is isomorphic to $\text{Gp}〈p,q|\mathit{pqp}=1〉$, which is isomorphic to $\mathbb{Z}$ by removing the redundant generator q. Hence the non-trivial maximal subgroups of M₃ are all infinite cyclic, and in particular virtually free. Hence the monoid M₃ defined by (5.3) has context-free word problem by Theorem 5.2, and it has decidable rational subset membership problem by Corollary 5.3.

We end with a final corollary of Theorem 5.2, the statement of which does not use compression or subspeciality.

Theorem 5.4.

There is an algorithm which takes as input a one-relation monoid $M=\text{Mon}〈A|u=v〉$ containing a non-trivial idempotent, and decides whether M has context-free word problem.

Proof.

Suppose we are given a one-relation monoid presentation $\text{Mon}〈A|u=v〉$ for M. Assume without loss of generality that $\left|u\right|\ge \left|v\right|$. Then as M contains a non-trivial idempotent, either M is special, or else M is subspecial with $\left|u\right|>\left|v\right|\ge 0$. In the first case, the defining relation is u = 1, and by [36, Theorem B] we can hence decide (uniformly in u) whether this special one-relation monoid has context-free word problem.

In the latter case, we repeatedly compress the relation u = v until we find(5.4) $$L_s(M)=\text{Mon}〈B|w=1〉.$$(5.4)

By Theorem 1.1, M has context-free word problem if and only if the special one-relation monoid (5.4) has context-free word problem; this latter problem is (uniformly) decidable by another application of [36, Theorem B]. □

In 1992, Zhang [40, Problem 3] asked if it is decidable whether a special one-relation monoid has context-free word problem. This was recently answered affirmatively by the author [36, Theorem B]. The above Theorem 5.4 thus extends this answer from special to subspecial one-relation monoids.

Acknowledgments

The research in this article was carried out while the author was a Ph.D. student at the University of East Anglia. The author wishes to thank his supervisor Dr Robert D. Gray for many useful comments and discussions, and the anonymous referee for very thorough and careful comments, all of which significantly improved the article.

Additional information

Funding

The author gratefully acknowledges funding from the Dame Kathleen Ollerenshaw Trust, which is supporting his current research at the University of Manchester.

Notes

1 The compression defined by Lallement [24] transforms M into $L^n(M)$ in a single step, whereas that by Adian & Oganesian [3] or indeed Kobayashi [22] corresponds to transforming M into L(M).

2 The alternating products and ancestry defined and used by the author in [37] were, in fact, first developed by the author to deal with precisely the problem of describing the word problem of $L_{\ast }(M)$.

3 For example, if we take the word $\alpha \equiv \mathit{xyx}$, which has self-overlaps, then ${\sigma }_{\diamond }(xy\diamond )={\sigma }_{\diamond }(\diamond yx)=\mathit{xyxyx}$.