Two-sided homological properties of special and one-relator monoids Abstract . A monoid presentation is called special if the right-hand side of each defining relation is equal to 1. We prove results which relate the two-sided homological finiteness properties of a monoid defined by a special presentation with those of its group of units. Specifically we show that the monoid enjoys the homological finiteness property bi- FP n {\rm FP}_{n} if its group of units is of type FP n {\rm FP}_{n} . We also obtain results which relate the Hochschild cohomological dimension of the monoid to the cohomological dimension of its group of units. In particular we show that the Hochschild cohomological dimension of the monoid is bounded above by the maximum of 2 2 and the cohomological dimension of its group of units. We apply these results to prove a Lyndon’s Identity type theorem for the two-sided homology of one-relator monoids of the form ⟨ A ∣ r = 1 ⟩ \langle A\mid r=1\rangle . In particular, we show that all such monoids are of type bi- FP ∞ {\rm FP}_{\infty} . Moreover, we show that if r r is not a proper power then the one-relator monoid has Hochschild cohomological dimension at most 2 2 , while if r r is a proper power then it has infinite Hochschild cohomological dimension. For non-special one-relator monoids with defining relation u = v u=v we show that if there is no non-empty word r r such that u , v ∈ A ∗ ​ r ∩ r ​ A ∗ u,v\in A^{*}r\cap rA^{*} then M M is of type bi- FP ∞ {\rm FP}_{\infty} and the Hochschild cohomological dimension at most 2 2 . 2020 Mathematics Subject Classification 20M50, 20M05, 20J05, 57M07, 20F10, 20F65 ROBERT D. GRAY 1 1 1 School of Engineering, Mathematics, and Physics, University of East Anglia, Norwich NR4 7TJ, England. Email Robert.D.Gray@uea.ac.uk . and BENJAMIN STEINBERG 2 2 2 Department of Mathematics, City College of New York, Convent Avenue at 138th Street, New York, New York 10031, USA. Email bsteinberg@ccny.cuny.edu . August 8, 2026 1. Introduction Algorithmic problems in algebra have their origins in logic and topology in the fundamental work of Dehn, Thue and Tietze in the early 1900s; see [ 7 , 44 , 47 ] . The most important algorithmic question concerning an algebraic structure is the word problem, which asks whether one can decide whether two expressions over generators represent the same element. Markov [ 48 ] and Post [ 52 ] proved independently that in general the word problem for finitely presented monoids is undecidable. This was later extended to cancellative monoids by Turing [ 57 ] and then to groups by Novikov [ 50 ] and Boone [ 8 ] . Given that the word problem is undecidable in general, a central theme running through the development of geometric and combinatorial group and monoid theory has been to identify and study families all of whose members have solvable word problem; see [ 9 , Chapter 2] . One of the most important and interesting such families is the class of one-relator groups, which were shown to have decidable word problem in classical work of Magnus [ 45 ] in the 1930s. The theory of one-relator groups has developed extensively over the last century and continues to be a highly active area of research; see [ 42 ] for a recent survey. One of the challenges in studying one-relator groups is that their geometry can be quite complicated. On the other hand, one-relator groups have turned out to be susceptible for study using topological and homological methods. A classical result of this kind is Lyndon’s Identity Theorem [ 43 ] which, interpreted topologically, constructs certain natural classifying spaces for one-relator groups that can be used to deduce all one-relator groups are {\rm FP}_{\infty} , and to determine their cohomological dimension. Some recent important results on one-relator groups that have been impacted by topological and homological methods include: residual finiteness of one-relator groups with torsion [ 61 ] , the proof that one-relator groups with torsion are virtually free-by-cyclic [ 30 ] , and the coherence of one-relator groups [ 29 ] . In particular, a key step in the recent breakthrough coherence theorem of Jaikin-Zapirain and Linton [ 29 ] was to establish homological coherence of one-relator groups, meaning that every finitely generated subgroup is of type {\rm FP}_{2} . This paper is part of a programme of research initiated by the authors in [ 22 , 23 , 21 ] aimed at developing topological and homological methods for monoids and then applying these new results and techniques to the class of one-relator monoids 3 3 3 That is, monoids defined by presentations with a single defining relation u=v where u and v are words over some finite alphabet A . In contrast to one-relator groups, far less is currently known about one-relator monoids, and many fundamental questions about them remain open. Indeed, it is an important longstanding open problem whether the word problem is decidable for one-relator monoids. While in general this problem is open, it has been solved in a number of key cases in the work of Adjan, Adjan and Oganesyan, and Lallement; see [ 1 , 2 , 41 ] . A natural way to attack the word problem for one-relator monoids is via the theory of string rewriting systems. Indeed, an open problem which is intimately related to the word problem for one-relator monoids is the question of whether every one-relator monoid admits a finite complete rewriting system (meaning a monoid presentation which is confluent and terminating; see [ 26 , Chapter 12] ). Since complete rewriting systems give computable normal forms, a positive answer to this question would solve the word problem for one-relator monoids. \Longrightarrow\cdots\Longrightarrow \Longrightarrow\cdots\Longrightarrow \Longrightarrow\cdots\Longrightarrow \Longrightarrow\cdots\Longrightarrow \Longrightarrow\cdots\Longrightarrow \Longrightarrow\cdots\Longrightarrow \Longrightarrow\cdots\Longrightarrow \Longrightarrow\cdots\Longrightarrow bi- {\rm FP}_{3} ( = FHT) FDT left- and right- {\rm FP}_{\infty} left- and right- {\rm FP}_{n} left- and right- {\rm FP}_{3} left- {\rm FP}_{\infty} left- {\rm FP}_{n} bi- {\rm FP}_{\infty} left- {\rm FP}_{3} right- {\rm FP}_{\infty} right- {\rm FP}_{n} right- {\rm FP}_{3} bi- {\rm FP}_{n} bi- {\rm FP}_{2} left- and right- {\rm FP}_{2} left- {\rm FP}_{2} bi- {\rm FP}_{1} ( = finitely dominated) left- and right- {\rm FP}_{1} left- {\rm FP}_{1} ( = f.g. universal left congruence) right- {\rm FP}_{2} right- {\rm FP}_{1} ( = f.g. universal right congruence) Finitely presented Finitely generated Admits a finite complete rewriting system Figure 1. Homological finiteness properties satisfied by monoids that admit finite complete rewriting systems, and all implications between them. The proofs that all these implications hold, and that none of the implications in the diagram are reversible, can be found in the papers [ 14 , 39 , 53 , 58 , 38 , 34 , 54 , 36 ] . Homological and topological methods provide important tools for investigating the question of whether a given monoid admits a presentation by a finite complete rewriting system. The Anick-Groves-Squier theorem, cf. [ 11 ] , shows that if a monoid admits a finite complete rewriting system, then the monoid must satisfy the homological finiteness properties left- and right- {\rm FP}_{\infty} . Kobayashi [ 34 ] improved this result by showing a monoid admitting a finite complete rewriting is of type bi- {\rm FP}_{\infty} . There are in fact a range of finiteness properties satisfied by monoids that admit finite complete rewriting systems, and they have received extensive attention in the literature. The homotopical finiteness property FDT (finite derivation type) was introduced by Squier in [ 55 ] where it was shown that any monoid admitting a finite complete rewriting system had FDT. The two-sided homological finiteness property bi- {\rm FP}_{n} was introduced in [ 37 ] , and in [ 38 ] it was proved that bi- {\rm FP}_{3} is equivalent to the property FHT (finite homological type). Note that Alonso and Hermiller in [ 3 ] introduced another homological finiteness property satisfied by monoids admitting finite complete rewriting systems (that they also called bi- {\rm FP}_{n} ) that was later shown by Pride [ 54 ] to be equivalent to a monoid satisfying both left- {\rm FP}_{n} and right- {\rm FP}_{n} . In Figure 1 we have arranged all these properties and the various implications between them. Note that by results in [ 14 , 39 , 53 , 58 , 38 , 34 , 54 , 36 ] none of the implications in Figure 1 are reversible in general. In particular, in relation to the results we prove in this paper, it is important to stress that it is not true that a monoid satisfying left- {\rm FP}_{n} and right- {\rm FP}_{n} is of type bi- {\rm FP}_{n} . These homological finiteness properties have also arisen naturally in connection to other areas including: monoids with finitely generated universal left congruence, which is equivalent to left- {\rm FP}_{1} (see [ 15 , 16 , 35 ] ), the notion of ancestry in a monoid, due to White from the study of Banach algebras on groups and monoids see [ 15 , Section 3] and [ 60 ] , and finitely dominated monoids (meaning there is a finite subset that dominates the monoid in the sense of Howie and Isbell [ 27 ] ), which is equivalent to bi- {\rm FP}_{1} ; see [ 35 ] . Monoids of type left- {\rm FP}_{n} are also used to define the higher dimensional BNSR invariants of groups; see [ 5 , 6 ] . Motivated by the open question of whether one-relator monoids admit finite complete rewriting systems, together with the Anick-Groves-Squier theorem, Kobayashi initiated the study of homological finiteness properties of one-relator monoids in the papers [ 31 , 33 ] . In these papers Kobayashi resolved this problem in low dimensions by showing that all one-relator monoids are FDT and thus are of type left- {\rm FP}_{3} and right- {\rm FP}_{3} . He then asked the natural question [ 33 , Problem 1] of whether this result could be extended to higher dimension left- and right- {\rm FP}_{n} for all n . In [ 21 ] we gave a positive answer to Kobayashi’s problem by proving that every one-relator monoid is of type left- {\rm FP}_{\infty} and right- {\rm FP}_{\infty} . Looking at the diagram in Figure 1 it is clear that the remaining main open question in this area is to determine whether all one-relator monoids are of type bi- {\rm FP}_{\infty} . Establishing the property bi- {\rm FP}_{\infty} is the best possible result on homological finiteness properties that one could hope to prove for one-relator monoids since it would imply all other previous results on such properties for this class. One of the main applications of the general results we prove in this paper is to resolve this problem in the key case of one-relator monoids where the defining relation is of the form r=1 . We obtain results in this paper on one-relator monoids of the form \langle A\mid r=1\rangle by proving more general results for monoids defined by finite presentations of the form \langle A\mid w_{1}=1,\ldots,w_{k}=1\rangle . These are called special monoids in the literature. Special monoids were studied in the sixties by Adjan [ 1 ] and Makanin [ 46 ] . Adjan proved that the group of units of a one-relator special monoid is a one-relator group and solved the word problem for this class of one-relator monoids by reducing the word problem of the monoid to that of the group of units. Makanin proved more generally that the group of units of a k -relator special monoid is a k -relator group and showed that the monoid has decidable word problem if and only if its group of units does. Later Zhang [ 63 ] gave a more modern approach to these results via the theory of string rewriting systems. The main general result in this paper reduces the problem of whether the homological finiteness property bi- {\rm FP}_{n} holds in a special monoid, to the corresponding question for its group of units. In addition, our methods can be applied to relate the Hochschild cohomological dimension of the monoid to the cohomological dimension of its group of units. Our first main result is: Theorem A . Let M be a finitely presented monoid of the form M=\langle A\mid w_{1}=1,\ldots,w_{k}=1\rangle and let G be the group of units of M . (i) If G is of type {\rm FP}_{n} (for 1\leq n\leq\infty ) then M is of type bi- {\rm FP}_{n} . (ii) Furthermore, the Hochschild cohomological dimension of M is bounded below by \mathrm{cd}(G) and bounded above by \mathrm{max}\{2,\mathrm{cd}(G)\} . We shall then go on to apply this result to prove the following two-sided Lyndon’s Identity Theorem for one-relator monoids of the form \langle A\mid w=1\rangle . Theorem B . Every one-relator monoid of the form \langle A\mid r=1\rangle is of type bi- {\rm FP}_{\infty} . Moreover, if r is not a proper power then the one-relator monoid has Hochschild cohomological dimension at most 2 , while if r is a proper power then the monoid has infinite Hochschild cohomological dimension. As explained in Section 8 below, Theorem B gives a positive solution for an important infinite family of base cases towards a proof of the more general conjecture that all one-relator monoids \langle A\mid u=v\rangle are of type bi- {\rm FP}_{\infty} . The property bi- {\rm FP}_{n} is significantly more robust, and carries more information about a monoid, than either of the properties left- {\rm FP}_{n} or right- {\rm FP}_{n} . For instance, for any monoid M if we adjoin a zero element to form M^{0}=M\cup\{0\} , then the monoid M^{0} will be automatically be of type left- and right- {\rm FP}_{\infty} while in contrast for any integer n the monoid M^{0} will be of type bi- {\rm FP}_{n} if and only if M itself is of type bi- {\rm FP}_{n} ; see [ 23 , Section 3] . There are other results that provide evidence that bi- {\rm FP}_{n} is a more reasonably behaved property than its one-sided counterparts. For instance, in [ 17 ] we shall prove that a von Neumann regular monoid with finitely many left and right ideals is of type bi- {\rm FP}_{n} if and only if all of its maximal subgroups are of type {\rm FP}_{n} . For left- or right- {\rm FP}_{n} this result fails to hold since any group with a zero element adjoined is left- and right- {\rm FP}_{\infty} . The importance of Hochschild cohomology stems from the fact that it is the standard notion of cohomology for rings; [ 25 ] , [ 59 , Chapter 9] , or [ 49 ] . See [ 62 ] for a recent survey article on Hochschild cohomology and its many important uses in algebra. The Hochschild cohomological dimension of a monoid bounds both its left and right cohomological dimension, but there are examples where all three dimensions are different; see [ 24 , 13 ] . To prove our main results Theorem A and Theorem B we shall need in this paper to introduce and develop an entirely new two-sided analogue of the classical Adjan–Makanin–Zhang theory of special monoids. This makes the results in this paper significantly more difficult than the corresponding one-sided results proved in [ 23 , Section 3] . To give an example of this, implicit in the word of Adjan and Makanin, and explicit in Zhang, is the fundamental result that the right units (dually left units) of a special monoid M is isomorphic to the free product of the group of units and a finite rank free monoid. This algebraic description of the right units is key to relating the structure of special monoids and their groups of units. For the two-sided theory developed in this paper the right units R and left units L are replaced by a single monoid N=\{(x,y)\in R\times L:xy=1\} , which is a submonoid of M\times M^{op} . It turns out, rather miraculously, that for any special monoid M this submonoid N of M\times M^{op} is also isomorphic to a free product of the group of units of M with a finite rank free monoid. Another key ingredient for studying special monoids is the fact, proved in [ 23 , Corollary 3.12] , that any two right Schützenbeger graphs of a special monoid are isomorphic to each other (as directed labelled graph) and that modulo these graphs the Cayley graph has a tree-like structure. This structural description of the right Cayley graph together with results about the left-multiplication action of M on it were then combined in [ 23 , Theorem 3.20] to build a left equivalent classifying space for the monoid from one for its group of units. To prove the two-sided results in this paper we need to establish several new results that give a sufficient level of information about the structure of the two-sided Cayley graph of the monoid and the action of M\times M^{op} upon it. In this way, the results in this paper make new contributions to the theory of special monoids by fully developing, for the first time, the two-sided theory. We note in passing that the success of the theory of special monoids has inspired the development of a parallel theory of special inverse monoids initiated in important work of Ivanov, Margolis and Meakin [ 28 ] and then developed further in several recent papers including [ 18 , 19 , 20 ] . The paper is organised as follows. In Section 2 we give some preliminary definitions and results on presentations, rewriting systems and homological algebra. In Section 3 we give some background on the theory of finitely presented special monoids including results that give normal forms for the elements of the monoid. Section 4 is devoted to proving that the monoid N , discussed above, has the structure of the free product of a group and a free monoid. In Section 5 we prove that M\times M is a free N -set and apply this in Lemma 5.3 to show that the quotient \overleftrightarrow{\Gamma}/N of the two-sided Cayley graph \overleftrightarrow{\Gamma} of M by N is a forest. Section 6 is devoted to the proof that the set E of edges collapsed when forming \overleftrightarrow{\Gamma}/N is a finitely generated free M\times M^{\mathrm{op}} -set. In Section 7 we combine all the results from Sections 4 – 6 together to prove our main results Theorem A and Theorem B. Finally in Section 8 we give a framework for attacking the problem of proving that all one-relator monoids \langle A\mid u=v\rangle , explain how Theorem B deals with an infinite family of base cases for that approach, and also show how to deal with the other infinite family of base cases by showing that if a non-special one-relator monoid M has defining relation u=v such that there is no non-empty word r with u,v\in A^{*}r\cap rA^{*} , then M is of type bi- {\rm FP}_{\infty} and the Hochschild cohomological dimension at most 2 . 2. Preliminaries Presentations and complete rewriting systems We recall some basic definitions and notation for monoid presentations and rewriting systems. For further details we refer the reader to [ 26 , Chapter 12] . Let A be a non-empty set, that we call an alphabet, and let A^{*} denote the free monoid of all words over A . A rewriting system over A is a subset R of A^{*}\times A^{*} . The pair \langle A\mid R\rangle is called a monoid presentation . The elements of R are called rewrite rules of the system, and the defining relations of the presentation. We write u\rightarrow_{R}v for words u,v\in A^{*} if there are words \alpha,\beta\in A^{*} and a rewrite rule (\ell,r)\in R such that u=\alpha\ell\beta and v=\alpha r\beta . We use \rightarrow_{R}^{*} to denote the reflexive transitive closure of \rightarrow_{R} , and write \leftrightarrow_{R}^{*} for the symmetric closure of \rightarrow_{R}^{*} . When the set of rewrite rules with respect to which we are working with is clear from context, we shall often omit the subscript R and simply write \rightarrow , \rightarrow^{*} and \leftrightarrow^{*} . Then \leftrightarrow_{R}^{*} is a congruence on the free monoid A^{*} and the quotient A^{*}/{\leftrightarrow_{R}^{*}} is the monoid defined by the presentation \langle A\mid R\rangle . When working with a monoid M defined by presentation \langle A\mid R\rangle , given two words u,v\in A^{*} we write u=v (or sometimes we write u=_{M}v ) to mean they are equal in M , and we write u\equiv v to indicate that u and v are equal as words in A^{*} , in which case we say the words are graphically equal . Given a rewriting system R over an alphabet A , we say that a word u\in A^{*} is irreducible (or reduced ) if no rewrite rule can be applied to it, that is, there is no word v such that u\rightarrow v . The rewriting system \mathfrak{R} is Noetherian if there is no infinite chain of words u_{i}\in A^{*} with u_{i}\rightarrow u_{i+1} for all i\geq 1 . We say that the rewriting system is confluent if whenever u\rightarrow^{*}u_{1} and u\rightarrow^{*}u_{2} there is a word v\in A^{*} such that u_{1}\rightarrow^{*}v and u_{2}\rightarrow^{*}v . A rewriting system that is both Noetherian and confluent is called complete . If R is a complete rewriting system then each \leftrightarrow^{*} equivalence class contains a unique irreducible word, so in this situation the irreducible words give a set of normal forms for the elements of the monoid that is defined by the presentation \langle A\mid R\rangle . The category of M -sets For any monoid M a left M -set consists of a set X and a mapping M\times X\rightarrow X written (m,x)\mapsto mx called a left action , such that 1x=x and m(nx)=(mn)x for all m,n\in M and x\in X . We define right M -sets dually. Note that right M -sets are the same thing as left M^{op} -sets, where M^{op} is the opposite of the monoid M which is the monoid with the same underlying set M and multiplication given by x\cdot y=yx . An M -biset is an M\times M^{op} -set. We often write (m_{1},m_{2})x=m_{1}xm_{2} in this case. A mapping f\colon X\rightarrow Y between M -sets is said to be M -equivariant if f(mx)=mf(x) for all x\in X , m\in M . For a fixed monoid M the collection M -sets together with M -equivariant mappings form a category. If X is a left M -set and B\subseteq X , then B is said to be a basis for X if and only if each element of X can be expressed uniquely as mb with m\in M and b\in B . Free left M -sets have the usual universal property. The free left M -set on B exists and can be realised as the set M\times B with action m(m^{\prime},b)=(mm^{\prime},b) . Free right M -sets are defined dually. If X is a free left M -set with basis B , then \mathbb{Z}X is a free left \mathbb{Z}M -module with basis B . Given any right M -set X we define a natural preorder relation \leq on X where x\leq y if and only if xM\subseteq yM . We write x\approx y if there is a sequence z_{1},z_{2},\ldots,z_{n} of elements of X such that for each 0\leq i\leq n-1 either z_{i}\leq z_{i+1} or z_{i}\geq z_{i+1} . This is an equivalence relation and we call the \approx -classes of X the weak orbits of the M -set. This corresponds to the notion of the weakly connected components in a directed graph. If X is a right M -set then we use X/M to denote the set of weak orbits of the M -set. Homological algebra Let R be a ring. Then a left R -module V is said to be of type \mathrm{FP}_{n} if it has a projective resolution P_{\bullet}\to V\to 0 such that P_{i} is finitely generated for 0\leq i\leq n . This is equivalent to having a free resolution that is finitely generated through degree n ; see [ 12 , Proposition 4.3] . We say that V is of type {\rm FP}_{\infty} if it has a projective (equivalently, free) resolution that is finitely generated in all degrees. A right R -module is \mathrm{FP}_{n} if it is \mathrm{FP}_{n} as a left R^{op} -module, and we say an R - R -bimodule (called here an R -bimodule) is \mathrm{FP}_{n} if it is \mathrm{FP}_{n} as a left R^{e}=R\otimes_{\mathbb{Z}}R^{op} -module. Note that if M is a monoid, then \mathbb{Z}M^{e}\cong\mathbb{Z}[M\times M^{op}] . We also write \mathrm{FP}_{n}(R) to indicate that we are referring to the ring R in the case that ambiguity might arise. For convenience, all modules will be considered \mathrm{FP}_{-1} . A ring R is of type bi- \mathrm{FP}_{n} if the R -bimodule R is \mathrm{FP}_{n}(R^{e}) . We say that a left R -module V has projective dimension at most d if it has a projective resolution of length d . A monoid M is of type left- \mathrm{FP}_{n} (respectively, right- \mathrm{FP}_{n} ) if the trivial left (respectively, right) module \mathbb{Z} is of type \mathrm{FP}_{n} . Kobayashi and Otto [ 37 ] defined M to be of type bi- \mathrm{FP}_{n} if \mathbb{Z}M is of type bi- \mathrm{FP}_{n} . So, the monoid M is of type bi- {\rm FP}_{n} if there is a projective resolution \cdots\rightarrow P_{1}\rightarrow P_{0}\rightarrow\mathbb{Z}M\rightarrow 0 of the \mathbb{Z}M -bimodule \mathbb{Z}M , where P_{0},P_{1},\ldots,P_{n} are finitely generated projective \mathbb{Z}M -bimodules. If a monoid is of type bi- {\rm FP}_{n} then it is both of type left- {\rm FP}_{n} and right- {\rm FP}_{n} ; see [ 38 , Proposition 4.2] . Kobayashi [ 34 ] proved that if a monoid admits a presentation by a finite complete rewriting system then that monoid must be of type bi- {\rm FP}_{\infty} . See also [ 22 , Section 11] for a topological proof of this using the theory of equivariant collapsing schemes (i.e., discrete Morse theory). The left (right) cohomological dimension of a monoid M is the projective dimension of the trivial left (right) {\mathbb{Z}M} -module \mathbb{Z} . For a group G the right cohomological dimension is equal to the left cohomological dimension and is just called the cohomological dimension of the group and is denoted \mathrm{cd}(G) . The Hochschild cohomological dimension of a monoid M , written \dim M , is the projective dimension of \mathbb{Z}M as a \mathbb{Z}[M\times M^{op}] -module. The Hochschild cohomological dimension bounds both the left and right cohomological dimension of the monoid. We shall need the following result on modules of type \mathrm{FP}_{n} which may be found in [ 4 , Proposition 1.4] . Lemma 2.1 . Let R be a ring. If 0\to A\to B\to C\to 0 is an exact sequence of left R -modules such that A is of type \mathrm{FP}_{n-1} and B is of type \mathrm{FP}_{n} , then C is of type \mathrm{FP}_{n} . We shall also make use of following result about projective dimension of R -modules. The following lemma can be proved by applying [ 10 , Lemma 1.5] ; see [ 23 , Corollary 2.4] . Lemma 2.2 . Let R be a ring and suppose that C_{n}\longrightarrow C_{n-1}\longrightarrow\cdots\longrightarrow C_{0}\longrightarrow V is a partial resolution of an R -module V . Let d\geq n and suppose that C_{n}\to C_{n-1} is injective. If C_{i} has a projective dimension of at most d-i , for 0\leq i\leq n , then V has a projective dimension at most d . In [ 23 , Section 3] a key part of proving results relating the one-sided homological finiteness properties of a special monoid and those of its group of units involved analysing properties of the right and left Cayley graphs of the monoid. In this paper, to study bi- {\rm FP}_{n} and the Hochschild cohomological we shall need to prove results about the structure of the two-sided Cayley graph of the monoid M which is defined as follows. Let M be a monoid generated by a finite set A . Then the two-sided Cayley graph \overleftrightarrow{\Gamma}=\overleftrightarrow{\Gamma}(M,A) of M with respect to A is the directed labelled graph with vertex set M\times M and directed edges M\times A\times M where (m_{1},a,m_{2}) is a directed edge with initial vertex (m_{1},am_{2}) and terminal vertex (m_{1}a,m_{2}) . Just as a monoid acts naturally by left multiplication on its right Cayley graph, there is a natural action of M\times M^{\mathrm{op}} on \overleftrightarrow{\Gamma}=\overleftrightarrow{\Gamma}(M,A) via \displaystyle(m_{1},m_{2})\cdot(x,y)=(m_{1}x,ym_{2}) \displaystyle(m_{1},m_{2})\cdot(x,a,y)=(m_{1}x,a,ym_{2}) where (m_{1},m_{2})\in M\times M^{\mathrm{op}} , x,y\in M and a\in A . These are free M\times M^{\mathrm{op}} -sets with bases \{(1,1)\} and \{1\}\times A\times\{1\} , respectively. The two-sided Cayley graph and this action of M\times M^{\mathrm{op}} will play a central role in the proof of the mains result of this paper. See [ 22 , Section 5.3] for more on the two-sided Cayley graph and its role in the study of two-sided homological and geometric finiteness properties of monoids. 3. Finitely presented special monoids We now give some definitions and results from [ 63 ] that will be used throughout the paper. Let M=\langle A\mid w_{1}=1,\ldots,w_{k}=1\rangle and let G be the group of units of M . By [ 63 , Theorem 3.7] , G has a group presentation with k defining relations. We call a word u\in A^{*} invertible if it represents an element of the group of units G . We say that an invertible word u\in A^{*} is indecomposable if it has no proper prefix that is invertible. It is straightforward to see that every non-empty invertible word u has a unique factorisation u\equiv u_{1}\ldots u_{l} where each u_{j} is non-empty and indecomposable. For each relation word w_{i} in the presentation of M let w_{i}\equiv w_{i,1}\ldots w_{i,n_{i}} be its decomposition into non-empty indecomposable invertible words. Given any invertible word \beta\in A^{+} we call \beta minimal if it is indecomposable, and in addition |\beta|\leq\mathrm{max}_{1\leq i\leq k}|w_{i}| . Now let \Delta be the set of all minimal invertible words \delta\in A^{*} such that \delta=w_{i,j} in M for some 1\leq i\leq n,1\leq j\leq n_{j} . It is immediate from the definition that \Delta is a finite set of indecomposable invertible words. It is proved in [ 63 , Section 3] that the elements represented by words from \Delta give a finite generating set for the group of units G of M . An important result of Zhang [ 63 ] shows how \Delta can be used to give an infinite rewriting system for the monoid M modulo the group of units of M , in the following way. Let <_{s} be the short-lex order on A^{*} induced by some fixed order on the generators A . Then define a rewriting system S=\{u\rightarrow v\mid u,v\in\Delta^{*},u=v\ \mbox{in $M$}\ \mbox{and}\ u>_{s}v\}. It follows from Zhang [ 63 , Proposition 3.2] that S is an infinite complete rewriting system defining the special monoid M . We call a word \alpha\in A^{*} irreducible (or reduced ) if it is irreducible with respect to the rewriting system S . For any word w\in A we shall use \overline{w} to denote the unique reduced word such that w=\overline{w} in M . The following lemma is folklore. Lemma 3.1 . Let T be a monoid and r,s,t\in T with rs and st invertible. Then s and rst are invertible. Proof. First note that rst[(st)^{-1}s(rs)^{-1}]=1 and [(st)^{-1}s(rs)^{-1}]rst=1 , whence rst is invertible. Since rs,st are invertible, s is left and right invertible, hence invertible. ∎ A key result for us is the following. Lemma 3.2 . [ 63 , Lemma 3.4] An irreducible word u\in A^{*} is invertible if and only if u\in\Delta^{*} . Another result that will prove useful later on is the following normal form result of Otto and Zhang [ 51 , Theorem 5.2 and Lemma 5.4] . We shall say a word w\in A^{*} is invertible if it represents an invertible element of M , and trivial if it represents the trivial element of M . We say a subword u of a word w is a maximal invertible subword if u is an invertible word and u is not properly contained in some other invertible subword of w . Lemma 3.1 implies that any non-empty invertible subword u of a word w is contained in a unique maximal invertible subword of w . Lemma 3.3 . [ 51 , Theorem 5.2] Let M=\langle A\mid w_{1}=1,\ldots,w_{k}=1\rangle . Then every word u\in A^{*} can be uniquely factorised as u\equiv u_{0}a_{1}u_{1}\ldots a_{m}u_{m} where, for 0\leq i\leq m , we have a_{i}\in A and u_{i} is a maximal invertible subword of u . We call this the Otto-Zhang normal form of u . Moreover, if v\in A^{*} with u=v in M , then the Otto-Zhang normal form of v is v\equiv v_{0}a_{1}v_{1}\ldots a_{m}v_{m} where u_{i}=v_{i} in M for i=0,\ldots,m . We note that some of the u_{i} and v_{j} in the lemma above may be empty. Lemma 3.4 . Let M=\langle A\mid w_{1}=1,\ldots,w_{k}=1\rangle , let u\in A^{*} and let u\equiv u_{0}a_{1}u_{1}\ldots a_{m}u_{m} be the Otto-Zhang normal form of u . Then \overline{u}\equiv\overline{u_{0}}a_{1}\overline{u_{1}}\cdots a_{m}\overline{u_{m}} and each \overline{u_{i}}\in\Delta^{*} . Moreover, this is the Otto-Zhang normal form of \overline{u} . Proof. To see this, it suffices to show that each \overline{u_{i}} is a maximal invertible subword of v\equiv\overline{u_{0}}a_{1}\overline{u_{1}}\cdots a_{m}\overline{u_{m}} , and that v is reduced. Suppose that w is a maximal invertible subword of v . Since each \overline{u_{j}} is invertible, it follows from Lemma 3.1 that either w\equiv\overline{u}_{i} for some i , or w\equiv\overline{u_{i-1}}a_{i}\cdots a_{k}\overline{u_{k}} for some 1\leq i\leq k\leq m . But in the latter case u_{i-1}a_{i}\cdots a_{k}u_{k} is an invertible word, a contradiction. Thus each \overline{u_{j}} is a maximal invertible subword of v . It now follows that v is reduced since the left-hand side of each rewrite rule is nonempty and invertible, and each maximal invertible subword of v is reduced. Finally, by Lemma 3.2 , each \overline{u_{i}} is a word in \Delta^{*} . ∎ Let us say that a word u\in A^{*} , written in Otto-Zhang normal form u\equiv u_{0}a_{1}u_{1}\ldots a_{m}u_{m} has no invertible suffix if u_{m} represents the identity of M , that is \overline{u_{m}} is empty. We define having no invertible prefix dually. In particular, a nonempty reduced word \mu has no invertible suffix if the Otto-Zhang normal form of \mu is \mu\equiv\mu_{0}a_{1}\mu_{1}\cdots\mu_{n}a_{n} with the a_{i}\in A and the \mu_{i} the maximal invertible subwords of \mu . In particular, \mu is not invertible. There is an obvious dual condition for any nonempty reduced word to have no invertible prefix . 4. Proving that N\cong G\ast C^{*} for some finite set C . Throughout this section M=\langle A\mid w_{1}=1,\ldots,w_{k}=1\rangle. Let R_{1} and L_{1} be the right and left units, respectively, of the monoid M . Let G=R_{1}\cap L_{1} be the group of units of M . Define a monoid N=\{(u,v):u\in R_{1},v\in L_{1},uv=1\} with multiplication (a,b)\cdot(x,y)=(ax,yb). Note that N is a submonoid of R_{1}\times L_{1}^{\mathrm{op}}\subseteq M\times M^{\mathrm{op}} . We remark that while N is a set of pairs of elements of M we shall almost always write elements of N as pairs (u,v) where u,v\in A^{*} . This should of course be interpreted as meaning the pair ([u],[v]) where [u],[v]\in M are the elements of M represented by the words u and v , respectively. By results of Zhang [ 63 , Theorem 4.4] we know that R_{1}\cong G\ast C^{*} for some finite set C , and L_{1}\cong G\ast D^{*} for some finite set D , it follows that N is a submonoid of (G\ast C^{*})\times(G\ast D^{*})^{\mathrm{op}} . This implies that N is group-embeddable, and thus, in particular, N is two-sided cancellative. More generally R_{1}\times L_{1}^{op} is a group-embeddable and thus two-sided cancellative monoid. Our aim in this section is to prove that N\cong G\ast X^{*} for some finite set X . The key to proving this result is to identify a suitable generating set with respect to which we can see that N has this free product structure. Given any invertible word \alpha\in A^{*} we shall use \alpha^{-1} to denote the reduced form of the inverse of the invertible element \alpha . For example when r=(ab)(cd)(ab) then (cd)(ab)=(ab)(cd) is the inverse of ab and it may be verified that (ab)^{-1}=(ab)(cd) is the normal form in this case. By Lemma 3.2 we know that \alpha^{-1}\in\Delta^{*} for every invertible word \alpha\in A^{*} , and if \alpha is itself irreducible, then also \alpha\in\Delta^{*} . Let u,v\in A^{+} be reduced words such that uv=1 in M . Then by definition of the Zhang rewriting system and the fact that u,v are reduced, there must exist factorisations u\equiv u_{1}u_{2} and v\equiv v_{1}v_{2} with u_{2}v_{1}\in\Delta^{*} and u_{2} and v_{1} both nonempty. Of course, u_{2}v_{1} is an invertible word. In general, if u,v are nonempty words, we say that an invertible word z\in A^{+} cuts across (u,v)\in A^{+}\times A^{+} if u\equiv u_{1}u_{2} and v\equiv v_{1}v_{2} with z\equiv u_{2}v_{1} and u_{2},u_{1} nonempty. Let (u,v)\in N with u and v both reduced. It follows from the definitions that u=1 in M if and only if v=1 in M . Otherwise, u\in A^{+} and v\in A^{+} and the argument above shows that at least one invertible word cuts across (u,v) . The collection of invertible words cutting across (u,v) is partially ordered by subword inclusion, as subwords of uv . We aim to show that set of invertible words cutting across (u,v) , if nonempty, is a lattice. Let us prove a more general result first. Proposition 4.1 . Let u\in A^{+} and v be a nonempty subword of u . If some invertible subword of u contains v , then the set of invertible subwords of u containing v is a lattice ordered by subword inclusion. Moreover, if \delta\equiv u_{1}vu_{2} is the unique smallest element of this lattice, then u_{1} has no nonempty invertible prefix and u_{2} has no nonempty invertible suffix. Proof. We being by showing the poset is a lattice. Let x,y\in A^{+} be invertible subwords of u containing v . We must show that x,y have a join and meet in the collection of invertible subwords of v containing u . Write x\equiv x_{1}vx_{2} and y\equiv y_{1}vy_{2} . Without loss of generality assume that |x_{1}|\leq|y_{1}| . If |x_{2}|\leq|y_{2}| , then x is a subword of y and so the meet and join in this case are clearly given by x and y , respectively. So assume that |x_{2}|>|y_{2}| . Then it suffices to show that y_{1}vx_{2} and x_{1}vy_{2} are invertible, as these will then be the meet and join, respectively, of x,y in this poset. Write y_{1}\equiv\alpha x_{1} and x_{2}\equiv y_{2}\beta . Then y_{1}vy_{2}\equiv\alpha x_{1}vy_{2} and x_{1}vx_{2}\equiv x_{1}vy_{2}\beta are invertible, and so x_{1}vy_{2} and y_{1}vx_{2}\equiv\alpha x_{1}vy_{2}\beta are invertible by Lemma 3.1 , as required. For the final statement, if u_{1}\equiv u_{1}^{\prime}u_{1}^{\prime\prime} with u_{1}^{\prime} invertible, then u_{1}^{\prime\prime}vu_{2} is invertible and hence by minimality of u , we must have u_{1}^{\prime\prime}\equiv u_{1} , and so u_{1}^{\prime} is empty. Dually u_{2} has no nonempty invertible suffix. ∎ Proposition 4.2 . Let (u,v)\in A^{+}\times A^{+} . Suppose that some invertible word cuts across (u,v) . Then the poset of invertible words cutting across (u,v) is a lattice. Proof. Let a be the last letter of u and b the first letter of v . Then the invertible words cutting across (u,v) are the subwords of uv containing ab . Therefore, this poset is a lattice by Proposition 4.1 . ∎ Definition 4.3 . Given any pair (\mu,\gamma)\in A^{+}\times A^{+} such that some invertible word cuts across (\mu,\gamma) , we define the height of (\mu,\gamma) to be the height of the lattice of invertible words cutting across (\mu,\gamma) , i.e., the length of the longest chain of invertible words cutting across (\mu,\gamma) . Clearly since the lattice in Definition 4.3 is always finite, it must have finite height, and so the height of a pair of words (\mu,\gamma)\in A^{+}\times A^{+} , such that some invertible word cuts across (\mu,\gamma) , is always finite. We shall later need the following property of height 0 pairs, which is immediate from the final statement of Proposition 4.1 . Lemma 4.4 . Let \mu,\gamma\in A^{*} be reduced with \mu\gamma invertible but \mu noninvertible (or, equivalently, \gamma noninvertible). If (\mu,\gamma) has height 0 , then \mu has no nonempty left invertible prefix and \gamma has no nonempty right invertible suffix. Proof. Write \mu\equiv\mu^{\prime}a and \gamma\equiv b\gamma^{\prime} with a,b\in A . Note that \mu^{\prime} is right invertible and \gamma^{\prime} is left invertible, and so \mu^{\prime} has no nonempty left invertible prefix and \gamma^{\prime} has no nonempty right invertible suffix by Proposition 4.1 . Since \mu and \gamma are also not invertible, but are right and left invertible, respectively, the lemma follows. ∎ We are now ready to provide a finite generating set for N . Lemma 4.5 . The monoid N is finitely generated by the set X\cup Y where Y=\{(\delta,\delta^{-1}):\delta\in\Delta\} and X consists of all pairs (\delta_{1},\delta_{2}\delta^{-1}) such that: (1) \delta_{1},\delta_{2}\in A^{+} are reduced; (2) \delta\equiv\delta_{1}\delta_{2} is invertible; (3) (\delta_{1},\delta_{2}) has height 0 ; (4) \delta_{1} has no invertible suffix. Furthermore these four conditions imply that \delta\equiv\delta_{1}\delta_{2}\in\Delta , and hence the set X is finite. Proof. Let u,v\in A^{*} be reduced with uv=1 in M . We prove by induction on |u| that (u,v)\in\langle X\cup Y\rangle . If u=1 , then since uv=1 in M and v is reduced, we must have v=1 . Proceeding by induction, if |u|>0 , then uv is not reduced (being 1 in M ), and so we can apply a rewrite rule to it. Since u,v are reduced, the left-hand side of any applicable rewrite rule cuts across (u,v) . But the left-hand side of any rewrite rule is invertible and nonempty. Hence there is an invertible word cutting across (u,v) . Let \delta be the minimal invertible word cutting across (u,v) ; this exists by Proposition 4.2 . Write u\equiv u^{\prime}\delta_{1} and v\equiv\delta_{2}v^{\prime} with \delta\equiv\delta_{1}\delta_{2} . Suppose first that \delta_{1} has no invertible suffix. We compute (u,v)=(u^{\prime},\delta v^{\prime})(\delta_{1},\delta_{2}\delta^{-1}) . Note that |u^{\prime}|<|u| and u^{\prime}\delta v^{\prime}\equiv uv , and hence is 1 in M . So (u^{\prime},\delta v^{\prime})\in\langle X\cup Y\rangle by induction, noting that u^{\prime} is a reduced word, whereas (\delta_{1},\delta_{2}\delta^{-1})\in X by minimality of \delta which implies (\delta_{1},\delta_{2}) has height zero. Otherwise, \delta_{1}\equiv\delta_{1}^{\prime}\gamma where \gamma is a nonempty invertible suffix. Since \delta_{1} is reduced, \gamma\in\Delta^{*} by Lemma 3.2 . Therefore, (\gamma,\gamma^{-1})\in\langle Y\rangle . But then (u,v)=(u^{\prime}\delta_{1}^{\prime}\gamma,v)=(u^{\prime}\delta_{1}^{\prime},\overline{\gamma v})(\gamma,\gamma^{-1}) , where u^{\prime}\delta_{1}^{\prime} is a reduced word since it is a subword of the reduced word u . Since u^{\prime}\delta_{1}^{\prime}\overline{\gamma v}=uv=1 in M , and |u^{\prime}\delta_{1}^{\prime}|<|u| , we deduce that (u^{\prime}\delta_{1}^{\prime}\gamma,v)\in\langle X\cup Y\rangle by induction, and hence (u,v)\in\langle X\cup Y\rangle . Finally, we show that conditions (1)–(4) together imply that \delta\equiv\delta_{1}\delta_{2}\in\Delta and hence the set X is finite. There are two cases to consider. First suppose that \delta\equiv\delta_{1}\delta_{2} is not reduced. Since \delta_{1} and \delta_{2} are both reduced by (1) it follows that the left hand side \mu\in\Delta^{+} of some rewrite rule cuts across (\delta_{1},\delta_{2}) . Write \delta_{1}\delta_{2}\equiv\delta_{1}^{\prime}\mu_{1}\mu_{2}\delta_{2}^{\prime} where \delta_{1}\equiv\delta_{1}^{\prime}\mu_{1} , \delta_{2}\equiv\mu_{2}\delta_{2}^{\prime} and \mu_{1}\mu_{2}\in\Delta^{+} with \mu_{1} and \mu_{2} both non-empty words. Since by (4) the word \delta_{1} has no invertible suffix, it follows that \mu_{1}\not\in\Delta^{+} hence there is a word \gamma\in\Delta such that \gamma cuts across (\delta_{1},\delta_{2}) . Since by (3) we have that (\delta_{1},\delta_{2}) has height zero this is only possible if \delta\equiv\delta_{1}\delta_{2}\equiv\gamma\in\Delta . This completes the proof that in this case \delta\equiv\delta_{1}\delta_{2}\in\Delta . Next we consider the case that \delta\equiv\delta_{1}\delta_{2} is reduced. Since \delta_{1}\delta_{2} is reduced, then as it is invertible it belongs to \Delta^{*} by Lemma 3.2 . Since \delta_{1}\notin\Delta^{*} (being noninvertible), the expression of \delta_{1}\delta_{2} as a product of words from \Delta must involve an element \delta^{\prime}\in\Delta cutting across (\delta_{1},\delta_{2}) . Since any element of \Delta is invertible, we deduce that \delta_{1}\delta_{2}\equiv\delta^{\prime}\in\Delta by definition of height 0 . This completes the proof that in this case \delta\equiv\delta_{1}\delta_{2}\in\Delta . We have shown that the conditions (1)–(4) together imply that \delta\equiv\delta_{1}\delta_{2}\in\Delta and hence, since \Delta is finite, the set X is also finite. ∎ Remark 4.6 . The idea behind the height zero condition in the definition of the set X in Lemma 4.5 is to ensure that the generating set obtained in minimal. In particular, if we were to remove the height zero assumption from the set X in Lemma 4.5 then in general it would result in a generating set for N that is not minimal. To see this consider, for example, the monoid M defined by the presentation \langle a,b,c,d\mid(abcd)(bc)(abcd)=1\rangle . It is straightforward to verify that the minimal invertible pieces of this defining relator are abcd and bc . Consider the following three elements from N (b,c(bc)^{-1}),\quad(ab,cd(abcd)^{-1}),\quad(a,bcd(abcd)^{-1}). All three of theses elements has the form (\delta_{1},\delta_{2}\delta^{-1}) where \delta\equiv\delta_{1}\delta_{2}\in\Delta since it may be shown that bc\in\Delta and abcd\in\Delta . However, if we included all three of these generators in a generating set for N then that generating set would not be minimal since (a,bcd(abcd)^{-1})\cdot(b,c(bc)^{-1})=(ab,c(bc)^{-1}bcd(abcd)^{-1})=(ab,cd(abcd)^{-1}). Note that the pair (ab,cd(abcd)^{-1}) does not have height zero, and the product above shows that this element can be written as a product of the two height zero elements (a,bcd(abcd)^{-1}) and (b,c(bc)^{-1}) . We are now in a position to prove that N decomposes as a free product of its group of units and a free monoid of finite rank. Let us recall briefly the normal form for a free product. Suppose that \{M_{i}:i\in I\} is a collection of monoids. Consider the alphabet B=\bigsqcup_{i\in I}M_{i}\setminus\{1\} . An element of M_{i}\setminus\{1\} is called an M_{i} -syllable or a syllable of type M_{i} . A word in B^{*} is in normal form if it does not contain two consecutive syllables of the same type. The length of a normal form is called its syllable length. Each element of the free product \Asterisk_{i\in I}M_{i} has a unique representative in normal form. The following is a variant of the Ping Pong Lemma. Lemma 4.7 (Ping Pong Lemma) . Let N be a cancellative monoid, G a subgroup of the group of units of N and X\subseteq N . Suppose that N=\langle G\cup X\rangle and there is a right N -set A such that A=A_{0}\sqcup\bigsqcup_{x\in X}Ax with Axg\subseteq A_{0} whenever x\in X and 1\neq g\in G , and Ax\subsetneq A . Then \langle X\rangle is a free monoid with basis X and N\cong G\ast X^{*} . Proof. First note that if X=\emptyset , then N=G and there is nothing to prove. So we may assume that X\neq\emptyset . For each x\in X if x^{i}=x^{j} for some i,j\in\mathbb{N} with i>j then since N is a cancellative monoid this would imply x^{i-j}=1 and thus x is invertible. But if x were invertible it would imply Ax=A contradicting the hypotheses of the lemma. Hence, each x\in X generates a free submonoid x^{*} . We want to show that N\cong G\ast\Asterisk_{\begin{subarray}{c}x\in X\end{subarray}}x^{*} . By assumption, the natural map from the free product to N is surjective. The action of N on A inflates to G\ast\Asterisk_{\begin{subarray}{c}x\in X\end{subarray}}x^{*} via this natural map. First note that if an element \alpha of the free product G\ast\Asterisk_{\begin{subarray}{c}x\in X\end{subarray}}x^{*} is in normal form with last syllable of type x^{*} , then A\alpha\subseteq Ax . If \alpha has last syllable of type G , there are two cases. If \alpha\in G\setminus\{1\} , then A\alpha=A and Ax\alpha\subseteq A_{0} for all x\in X ; if \alpha=\alpha^{\prime}x^{k}g with x\in X , k>0 and g\in G\setminus\{1\} , then A\alpha\subseteq A_{0} . It follows that if \alpha is a nonempty normal form, then it acts nontrivially on A , and we can determine the type of its last syllable from its action on A . Suppose that \alpha and \beta are normal forms for the free product. We induct on the sum of their syllable lengths to show that if \alpha and \beta represent the same element of N , then they are equal in the free product. By the previous paragraph, we may assume that \alpha and \beta are nonempty and their last syllables have the same type. Suppose first that \alpha=\alpha^{\prime}x^{k} and \beta=\beta^{\prime}x^{m} with x\in X and \alpha^{\prime},\beta^{\prime} of one shorter syllable length. Without loss of generality assume that k\leq m . Then cancelling x^{k} we get \alpha^{\prime} and \beta^{\prime}x^{m-k} represent the same element of N . By induction, since \alpha^{\prime} does not end in an x^{*} -syllable, we must have that m=k and \alpha^{\prime}=\beta^{\prime} in the free product. Next suppose that \alpha=\alpha^{\prime}g and \beta=\beta^{\prime}g^{\prime} where g,g^{\prime}\in G\setminus\{1\} and \alpha^{\prime},\beta^{\prime} have syllable length one shorter. Then \alpha^{\prime}=\beta^{\prime}g^{\prime}g^{-1} in N . Since \alpha^{\prime} does not end in a G -syllable, we deduce by induction that g^{\prime}g^{-1}=1 and \alpha^{\prime}=\beta^{\prime} in the free product. This completes the proof. ∎ We now apply the Ping Pong Lemma to our setting. Theorem 4.8 . The monoid N is isomorphic to a free product G\ast C^{*} where G is the group of units of M and C is a finite set. More precisely, let X\cup Y be the finite generating set for N obtained in Lemma 4.5 . Then X is a basis for a free submonoid of N and N\cong G\ast X^{*} where the copy of G is identified with \langle Y\rangle . Proof. Note that if \mu,\gamma\in A^{*} are reduced with \mu non-empty, and with \mu\gamma invertible and with \mu having no invertible suffix, then \mu is right invertible, but not invertible. We prove the free product decomposition using the Ping Pong Lemma applied to the right action of N on itself. We know that N is generated by X\cup Y by Lemma 4.5 . We have already pointed out that N is cancellative. Note that if x=(\delta_{1},\delta_{2}\delta^{-1})\in X with \delta_{1}\delta_{2}\equiv\delta\in\Delta and \delta_{1} having no invertible suffix, then \delta_{1} is right invertible (as \delta is invertible), and hence is not left invertible. It follows that x is not left invertible, and so Nx\subsetneq N for all x\in X . We now prove that the collection \{Nx:x\in X\} is pairwise disjoint. Let \pi\in N with \pi=(\pi_{\ell},\pi_{r}) with \pi_{\ell},\pi_{r} reduced words. If (\mu,\gamma\tau^{-1})\in X with \mu\gamma\equiv\tau\in\Delta , we shall show that we can uniquely recover (\mu,\gamma\tau^{-1}) from (\pi_{\ell}\mu,\gamma\tau^{-1}\pi_{r})=\pi(\mu,\gamma\tau^{-1}) . We need a claim in order to do this. We continue to write \overline{w} for the reduced form of w . Claim 1 . Let \pi=(\pi_{\ell},\pi_{r})\in N with \pi_{\ell},\pi_{r} reduced, (\mu,\gamma\tau^{-1})\in X with \tau\equiv\mu\gamma and \delta\in\Delta^{*} reduced. Then \pi(\mu,\gamma\tau^{-1})(\delta,\delta^{-1})=(\pi_{\ell}\mu\delta,\delta^{-1}\gamma\overline{\tau^{-1}\pi_{r}}) and \pi_{\ell}\mu\delta and \gamma\overline{\tau^{-1}\pi_{r}} are both reduced. Proof of Claim 1 . By assumption \pi_{\ell} , \pi_{r} and \delta are reduced. The words \mu,\gamma are reduced by the definition of X in Lemma 4.5 . First we observe that \pi_{\ell}\mu is reduced. This follows since \pi_{\ell} and \mu are reduced, and no rewrite rule can be applied with the left-hand side of the rewrite rule including both letters in \pi_{\ell} and in \mu since the left-hand side of every rewrite rule belongs to \Delta^{+} , and hence is invertible, and that would then give a nonempty left invertible prefix of \mu , something we already observed in Lemma 4.4 it does not have. Dually, \gamma\overline{\tau^{-1}\pi_{r}} is reduced because no rewrite rule can be applied to \gamma or \overline{\tau^{-1}\pi_{r}} since they are reduced, and furthermore, any rewrite rule applied across both of these words (i.e., involving letters from both of them) would contradict the fact (proved in Lemma 4.4 ) that \gamma has no nonempty right invertible suffix, as the left-hand side of any rewrite rule is nonempty and invertible. Finally we show that \pi_{\ell}\mu\delta is reduced. Since the left hand side of any rewrite rule is nonempty and invertible, and as \pi_{\ell}\mu and \delta are reduced, it is enough to show that \delta is a maximal invertible subword of \pi_{\ell}\mu\delta by Lemma 3.4 . By definition of the generating set X the word \mu does not have an invertible suffix. It follows that there is no suffix \mu^{\prime\prime} of \mu such that \mu^{\prime\prime}\delta is invertible. A word of the form \sigma\mu\delta cannot be invertible since if it were, then \sigma\mu would be invertible, implying \mu is left invertible which is a contradiction, since it is right invertible but not invertible. This completes the proof of the claim. ∎ From Claim 1 it follows that \pi_{\ell}\mu and \gamma\overline{\tau^{-1}\pi_{r}} are reduced. We now recover (\mu,\gamma\tau^{-1}) uniquely from (\pi_{\ell}\mu,\gamma\overline{\tau^{-1}\pi_{r}}) in the following way. Consider all the invertible words cutting across this pair. There is at least one such word since \mu\gamma is invertible and \mu and \gamma are both non-empty words by definition of X . By Proposition 4.2 the set of invertible words cutting across this pair is a lattice under inclusion. We claim that the word \mu\gamma is the unique minimal element of this lattice. This word is minimal because, by definition of X , the pair (\mu,\gamma) has height zero. In a lattice minimal elements are unique. It follows that we can recover (\mu,\gamma\tau^{-1}) from (\pi_{\ell}\mu,\gamma\overline{\tau^{-1}\pi_{r}}) , and hence the collection \{Nx:x\in X\} is pairwise disjoint. Let N_{0} be the complement of \bigsqcup_{x\in X}Nx . By the Ping Pong Lemma, it remains to show that Nx(g,g^{-1})\subseteq N_{0} for all x\in X and g\neq 1 in G . Indeed, let x=(\mu,\gamma\tau^{-1})\in X , and let \delta\in\Delta^{*} be reduced representing g , whence \delta is nonempty. Let \pi=(\pi_{\ell},\pi_{r})\in N with \pi_{\ell},\pi_{r} reduced. Then \pi x(g,g^{-1})=(\pi_{\ell}\mu\delta,\delta^{-1}\gamma\tau^{-1}\pi_{r}) and \pi_{\ell}\mu\delta is reduced by Claim 1 . Now if \pi x(g,g^{-1})=\pi^{\prime}x^{\prime} with \pi^{\prime}=(\pi_{\ell}^{\prime},\pi_{r}^{\prime})\in N , x^{\prime}=(\mu^{\prime},\gamma^{\prime}(\tau^{\prime})^{-1})\in X , \tau^{\prime}\equiv\mu^{\prime}\gamma^{\prime}\in\Delta and \pi_{\ell}^{\prime},\pi_{r}^{\prime} reduced, then we would have \pi^{\prime}x^{\prime}=(\pi_{\ell}^{\prime}\mu^{\prime},\gamma^{\prime}(\tau^{\prime})^{-1}\pi_{r}^{\prime}) with \pi_{\ell}^{\prime}\mu^{\prime} reduced by Claim 1 . Thus \pi_{\ell}^{\prime}\mu^{\prime}\equiv\pi_{\ell}\mu\delta . We cannot have \delta as a suffix of \mu^{\prime} since \mu^{\prime} has no invertible suffix and \delta is nonempty. If \mu^{\prime} is a suffix of \delta , then it is left invertible, but it is also right invertible since \mu^{\prime}\gamma^{\prime} is invertible. This contradicts that \mu^{\prime} has no invertible suffix. Thus \pi x(g,g^{-1})\in N_{0} . This completes the proof that X freely generates X^{*} and N\cong G\ast X^{*} by the Ping Pong Lemma. ∎ 5. Proving M\times M is a free N -set As in the previous section, throughout this section M=\langle A\mid w_{1}=1,\ldots,w_{k}=1\rangle. For the next part of the argument we want to prove that M\times M is a free right N -set under the action (m_{1},m_{2})\cdot(n_{1},n_{2})=(m_{1}n_{1},n_{2}m_{2}), where (m_{1},m_{2})\in M\times M and (n_{1},n_{2})\in N . Note that in the above situation we have m_{1}m_{2}=m_{1}n_{1}n_{2}m_{2} in M since n_{1}n_{2}=1 by definition of N . So we are always working with respect to some fixed element of M when studying this action. We shall need the following remark. If S is a cancellative monoid and X is a free right S -set, then xs=xs^{\prime} implies s=s^{\prime} for x\in X and s,s^{\prime}\in S , and dually for free left S -sets. Indeed, this is true for the right action of S on itself by cancellativity, and a free S -set is a disjoint union of copies of the action of S on itself. Our aim in this section is to prove the following result. Note the basis in the following theorem is not finite, but we do not expect nor need it to be so. Theorem 5.1 . The set M\times M is a free right N -set under the action (m_{1},m_{2})\cdot(n_{1},n_{2})=(m_{1}n_{1},n_{2}m_{2}), where (m_{1},m_{2})\in M\times M and (n_{1},n_{2})\in N . In more detail, let \displaystyle\mathcal{B}=\{(\alpha_{1},\alpha_{2}):\mbox{$\alpha_{1}\alpha_{2}\equiv\alpha$ is a reduced word and $\alpha$} has Otto-Zhang normal form \alpha\equiv w_{0}a_{1}w_{1}\cdots a_{m}w_{m} with \alpha_{1}\equiv w_{0}a_{1}\cdots wa_{i-1} and \alpha_{2}\equiv w_{i-1}a_{i}\cdots a_{m}w_{m} \displaystyle\mbox{for some $1\leq i\leq m+1$}\}. Then M\times M is a free right N -set with basis \mathcal{B} . Proof. Let u,v\in A^{*} be reduced words and let uv\equiv w_{0}a_{1}\cdots a_{m}w_{m} in Otto-Zhang normal form. Suppose, moreover, that u\equiv w_{0}a_{0}\cdots w_{i-2}a_{i-1}w_{i-1}^{\prime} and v\equiv w_{i-1}^{\prime\prime}a_{i}\cdots a_{m}w_{m} where w_{i-1}\equiv w_{i-1}^{\prime}w_{i-1}^{\prime\prime} . Note that for j\neq i-1 , we have that w_{j} is reduced and hence belongs to \Delta^{*} by Lemma 3.2 . Also, \overline{uv}=w_{0}a_{1}\cdots a_{i-1}\overline{w_{i-1}}a_{i}\cdots a_{m}w_{m} by Lemma 3.4 . It follows that (u^{\prime},v^{\prime})\in\mathcal{B} where u^{\prime}\equiv w_{0}a_{1}\cdots w_{i-2}a_{i-1} and v^{\prime}\equiv\overline{w_{i-1}}a_{i}\cdots a_{m}w_{m} . We claim that (u,v)\in(u^{\prime},v^{\prime})N . Indeed, note that (w_{i-1}^{\prime},w_{i-1}^{\prime\prime}w_{i-1}^{-1})\in N and (u^{\prime},v^{\prime})(w_{i-1}^{\prime},w_{i-1}^{\prime\prime}w_{i-1}^{-1})=(u^{\prime}w_{i-1}^{\prime},w_{i-1}^{\prime\prime}w_{i-1}^{-1}w_{i-1}a_{i}\cdots a_{m}w_{m})=(u,v), as required. We conclude that \mathcal{B} is a generating set for M\times M as a right N -set. It remains, to show each element of M\times M has only one expression in the form (\alpha_{1},\alpha_{2})(n_{1},n_{2}) with (\alpha_{1},\alpha_{2})\in\mathcal{B} and (n_{1},n_{2})\in N . Suppose that (\alpha_{1},\alpha_{2})\in\mathcal{B} and let x,y be reduced words with xy=1 . We show that (\alpha_{1},\alpha_{2}) can be recovered from the right-hand side of (\alpha_{1},\alpha_{2})(x,y)=(\alpha_{1}x,y\alpha_{2}) . Note that by definition of \mathcal{B} , \alpha_{1} has no invertible suffix. First we claim that \alpha_{1}x is reduced. Indeed, since \alpha_{1} and x are reduced, any rewrite rule that is applicable must cut across (\alpha_{1},x) . Since the left-hand side of a rewrite rule is nonempty and invertible, this means we can write \alpha_{1}\equiv\alpha\beta and x\equiv\gamma\delta with \beta\gamma invertible and \beta , \gamma nonempty. Since x is right invertible, we deduce that \gamma is invertible and hence \beta is invertible, contradicting that \alpha_{1} has no invertible suffix. Consider (\alpha_{1}x,\overline{y\alpha_{2}}) . Let \mu be the longest invertible word that cuts across (\alpha_{1}x,\overline{y\alpha_{2}}) if such a word exists, while if no such word exists then let \mu be the longest invertible suffix of \alpha_{1}x , which could possibly be empty. We claim that \alpha_{1}x\overline{y\alpha_{2}}\equiv\alpha_{1}\mu\nu with \overline{\mu\nu}=\alpha_{2} . It will then follow that we can recover (\alpha_{1},\alpha_{2}) from (\alpha_{1},\alpha_{2})(x,y) . Indeed, to prove the claim let \alpha_{1}\alpha_{2}\equiv w_{0}a_{0}\cdots a_{m}w_{m} in Otto-Zhang normal form. By Lemma 3.4 , each w_{j} is reduced and in \Delta^{*} . Then by definition of \mathcal{B} , we have some i with \alpha_{1}\equiv w_{0}a_{0}\cdots w_{i-2}a_{i-1} and \alpha_{2}\equiv w_{i-1}a_{i}\cdots a_{m}w_{m} . Then \alpha_{1}xy\alpha_{2}\equiv w_{0}a_{0}\cdots w_{i-2}a_{i-1}xyw_{i-1}a_{i}\cdots a_{m}w_{m} . By Lemma 3.1 , it follows that any maximal invertible subword of \alpha_{1}xy\alpha_{2} is either a maximal invertible subword of \alpha_{1} , \alpha_{2} or contains xy . But since xy=1 in M and w_{i-1} is maximal invertible in \alpha_{1}\alpha_{2} , it follows that xyw_{i-1} is the maximal invertible subword of \alpha_{1}xy\alpha_{2}\equiv w_{0}a_{0}\cdots w_{i-2}a_{i-1}xyw_{i-1}a_{i}\cdots a_{m}w_{m} containing xy . Since every maximal invertible subword of \alpha_{1}xy\alpha_{2} is either a maximal invertible subword of \alpha_{1} , \alpha_{2} or contains xy , it follows that the Otto Zhang normal form of the word \alpha_{1}xy\alpha_{2} is \alpha_{1}xy\alpha_{2}\equiv w_{0}a_{0}\cdots w_{i-2}a_{i-1}(xyw_{i-1})a_{i}\cdots a_{m}w_{m} where the maximal invertible subwords in this normal form are the words w_{0},\ldots,w_{i-2},xyw_{i-1},w_{i},\ldots,w_{m}. Since xyw_{i-1} is invertible it follows that yw_{i-1} is left invertible. Since a_{i}w_{i}\cdots a_{m}w_{m} has no invertible prefix it follows that no invertible word cuts across the pair (yw_{i-1},a_{i}w_{i}\cdots a_{m}w_{m}). Indeed, if \sigma\equiv\sigma_{1}\sigma_{2} were an invertible word that cuts across this pair with \sigma_{2} a prefix of a_{i}w_{i}\cdots a_{m}w_{m} , then \sigma_{1} is left invertible since it is a suffix of the left invertible word yw_{i-1} , and \sigma_{1} is right invertible since it is a prefix of the invertible word \sigma . Then \sigma_{1} and \sigma are invertible and thus \sigma_{2} is an invertible prefix of a_{i}w_{i}\cdots a_{m}w_{m} which is a contradiction. It follows that every invertible subword of the word yw_{i-1}a_{i}w_{i}\cdots a_{m}w_{m} is contained in either a subword of yw_{i-1} or else is a subword of a_{i}w_{i}\cdots a_{m}w_{m} . It follows that the Otto-Zhang normal form of y\alpha_{2} is graphically equal to the product of the Otto-Zhang normal form of yw_{i-1} and \nu:=a_{i}w_{i}\cdots a_{m}w_{m} . We conclude from Lemma 3.4 that \overline{y\alpha_{2}}\equiv\overline{yw_{i-1}}a_{i}w_{i}\cdots a_{m}w_{m} . Then \alpha_{1}x\overline{y\alpha_{2}}\equiv w_{0}a_{0}\cdots w_{i-2}a_{i-1}x\overline{yw_{i-1}}a_{i}w_{i}\cdots a_{m}w_{m}. Now there are two cases. If there is an invertible word that cuts across (\alpha_{1}x,\overline{y\alpha_{2}}) then it follows that \mu=x\overline{yw_{i-1}} since xy=1 , x\overline{yw_{i-1}} is invertible, and w_{i-1} is a maximal invertible subword of \alpha_{1}\alpha_{2} . Therefore, \alpha_{1}\overline{y\alpha_{2}}\equiv\alpha_{1}\mu\nu and \overline{\mu\nu}=\alpha_{2} . In the other case there is no invertible word that cuts across (\alpha_{1}x,\overline{y\alpha_{2}}) . In this case since x\overline{yw_{i-1}} is invertible, either x is empty or \overline{yw_{i-1}} is empty. If x is empty then y is also empty since xy=1 and x and y are reduced. Therefore, (\alpha_{1}x,\overline{y\alpha_{2}})=(\alpha_{1},\alpha_{2}) , and by definition of \mathcal{B} the word \alpha_{1} has no non-trivial invertible suffix, so \mu is empty. So we recover \alpha_{2}=\nu=\overline{\mu\nu} . Otherwise, \overline{yw_{i-1}} is the empty word so \alpha_{1}x\overline{y\alpha_{2}}\equiv w_{0}a_{0}\cdots w_{i-2}a_{i-1}xa_{i}w_{i}\cdots a_{m}w_{m}. In this case in M we have x=xyw_{i-1}=w_{i-1} . In particular x is invertible. Furthermore \alpha_{1}x\equiv w_{0}a_{0}\cdots w_{i-2}a_{i-1}x Suppose that x is not the longest invertible suffix of the word \alpha_{1}x ; say, e.g., z is a longer such suffix. Then since xyw_{i-1} and z are both invertible with x a suffix of z , it would follow from Lemma 3.1 that zyw_{i-1} is an invertible word strictly containing xyw_{i-1} contradicting the fact proved above that xyw_{i-1} is a maximal invertible subword of \alpha_{1}xy\alpha_{2} . Hence in this case x is the longest invertible suffix of the word \alpha_{1}x . So by definition \mu\equiv x and \alpha_{1}x\overline{y\alpha_{2}}\equiv\alpha_{1}xa_{i}w_{i}\cdots a_{m}w_{m}\equiv\alpha_{1}\mu\nu and \overline{\mu\nu}=\overline{xa_{i}w_{i}\cdots a_{m}w_{m}}=\overline{w_{i-1}a_{i}w_{i}\cdots a_{m}w_{m}}=\alpha_{2} since in this case, as we saw above, x=w_{i-1} in M . This completes the proof that we can recover (\alpha_{1},\alpha_{2}) from (\alpha_{1},\alpha_{2})(x,y) . Next suppose that (\alpha_{1},\alpha_{2})\in\mathcal{B} and (\alpha_{1},\alpha_{2})(x,y)=(\alpha_{1},\alpha_{2})(x^{\prime},y^{\prime}) with (x,y) and (x^{\prime},y^{\prime})\in N . We show that (x,y)=(x^{\prime},y^{\prime}) . Indeed, by Corollary [ 23 , Corollary 3.8] , M is a free right R_{1} -set and a free left L_{1} -set. Note that R_{1},L_{1} are cancellative monoids. Hence the equations \alpha_{1}x=\alpha_{1}x^{\prime} and y\alpha_{2}=y^{\prime}\alpha_{2} imply that x=x^{\prime} and y=y^{\prime} , as required. ∎ Remark 5.2 . Let u,v\in A^{*} be reduced. Write \displaystyle uv \displaystyle\equiv \displaystyle w_{0}a_{1}w_{1}\ldots a_{m}w_{m} as in the statement of Lemma 3.3 , where for 0\leq i\leq m we have a_{i}\in A and w_{i} is a maximal invertible subword of w (where some of the w_{i} could be the empty word). Suppose that \displaystyle u \displaystyle\equiv w_{0}a_{1}\cdots w_{i-2}a_{i-1}w_{i-1}^{\prime} \displaystyle v \displaystyle\equiv w_{i-1}^{\prime\prime}a_{i}w_{i}\cdots a_{m}w_{m} with w_{i-1}\equiv w_{i-1}^{\prime}w_{i-1}^{\prime\prime} . The proof of Theorem 5.1 shows that (u,v) is in the weak N -orbit of the basis element (w_{0}a_{1}\cdots w_{i-2}a_{i-1},\overline{w_{i-1}}a_{i}\cdots a_{m}w_{m}) . Since the set M\times M is a free right N -set Theorem 5.1 , the observation in the previous paragraph provides a characterisation of exactly when two pairs (u_{1},v_{1}) and (u_{2},v_{2}) belong to the same weak N -orbit of the free right N -set M\times M . Indeed, (u_{1},v_{1}) and (u_{2},v_{2}) belong to the same weak N -orbit if and only if the basis elements from \mathcal{B} obtained from (u_{1},v_{1}) and from (u_{2},v_{2}) via the process described in the previous paragraph are the same. This description of the weak N -orbits of M\times M will be used in several arguments below. Recall from the preliminaries section above that if a monoid N acts on the right of a set A , then the weak orbits of N on A are the equivalence classes under the smallest equivalence relation on A such that a,an are equivalent for all a\in A and n\in N . We recall for the benefit of the reader that \mathbb{Z}A\otimes_{\mathbb{Z}N}\mathbb{Z} is a free abelian group with basis the set of weak orbits of N on A via the map sending a\otimes 1 to its weak orbit. An important consequence of Theorem 5.1 and Remark 5.2 is that \overleftrightarrow{\Gamma}/N is a forest, where \overleftrightarrow{\Gamma} is the two-sided Cayley graph of M and \overleftrightarrow{\Gamma}/N is the graph obtained by collapsing the induced subgraph on each weak orbit of N on the vertices of \overleftrightarrow{\Gamma} to a point. So \overleftrightarrow{\Gamma}/N has vertex set (M\times M)/N and edge set consisting of those edges e of \overleftrightarrow{\Gamma} with initial vertex \iota(e) in a different weak N -orbit than terminal vertex \tau(e) . The corresponding edge of \overleftrightarrow{\Gamma}/N goes from [\iota(e)] to [\tau(e)] where [(m,m^{\prime})] denotes the weak N -orbit of (m,m^{\prime})\in M\times M . There is an M\times M^{op} -equivariant cellular map \overleftrightarrow{\Gamma}\to\overleftrightarrow{\Gamma}/N sending a vertex to its class, crushing the edges between vertices of the same weak N -orbit to a point and sending the remaining edges to themselves (viewed as edges of \overleftrightarrow{\Gamma}/N ). Note that if [(m_{1},m_{2})]=[(m_{1}^{\prime},m_{2}^{\prime})] , then m_{1}m_{2}=m_{1}^{\prime}m_{2}^{\prime} . It follows that the map \overleftrightarrow{\Gamma}\to\overleftrightarrow{\Gamma}/N factors through the map \overleftrightarrow{\Gamma}\to\pi_{0}(\overleftrightarrow{\Gamma})\cong M , and so \pi_{0}(\overleftrightarrow{\Gamma}/N) is identified with M . Lemma 5.3 . The quotient \overleftrightarrow{\Gamma}/N of the two-sided Cayley graph \overleftrightarrow{\Gamma} of M by N is a forest. Proof. Let m\in M and consider the component corresponding to m in \overleftrightarrow{\Gamma}/N . Let w be the reduced word that equals m . Write w\equiv w_{0}a_{1}w_{1}\ldots a_{m}w_{m} in Otto-Zhang normal form where the w_{i} are maximal invertible subwords (possibly empty, and all in \Delta^{*} ) and all a_{i}\in A , as in the statement of Lemma 3.3 . Let w^{\prime}\equiv a_{1}a_{2}\ldots a_{m} . We claim that the m -component of \overleftrightarrow{\Gamma}/N is isomorphic as a labelled graph to the linear automaton \mathcal{A}(w^{\prime}) for w^{\prime} with vertex set 0,\ldots,m and an edge labelled by a_{i} from i-1 to i for 1\leq i\leq m . It will then follow that \overleftrightarrow{\Gamma}/N is a forest. Define a cellular map from the m -component of \overleftrightarrow{\Gamma} to A(w^{\prime}) as follows. If \alpha_{1},\alpha_{2}\in A^{*} are reduced with \alpha_{1}\alpha_{2}=m , then \alpha_{1}\equiv w_{0}a_{1}\cdots w_{i-2}a_{i-1}w_{i-1}^{\prime} and \alpha_{2}\equiv w_{i-1}^{\prime\prime}a_{i}w_{i}\cdots a_{m}w_{m} with \overline{w_{i-1}^{\prime}w_{i-1}^{\prime\prime}}=w_{i-1} by Lemma 3.3 and Lemma 3.4 . Both w_{i-1}^{\prime} and w_{i-1}^{\prime\prime} can be empty. Send (\alpha_{1},\alpha_{2}) to i-1 . Notice in particular that the basis element (w_{0}a_{1}\cdots w_{i-2}a_{i-1},w_{i-1}a_{i}w_{i}\cdots a_{m}w_{m}) is sent to i-1 , and so this map is surjective on vertices. By Remark 5.2 , this map factors through (M\times M)/N , and the induced map is injective on vertices. An edge in the m -component of \overleftrightarrow{\Gamma} has the form (\mu,a,\gamma) where \mu,\gamma\in A^{*} are reduced, a\in A and \mu a\gamma=m . By Lemma 3.3 and Lemma 3.4 , we have two cases. The first is that \mu\equiv w_{0}a_{0}\cdots w_{i-2}a_{i-1}w_{i-1}^{\prime} , \gamma\equiv w_{i-1}^{\prime\prime}a_{i}\cdots a_{m}w_{m} where \overline{w_{i-1}^{\prime}aw_{i-1}^{\prime\prime}}=w_{i-1} . In this case, by Remark 5.2 , this edge is between two vertices in the same weak N -orbit, namely that of the basis element (w_{0}a_{0}\cdots w_{i-2}a_{i-1},w_{i-1}a_{i}\cdots a_{m}w_{m}) . The second case is that \mu\equiv w_{0}a_{0}\cdots w_{i-1} , \gamma\equiv w_{i}\cdots a_{m}w_{0} and a=a_{i} . In this case, initial vertex is in the weak N -orbit of the basis element (w_{0}a_{0}\cdots a_{i-1},w_{i-1}a_{i}\cdots a_{m}w_{m}) , whereas the terminal vertex is in the weak N -orbit of the basis element (w_{0}\cdots w_{i-1}a_{i},w_{i}\cdots a_{m}w_{m}) . We map the corresponding edge of \overleftrightarrow{\Gamma}/N to the edge labeled a_{i} from i-1 to i . This completes the proof of the isomorphism. ∎ 6. Proving the set of collapsed edges is a finitely generated free M\times M^{\mathrm{op}} -set As in the previous section, throughout this section M=\langle A\mid w_{1}=1,\ldots,w_{k}=1\rangle. Up to this point we have proved that: • N\cong G\ast C^{*} for some finite set C where G is the group of units of M . • M\times M is a free N -set, with basis \mathcal{B} defined above, under the action (m_{1},m_{2})\cdot(n_{1},n_{2})=(m_{1}n_{1},n_{2}m_{2}). The final thing we need to prove is that the set E of edges collapsed when forming \overleftrightarrow{\Gamma}/N is a finitely generated free M\times M^{\mathrm{op}} -set. More precisely, we want to consider the edges E of the two-sided Cayley graph \overleftrightarrow{\Gamma} between vertices in the same weak N -orbit of M\times M . Then M\times M^{\mathrm{op}} acts on this set E of edges via (m_{1},m_{2})\cdot(u,a,v)=(m_{1}u,a,vm_{2}) where (m_{1},m_{2})\in M\times M^{\mathrm{op}} , a\in A and u,v,m_{1},m_{2} are reduced words over A . Drawing an analogy with our argument in [ 23 ] the edges E are the analogue of edges between vertices in the same \mathrel{\mathscr{R}} -class in that argument, and N is playing the role of R_{1} – the right units. Note however that N is not in general the submonoid of right units of the monoid M\times M^{\mathrm{op}} . With the above definitions we want to prove the following. Theorem 6.1 . Let E be the set of edges of the two-sided Cayley graph \overleftrightarrow{\Gamma} between vertices in the same weak N -orbit. Then E is a finitely generated free left M\times M^{\mathrm{op}} -set under the action (m_{1},m_{2})\cdot(u,a,v)=(m_{1}u,a,vm_{2}) for (m_{1},m_{2})\in M\times M^{\mathrm{op}} and (u,a,v)\in E , with finite basis \displaystyle\mathcal{C}=\{(\delta_{1},a,\delta_{2}):\delta_{1}a\delta_{2}\ \text{is invertible},\ a\in A,\ \delta_{1},\ \delta_{2}\in A^{*}\ \text{are reduced}, \displaystyle\mbox{and no proper invertible subword of $\delta_{1}a\delta_{2}$ contains this $a$}\}. Furthermore, if (\delta_{1},a,\delta_{2})\in\mathcal{C} then \delta_{1}a\delta_{2}\in\Delta . Proof. Let (u,a,v) be an edge with u,v\in A^{*} reduced, and let uav\equiv w_{0}a_{1}\cdots a_{m}w_{m} in Otto-Zhang normal form. First of all we claim that (u,a,v)\in E if and only if the distinguished occurrence of a is not any of the a_{i} . Suppose first that a_{i} is the distinguished occurrence of a for some i , then uav is reduced by Lemma 3.4 (since u,v are reduced, and hence their subwords w_{j} are reduced) and \displaystyle(u,av) \displaystyle=(w_{0}a_{1}\cdots a_{i-1}w_{i-1},a_{i}\cdots a_{m}w_{m}) and \displaystyle(ua,v) \displaystyle=(w_{0}\cdots w_{i-1}a_{i},w_{i}a_{i+1}\cdots a_{m}w_{m}) are in different weak N -orbits by Remark 5.2 , as (ua,v) is a basis element and (w_{0}a_{1}\cdots a_{i-1},w_{i-1}a_{i}\cdots a_{m}w_{m}) is the basis element in the weak orbit of (u,av) . On the other hand, suppose that a is a letter of some w_{i} . Then u\equiv w_{0}a_{1}\cdots a_{i}w_{i}^{\prime} and v\equiv w_{i}^{\prime\prime}a_{i+1}\cdots a_{m}w_{m} with w_{i}\equiv w_{i}^{\prime}aw_{i}^{\prime\prime} . It follows from Remark 5.2 that (ua,v) and (u,av) both belong to the weak N -orbit of the basis element (w_{0}a_{1}\cdots a_{i},\overline{w_{i}}a_{i+1}\cdots a_{m}w_{m}) . In particular, each element of \mathcal{C} belongs to E . We must now show that if (u,a,v)\in E , then (u,a,v)=(m_{1},m_{2})(\delta_{1},a,\delta_{2}) for a unique (m_{1},m_{2})\in M\times M^{op} and (\delta_{1},a,\delta_{2})\in\mathcal{C} . As before let uav\equiv w_{0}a_{1}\cdots a_{m}w_{m} in Otto-Zhang normal form. Then, by the above, there is a unique i such that the distinguished a occurs in w_{i} . Since w_{i} is invertible, there is a unique minimal invertible subword \delta_{1}a\delta_{2} containing this a by Proposition 4.1 . Write u\equiv u^{\prime}\delta_{1} and v\equiv\delta_{2}v^{\prime} . Then (\delta_{1},a,\delta_{2})\in\mathcal{C} and (u,a,v)=(u^{\prime},v^{\prime})(\delta_{1},a,\delta_{2}) . We claim that these choices are unique. Clearly the letter a is uniquely determined by (u,a,v) . Suppose that \alpha,\beta,\delta_{1}^{\prime},\delta_{2}^{\prime} are reduced with (\alpha,\beta)(\delta_{1}^{\prime},a,\delta_{2}^{\prime})=(u,a,v) and (\delta_{1}^{\prime},a,\delta_{2}^{\prime})\in\mathcal{C} . Then (u,a,v)=(\alpha\delta_{1}^{\prime},a,\delta_{2}^{\prime}\beta) . We claim that \alpha\delta_{1}^{\prime} and \delta_{2}^{\prime}\beta are reduced. We handle just the first case as the second is dual. Since \alpha,\delta_{1}^{\prime} are reduced and each left-hand side of a rewrite rule is nonempty and invertible, it follows that the only way we can apply a rewrite rule is if it overlaps \alpha and \delta_{1}^{\prime} . This would imply that \delta_{1}^{\prime} has a left invertible prefix. Now any prefix of \delta_{1}^{\prime} is right invertible since \delta_{1}^{\prime}a\delta_{2}^{\prime} is invertible. But then we obtain a contradiction to the fact that \delta_{1}^{\prime} has no invertible prefix by Proposition 4.1 . Thus \alpha\delta_{1}^{\prime}\equiv u^{\prime}\delta_{1} and, dually, \delta_{2}^{\prime}\beta\equiv\delta_{2}v^{\prime} . Then \delta_{1}^{\prime}a\delta_{2}^{\prime} and \delta_{1}a\delta_{2} are both minimal invertible subwords of uav\equiv\alpha\delta_{1}^{\prime}a\delta_{2}^{\prime}\beta containing the distinguished a . By uniqueness of the minimal invertible subword containing a , which follows from Proposition 4.1 , we conclude that \delta_{1}^{\prime}a\delta_{2}^{\prime}\equiv\delta_{1}a\delta_{2} , with the distinguished occurrences of a the same. Thus \delta_{1}\equiv\delta_{1}^{\prime} , \delta_{2}\equiv\delta_{2}^{\prime} , u^{\prime}\equiv\alpha and v^{\prime}\equiv\beta . This establishes the uniqueness, and so \mathcal{C} is a basis. To prove that \mathcal{C} is finite we show that if (\delta_{1},a,\delta_{2})\in\mathcal{C} , then \delta_{1}a\delta_{2}\in\Delta . We begin by showing that \delta_{1}a\delta_{2}\in\Delta^{*} . If \delta_{1}a\delta_{2} is reduced, then it belongs to \Delta^{*} by Lemma 3.2 since it is invertible. Otherwise, we can apply a rewrite rule to \delta_{1}a\delta_{2} . Since \delta_{1},\delta_{2} are reduced, the left-hand side of the rewrite rule must contain a . Since each left-hand side of a rewrite rule is in \Delta^{+} , hence invertible, and \delta_{1}a\delta_{2} has no proper invertible subword containing the distinguished a , we must have that \delta_{1}a\delta_{2} is the left-hand side of a rewrite rule, and hence in \Delta^{*} . It follows now that there is a subword of \delta_{1}a\delta_{2} containing a that belongs to \Delta . But then since elements of \Delta are invertible, we deduce by minimality that \delta_{1}a\delta_{2}\in\Delta . We conclude that \mathcal{C} is finite as \Delta is finite. ∎ 7. Two-sided homological finiteness properties of special monoids With all the results in place they can be combined to prove the following main result. We shall use freely that \mathbb{Z}M -bimodules are the same thing as left \mathbb{Z}[M\times M^{op}] -modules. Theorem 7.1 (Theorem A) . Let M be a finitely presented monoid of the form M=\langle A\mid w_{1}=1,\ldots,w_{k}=1\rangle and let G be the group of units of M . (i) If G is of type {\rm FP}_{n} (for 1\leq n\leq\infty ) then M is of type bi- {\rm FP}_{n} . (ii) Furthermore, the Hochschild cohomological dimension of M is bounded below by \mathrm{cd}(G) and bounded above by \mathrm{max}\{2,\mathrm{cd}(G)\} . Proof. Let \overleftrightarrow{\Gamma} be the two-sided Cayley graph of M and let F be \overleftrightarrow{\Gamma}/N which is a forest by Lemma 5.3 . Notice that the multiplication map M\times M\rightarrow M factors through (M\times M)/N and hence the connected components of F are still isomorphic to M as an M -biset. The augmented cellular chain complex 0\rightarrow C_{1}(F)\rightarrow C_{0}(F)\rightarrow H_{0}(F)\cong{\mathbb{Z}M}\rightarrow 0 is a bimodule resolution of {\mathbb{Z}M} with exactness following from F being a forest. Now C_{1}(F) is the quotient of a free bimodule on A , namely \mathbb{Z}[M\times A\times M] , by \mathbb{Z}E where E is the finitely generated free M\times M^{op} -set from Theorem 6.1 . Thus we have a free resolution 0\longrightarrow\mathbb{Z}E\longrightarrow\mathbb{Z}[M\times A\times M]\to C_{1}(F)\to 0 by finitely generated free bimodules, and so C_{1}(F) is {\rm FP}_{\infty} and has projective dimension at most 1. We have C_{0}(F)\cong\mathbb{Z}[(M\times M)/N]\cong\mathbb{Z}[M\times M]\otimes_{{\mathbb{Z}N}}\mathbb{Z} . In Theorem 4.8 we proved that N is a free product of the group of units G and a finitely generated free monoid. Together with [ 23 , Corollary 4.13] this then implies that N is of type left- {\rm FP}_{n} , and hence \mathbb{Z} is a left {\mathbb{Z}N} -module of type {\rm FP}_{n} . Let F_{\bullet}\to\mathbb{Z}\to 0 be a free resolution of \mathbb{Z} by {\mathbb{Z}N} -modules with F_{i} finitely generated for 0\leq i\leq n . Then since M\times M^{op} is a free right N -set, it follows that \mathbb{Z}[M\times M^{op}] is free as a right {\mathbb{Z}N} -module and hence flat. Thus \mathbb{Z}[M\times M^{op}]\otimes_{{\mathbb{Z}N}}F_{\bullet}\to\mathbb{Z}[M\times M^{op}]\otimes_{{\mathbb{Z}N}}\mathbb{Z}\to 0 is a free resolution with \mathbb{Z}[M\times M^{op}]\otimes_{{\mathbb{Z}N}}F_{i} finitely generated for 0\leq i\leq n . Therefore, C_{0}(F)\cong\mathbb{Z}[M\times M^{op}]\otimes_{{\mathbb{Z}N}}\mathbb{Z} is a \mathbb{Z}[M\times M^{op}] -module of type {\rm FP}_{n} . Now since C_{0}(F) is {\rm FP}_{n} and C_{1}(F) is {\rm FP}_{\infty} it follows from Lemma 2.1 that the {\mathbb{Z}M} is {\rm FP}_{n} as a \mathbb{Z}[M\times M^{op}] -module, and hence the monoid M is of type bi- {\rm FP}_{n} . By [ 23 , Corollary 4.15] , since N is a free product of G and a free monoid we can choose a free resolution of \mathbb{Z} over {\mathbb{Z}N} to have length at most \mathrm{max}\{1,\mathrm{cd}(G)\} , and so we can deduce from the above argument that C_{0}(F) has projective dimension at most \max\{1,\mathrm{cd}(G)\} . Since C_{1}(F) has projective dimension at most 1 , we deduce that {\mathbb{Z}M} has projective dimension at most \mathrm{max}\{2,\mathrm{cd}(G)\} , and thus M has Hochschild dimension at most \mathrm{max}\{2,\mathrm{cd}(G)\} , by Lemma 2.2 . The fact that the Hochschild cohomological dimension of M is bounded below by that of G follows from [ 23 , Theorem 3.16(2)] together with the fact that the Hochschild cohomological dimension bounds both the left and right cohomological dimension of a monoid; see [ 22 , Section 7] . ∎ 7.1. Applying the general result to special one-relator monoids In the one-relator case the main theorem above specialises to the following which gives a Lyndon’s Identity type theorem for the two-sided homology of one-relator monoids. Theorem 7.2 (Theorem B) . Every one-relator monoid of the form \langle A\mid r=1\rangle is of type bi- {\rm FP}_{\infty} . Moreover, if r is not a proper power then the one-relator monoid has Hochschild cohomological dimension at most 2 , while if r is a proper power then the monoid has infinite Hochschild cohomological dimension. Proof. Let M=\langle A\mid r=1\rangle . The group of units G of M is a one-relator group by Adjan’s theorem [ 1 , Lemma 96] and hence the group G is of type {\rm FP}_{\infty} by Lyndon’s Identity Theorem [ 43 ] . Now applying Theorem 7.1 (i) we deduce that M is of type bi- {\rm FP}_{\infty} . For the second statement, if r is not a proper power then the group of units G will be (see e.g. [ 23 , Lemma 3.18] ) a torsion-free one-relator group. Then Lyndon’s results [ 43 ] imply that G has cohomological dimension at most 2, which implies the same for the Hochschild cohomological dimension of M by Theorem 7.1 (ii). If r is a proper power then G has torsion and hence infinite cohomological dimension. Therefore M has infinite Hochschild cohomological dimension by Theorem 7.1 (ii). ∎ 8. Other one-relator monoids In [ 21 ] we proved that all one-relator monoids \langle A\mid u=v\rangle are of type left- {\rm FP}_{\infty} (and dually of type right- {\rm FP}_{\infty} ). In that paper we also classified the one-relator monoids of cohomological dimension at most 2. It is natural to ask to what extent the results in this paper on two-sided homology might be extended to general one-relator monoids \langle A\mid u=v\rangle . In particular, it would be interesting to see whether the techniques in this paper can be further developed to prove that all one-relator monoids \langle A\mid u=v\rangle are of type bi- {\rm FP}_{\infty} . One natural approach to answering this question would be to try to use the same general proof strategy that was employed in [ 21 ] in the one-sided case. From that viewpoint, the result in this paper showing that special monoids are all of type bi- {\rm FP}_{\infty} would provide one important infinite family of base cases. The other infinite family of base cases are the, so-called, strictly aspherical one-relator monoids. It turns out (as we shall explain below) that known results can be applied to deduce that these strictly aspherical one-relator monoids are also of type bi- {\rm FP}_{\infty} . Hence combined with the results in this paper that deals with all the base cases. Thus following same approach as in [ 21 ] this means that the key to proving that all one-relator monoids are of type bi- {\rm FP}_{\infty} will be to develop an understanding of how the property bi- {\rm FP}_{\infty} behaves under a process called compression (a common framework for both Adjan–Oganesyan compression [ 2 ] and Lallement compression [ 40 ] that was developed in [ 21 ] ). Developing this understanding in the one-sided case was already quite an involved task, occupying much of the paper [ 21 ] , and we expect the two-sided case to be even more challenging. Let us outline this approach in more detail. For full details of the terminology used here we refer the reader to [ 21 ] . Let M be the one-relator monoid defined by the presentation \langle A\mid u=v\rangle where, without loss of generality, we assume |v|\leq|u| . This presentation for M is called compressible if there is a non-empty word r\in A^{+} such that u,v\in A^{*}r\cap rA^{*} . Otherwise, the presentation is called incompressible. If u,v\in A^{*}r\cap rA^{*} then there is an associated compressed one-relator monoid M_{r} that has a shorter defining relation, and the word problem of M_{r} is equivalent to that of M . The compression operation is transitive and confluent and it follows that there is a unique incompressible monoid M^{\prime} to which M compresses. It follows from [ 21 , Lemma 3.4 and Proposition 3.5] and [ 32 , Corollary 5.6] that if M is the one-relator monoid defined by the presentation \langle A\mid u=v\rangle and M^{\prime} is the unique incompressible monoid to which M compresses then either (i) M^{\prime} is a special one-relator monoid \langle B\mid w=1\rangle , or else (ii) M^{\prime} is a non-special one-relator monoid with a strictly aspherical presentation \langle B\mid w=z\rangle . Here a monoid presentation is strictly aspherical if each connected component of the Squier complex of the presentation is simply connected (see [ 21 , Section 2] for the relevant definitions). In case (i) above it follows from the results in this paper that M^{\prime}=\langle B\mid w=1\rangle is of type bi- {\rm FP}_{\infty} . In case (ii) the compressed monoid M^{\prime}=\langle B\mid w=z\rangle is strictly aspherical, and it turns out, as we shall now explain, that this is enough to show that M^{\prime} is also of type bi- {\rm FP}_{\infty} . Indeed, a key fact used in the proof of the main result of [ 21 ] was that the Cayley complex of a strictly aspherical presentation turns out to be contractible; see [ 21 , Lemmas 6.4 and 6.5] . It turns out that key fact also holds in the two-sided case too, and that it likely to be equally important in the approach we are describing here to proving that all one-relator monoids are of type bi- {\rm FP}_{\infty} . In more detail, in [ 53 ] Pride defines \pi_{2}^{(b)}(\mathcal{P})=H_{1}(D(\mathcal{P})) where D(\mathcal{P}) is the Squier complex of the presentation. Hence if \mathcal{P} is strictly aspherical then \pi_{1}(D(\mathcal{P})) is trivial at every vertex, hence in this case \pi_{2}^{(b)}(\mathcal{P})=H_{1}(D(\mathcal{P}))=0 . Then the argument in the final two paragraphs of the article [ 56 ] shows that the second homology of the 2-sided Cayley 2-complex of the presentation \mathcal{P} is equal to \pi_{2}^{(b)}(\mathcal{P}) . When the presentation \mathcal{P} is strictly aspherical this implies that second homology of the two-sided Cayley complex is 0 . Together with the fact proved in [ 22 , Theorem 7.12] that each connected component of the two-sided Cayley complex is simply connected, this implies by the Hurewicz and Whitehead theorems that the connected components of the two-sided Cayley complex are contractible. Then it follows that the two-sided Cayley graph is a bi-equivariant classifying space for the monoid, in the sense defined in [ 22 , Section 7] , from which it follows that the monoid is bi- {\rm F}_{\infty} and hence by [ 22 , Proposition 7.7] is also bi- {\rm FP}_{\infty} . Also this shows that a strictly aspherical finitely presented monoid has Hochschild cohomological dimension at most 2 , again by results of [ 22 , Section 7] , since the argument above shows that the 2-sided Cayley 2-complex is a bi-equivariant classifying space for the monoid. In particular the observations in the previous paragraph can be used to give an alternative proof that when w is not a proper power the torsion-free special one-relator monoid \langle A\mid w=1\rangle is of type bi- {\rm FP}_{\infty} and has Hochschild cohomological dimension at most 2 , since Kobayashi proved in [ 33 , Corollary 7.5] that torsion-free special one-relator monoids are strictly aspherical. In addition these observations show the property bi- {\rm FP}_{\infty} holds for one-relator monoids also in the following cases. Theorem 8.1 . Let M=\langle A\mid u=v\rangle be an incompressible one-relator monoid with u,v\in A^{+} , that is, there is no non-empty word r\in A^{+} such that u,v\in A^{*}r\cap rA^{*} . Then M is of type bi- {\rm FP}_{\infty} and the Hochschild cohomological dimension at most 2 . The class of examples covered by the previous proposition should, from the discussion in this section above, be viewed as a family of base cases for a possible future inductive proof using compression that all one-relator monoids are of type bi- {\rm FP}_{\infty} .