Presentations of inverse monoids (Q582399): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Joseph B. Stephen / rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Peter R. Jones / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20M05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20M35 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 4130678 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
presentation | |||
Property / zbMATH Keywords: presentation / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
free inverse monoid | |||
Property / zbMATH Keywords: free inverse monoid / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
inverse semigroup congruence | |||
Property / zbMATH Keywords: inverse semigroup congruence / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
solvability of the word problem | |||
Property / zbMATH Keywords: solvability of the word problem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Schützenberger graph | |||
Property / zbMATH Keywords: Schützenberger graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
free inverse semigroups | |||
Property / zbMATH Keywords: free inverse semigroups / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
free products | |||
Property / zbMATH Keywords: free products / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Joseph B. Stephen / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5564342 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4079524 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5592246 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A graphical representation for the free product of E-unitary inverse semigroups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4145882 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4135772 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: E-unitary inverse monoids and the Cayley graph of a group presentation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3759040 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The free inverse semigroup on two commuting generators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of inverse semigroups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Free Inverse Semigroups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On theories with a combinatorial definition of 'equivalence' / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5606625 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3337662 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Une topologie du monoide libre / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Free Inverse Semigroups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Presentations of inverse monoids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4156452 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:16, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Presentations of inverse monoids |
scientific article |
Statements
Presentations of inverse monoids (English)
0 references
1990
0 references
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.
0 references
presentation
0 references
free inverse monoid
0 references
inverse semigroup congruence
0 references
solvability of the word problem
0 references
Schützenberger graph
0 references
free inverse semigroups
0 references
free products
0 references