On finitely generated submonoids of virtually free groups

2017/12/20 by Pedro V. Silva, Silva, Pedro V., Alexander Zakharov +1
Computer Science · Mathematics · #20E05 #20F10 #20M05 #68Q45 #68Q70 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Geometric and Algebraic Topology #Group Theory (math.GR) #Logic, programming, and type systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1712.07746

openalex publication_date 2017/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that it is decidable whether or not a finitely generated submonoid of a virtually free group is graded, introduce a new geometric characterization as quasi-geodesic monoids, and show that their word problem is rational (as a relation). We also solve the isomorphism problem for this class of monoids, generalizing earlier results for submonoids of free monoids. We also prove that the classes of graded monoids, regular monoids and Kleene monoids coincide for submonoids of free groups.

Related

• Free submonoids of hyperbolic monoids
• On the rational subsets of the monogenic free inverse monoid
• The degree of a finite set of words
• On the submonoid membership problem for HNN extensions of free groups
• Magnus submonoids and membership problems in one-relator, surface and hyperbolic groups