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

Robert D. Gray, Pedro V. Silva, Nóra Szakács

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
2 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)651-687
Number of pages37
JournalJournal of Algebra
Early online date9 Aug 2022
Publication statusPublished - 1 Dec 2022


  • Context-free language
  • Finitely presented inverse monoid
  • Hyperbolic group
  • Tree-like inverse monoid
  • Virtually free group
  • Word problem

Cite this