Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness
This paper shows that, given a finite subset $X$ of a finitely generated virtually free group $F$, the freeness of the subsemigroup of $F$ generated by $X$ can be tested algorithmically. (A group is virtually free if it contains a free subgroup of finite index.) It is then shown that every finitely generated subsemigroup of $F$ has a finite Malcev presentation (a type of semigroup presentation which can be used to define any semigroup that embeds in a group), and that such a presentation can be effectively found from any finite generating set.(Published Online July 3 2006)
(Received July 5 2004)
(Revised March 2 2005)
1 Work supported by the Carnegie Trust for the Universities of Scotland.
2 Partial financial support from INTAS 99/1224.