Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs

Gray, Robert D., Silva, Pedro V. and Szakács, Nóra (2022) Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs. Journal of Algebra, 611. pp. 651-687. ISSN 0021-8693

[thumbnail of GRAY_SILVA_SZAKACS_polyhyperbolic_acceptedVersion]
Preview
PDF (GRAY_SILVA_SZAKACS_polyhyperbolic_acceptedVersion) - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (1MB) | Preview

Abstract

We prove that the class of finitely presented inverse monoids whose Schützenberger graphs are quasi-isometric to trees has a uniformly solvable word problem, furthermore, the languages of their Schützenberger automata are context-free. On the other hand, we show that there is a finitely presented inverse monoid with hyperbolic Schützenberger graphs and an unsolvable word problem.

Item Type: Article
Additional Information: Funding information: The second author was partially supported by CMUP, which is financed by national funds through FCT – Fundação para a Ciência e a Tecnologia, I.P., under the project with reference UIDB/00144/2020. The third author was funded by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 799419. The third author was partially supported by the Hungarian National Foundation for Scientific Research grant nos. K115518 and K128042.
Uncontrolled Keywords: context-free language,finitely presented inverse monoid,hyperbolic group,tree-like inverse monoid,virtually free group,word problem,algebra and number theory ,/dk/atira/pure/subjectarea/asjc/2600/2602
Faculty \ School: Faculty of Science > School of Mathematics (former - to 2024)
UEA Research Groups: Faculty of Science > Research Groups > Logic (former - to 2024)
Faculty of Science > Research Groups > Algebra and Combinatorics (former - to 2024)
Faculty of Science > Research Groups > Algebra, Number Theory, Logic, and Representations (ANTLR)
Related URLs:
Depositing User: LivePure Connector
Date Deposited: 06 Sep 2022 11:49
Last Modified: 30 Nov 2024 01:40
URI: https://ueaeprints.uea.ac.uk/id/eprint/87732
DOI: 10.1016/j.jalgebra.2022.07.029

Downloads

Downloads per month over past year

Actions (login required)

View Item View Item