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

2019/12/02 by Robert D. Gray, Gray, Robert D., Pedro V. Silva +3
Computer Science · Mathematics · #20F05 #20F10 #20F67 #20M05 #20M18 #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Mathematical Dynamics and Fractals #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1912.00950

openalex publication_date 2019/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Application of verification techniques to inverse monoids
• Compressed word problems for inverse monoids
• Word Problem Languages for Free Inverse Monoids
• Decision problems for inverse monoids presented by a single sparse relator
• Free inverse monoids are co-context-free