Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs (Q2079248): Difference between revisions

The strongly connected components of the Cayley graph of an inverse monoid \(M\) with respect to a given set of generators \(A\) are called its Schützenberger graphs. For a word \(w\) in the alphabet \(A\cup A^{-1}\), the Schützenberger graph containing the vertex represented by \(w\) is denoted \(\mathcal{S}(w)\) and the Schützenberger automaton \(\mathcal{A}(w)\) is \(\mathcal{S}(w)\) with initial and terminal vertices those represented by \(ww^{-1}\) and \(w\), respectively. By a result of \textit{J. B. Stephen} [J. Pure Appl. Algebra 63, No. 1, 81--112 (1990; Zbl 0691.20044)], the word problem for \(M\) is decidable if and only if membership in each language \(L(\mathcal{A}(w))\) is decidable. A directed graph is said to be symmetric if edges come in pairs with opposite ends. The paper provides several alternative characterizations of when such a graph is quasi-isometric to a tree, called tree-like, one of them being that polygons, that is, piecewise geodesic closed paths, are hyperbolic. An inverse monoid is said to be tree-like if ao are its Schützenberger graphs, a property that is independent of the choice of generators. The first main result shows that, for a tree-like finitely presented inverse monoid \(\text{Inv}\langle A \mid R\rangle\), the set \(\text{Geo}(w)\) of words on \(A\cup A^{-1}\) that represent geodesics in \(\mathcal{S}(w)\) starting at the vertex represented by \(ww^{-1}\) is rational. As an application, an example is given of a finitely generated tree-like inverse monoid which is not finitely presentable. The second main result is that, for a finitely presented inverse monoid \(\text{Inv}\langle A \mid R\rangle\) and a word \(w\) on \(A\cup A^{-1}\) such that \(\mathcal{S}(w)\) is tree-like, the language \(L(\mathcal{A}(w))\) is context-free. As an application, it is shown that the word problem is uniformly solvable for such presentations. Since being tree-like is characterized by the hyperbolicity of polygons, it is natural to ask whether the above main results extend to inverse monoids with hyperbolic Schützenberger graphs, that is those whose triangles are hyperbolic. The final main result shows that there is a finitely presented inverse monoid whose Schützenberger graphs are \(\delta\)-hyperbolic for a fixed \(\delta>0\) which has an undecidable word problem. The paper concludes with several natural open questions motivated by the above results and geometric group theory.