Presentations of inverse monoids (Q582399)

A presentation of an inverse monoid is a pair \(P=(X;S)\), where S is a binary relation on the free inverse monoid FIM(X) on the set X (or on the free monoid \((X\cup X^{-1})^*)\). The inverse monoid \(M=Inv<X| S>\) presented by P is FIM(X)/\(\theta\), where \(\theta\) is the congruence generated by S. Alternatively, \(M=(X\cup X^{-1})^*/\tau\), where \(\tau\) is the congruence generated by S union the least inverse semigroup congruence on \((X\cup X^{-1})^*\). The latter interpretation and notation will be used in the rest of the review. The paper is a seminal study of the solvability of the word problem for M. For \(u\in (X\cup X^{-1})^*\), the Schützenberger graph \(S\Gamma\) (u) of u is the labelled digraph, the vertex of which is the \({\mathcal R}\)- class of \(u\tau\) in M, with an edge labelled \(y\in X\cup X^{-1}\) from m to n if and only if \(m(y\tau)=n\). The triple \({\mathcal A}(u)=((uu^{- 1})\tau,S\Gamma (u),u\tau)\) is a ``birooted inverse wordgraph'', which may be regarded as an ``inverse'' automaton, with inputs from \(X\cup X^{-1}\). It is shown that its language comprises those strings w for which \(w\tau\geq u\tau\) in M. It follows that for \(u,v\in (X\cup X^{- 1})^*\), \(u\tau =v\tau\) if and only if the languages of the respective automata are equal. It is proven that this is the case if and only if there is a label-preserving isomorphism from \(S\Gamma\) (u) to \(S\Gamma\) (v) that sends \((uu^{-1})\tau\) to \((vv^{-1})\tau\) to \((vv^{- 1})\tau\) and \(u\tau\) to \(v\tau\). Decidability of the Schützenberger graphs would clearly solve the word problem for M. The major part of the paper is devoted to a procedure which aims to construct these graphs. In brief, one begins with the ``linear'' graph of the string u and iteratively applies the following two steps: (i) if two edges with the same label emanate from, or enter, the same vertex, then coalesce their endpoints; (ii) if the graph contains a path labelled by one side of a relation in S, but no path between the same endpoints labelled by the other side of the relation, ``sew on'' the linear graph of the latter string in the appropriate location. If the presentation is finite then the graphs in the sequence so obtained are all finite and the sequence is proven to ``converge'' to \(S\Gamma\) (u). Thus, if the sequence should stabilize, an effective construction for \(S\Gamma\) (u) results. If all such sequences stabilize, the word problem for M is solvable. (In fact various more general statements may be made, without the finiteness restrictions.) Several applications are given. Munn's solution to the word problem for \(FIM(X)=Inv<X| \emptyset >\), in terms of ``birooted word trees'', is a special case. The lonstanding question of whether the free inverse semigroups on commuting generators have solvable word problem is answered affirmatively. During its long gestation period, the methods of this important paper have been quite widely used, for instance to study free strict inverse semigroups and free products of inverse semigroups.