‘Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness’
[with E. F. Robertson & N. Ruškuc]
Mathematical Proceedings of the Cambridge Philosophical Society, 141, no. 1 (2006), pp. 57–66.
DOI: 10.1017/s0305004106009236. MR: 2238642. ZBL: 1115.20043.


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.