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

Tools

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
UEA Research Groups:	Faculty of Science > Research Groups > Logic Faculty of Science > Research Groups > Algebra and Combinatorics
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	06 Sep 2022 11:49
Last Modified:	09 Aug 2023 01:38
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