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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2022

Autores

Gray, RD (Autor) Outra; Pedro V. Silva (Autor) FCUP; Szakacs, N (Autor) Outra

Revista

Título: Journal of Algebra

Vol. 611

Páginas: 651-687

ISSN: 0021-8693

Editora: Elsevier

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 37