  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.
