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

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.
Original languageEnglish
Pages (from-to)651-687
Number of pages37
JournalJournal of Algebra
Volume611
Early online date9 Aug 2022
DOIs
Publication statusE-pub ahead of print - 9 Aug 2022

Keywords

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

Cite this