Algorithmic properties of inverse monoids with hyperbolic and tree-like Schutzenberger graphs

• Type: Article in International Scientific Journal
• Date: 2022

Authors

Gray, RD (Author) Other; Pedro V. Silva (Author) FCUP; Szakacs, N (Author) Other

Journal

Title: Journal of Algebra

Vol. 611

Pages: 651-687

ISSN: 0021-8693

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: P-00X-5DZ

DOI: 10.1016/j.jalgebra.2022.07.029

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 37