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
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 |