On finitely generated submonoids of virtually free groups
arXiv:1712.07746
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.
22 pages. Main results generalized to virtually free groups, new geometric characterisation added in Section 4, Section 6 modified to include word problem for monoids, main proofs shortened, references added