Algorithmic properties of inverse monoids with hyperbolic and tree-like Sch\"utzenberger graphs

DOI10.1016/J.JALGEBRA.2022.07.029MaRDI QIDQ6330274arXivWikidataFDO

Authors R. Gray, Pedro V. Silva, Nóra Szakács

Publication date 2 December 2019

Mathematics Subject Classification ID

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)

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.

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)