##
**Presentations of inverse monoids.**
*(English)*
Zbl 0691.20044

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.

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.

Reviewer: P.R.Jones

### MSC:

20M05 | Free semigroups, generators and relations, word problems |

20M35 | Semigroups in automata theory, linguistics, etc. |

### Keywords:

presentation; free inverse monoid; inverse semigroup congruence; solvability of the word problem; Schützenberger graph; free inverse semigroups; free products
PDFBibTeX
XMLCite

\textit{J. B. Stephen}, J. Pure Appl. Algebra 63, No. 1, 81--112 (1990; Zbl 0691.20044)

Full Text:
DOI

### References:

[1] | Clifford, A. H.; Preston, G., The Algebraic Theory of Semigroups. The Algebraic Theory of Semigroups, The Algebraic Theory of Semigroups, Vol. II (1967), American Mathematical Society: American Mathematical Society Providence, RI: American Mathematical Society: American Mathematical Society: American Mathematical Society Providence, RI: American Mathematical Society Providence, RI · Zbl 0178.01203 |

[2] | Eilenberg, S., Automata, Languages and Machines, Volume A (1974), Academic Press: Academic Press New York · Zbl 0317.94045 |

[3] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley New York · Zbl 0196.01701 |

[4] | Jones, P. R., Free products of inverse semigroups, Trans. Amer. Math. Soc., 282, 283-318 (1984) |

[5] | Jones, P. R., A graphical representation of the free product of \(E\)-unitary inverse semigroups, Semigroup Forum, 24, 195-221 (1984) · Zbl 0486.20035 |

[6] | Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory (1977), Springer: Springer Berlin · Zbl 0368.20023 |

[7] | Magnus, W.; Karrass, A.; Solitar, D., Combinatorial Group Theory (1976), Dover: Dover New York · Zbl 0362.20023 |

[8] | S.W. Margolis and J.C. Meakin, \(E\); S.W. Margolis and J.C. Meakin, \(E\) · Zbl 0676.20037 |

[9] | Margolis, S. W.; Meakin, J. C.; Stephen, J. B., Some decision problems for inverse monoid presentations, (Goberstein, S. M.; Higgins, P. M., Semigroups and their applications (1987), Reidel: Reidel Dordrecht), 99-110 · Zbl 0622.20046 |

[10] | Mc Alister, D. B.; Mc Fadden, R., The free inverse monoid on two commuting generators, J. Algebra, 32, 215-233 (1974) · Zbl 0298.20054 |

[11] | Meakin, J. C., On the structure of inverse semigroups, Semigroup Forum, 12, 6-14 (1976) · Zbl 0325.20062 |

[12] | Munn, W., Free inverse semigroups, Proc. London Math. Soc., 30, 385-404 (1974) · Zbl 0305.20033 |

[13] | Newman, M. H.A., On theories with a combinatorial definition of equivalence, Ann. of Math., 43, 2, 223-243 (1941) · Zbl 0060.12501 |

[14] | Nivat, M.; Perrot, J., Une generalisation du monoide bicyclique, C.R. Acad. Sci. Paris, 271, 824-827 (1970) · Zbl 0206.30304 |

[15] | Petrich, M., Inverse Semigroups (1984), Academic Press: Academic Press New York · Zbl 0546.20053 |

[16] | Reutenauer, C., Une topologie du monoide libre, Semigroup Forum, 18, 33-49 (1979) · Zbl 0444.68076 |

[17] | Scheiblich, H. E., Free inverse semigroups, Proc. Amer. Math. Soc., 4, 1-7 (1973) · Zbl 0256.20079 |

[18] | Stephen, J. B., Applications of automata theory to presentations of monoids and inverse monoids, (PhD thesis (1987), University of Nebraska-Lincoln) · Zbl 0691.20044 |

[19] | White, A. T., Graphs, Groups and Surfaces (1984), North-Holland: North-Holland Amsterdam · Zbl 0378.05028 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.