Algorithmic properties of inverse monoids with hyperbolic and tree-like Sch\"utzenberger graphs
From MaRDI portal
Publication:6330274
DOI10.1016/J.JALGEBRA.2022.07.029arXiv1912.00950WikidataQ115571719 ScholiaQ115571719MaRDI QIDQ6330274FDOQ6330274
Authors: R. Gray, Pedro V. Silva, Nóra Szakács 
Publication date: 2 December 2019
Abstract: We prove that the class of finitely presented inverse monoids whose Sch"utzenberger graphs are quasi-isometric to trees has a uniformly solvable word problem, furthermore, the languages of their Sch"utzenberger automata are context-free. On the other hand, we show that there is a finitely presented inverse monoid with hyperbolic Sch"utzenberger graphs and an unsolvable word problem.
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Inverse semigroups (20M18) Algebraic monoids (20M32) Semigroups in automata theory, linguistics, etc. (20M35) Generalizations of semigroups (20M75)
This page was built for publication: Algorithmic properties of inverse monoids with hyperbolic and tree-like Sch\"utzenberger graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330274)
