Mathematical Proceedings of the Cambridge Philosophical Society



Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness


ALAN J. CAIN a1 1 , EDMUND F. ROBERTSON a1 and NIK RUŠKUC a1 2
a1 School of Mathematics and Statistics, University of St Andrews, North Haugh, St Andrews, Fife KY16 9SS. e-mail: alanc@mcs.st-andrews.ac.uk, edmund@mcs.st-andrews.ac.uk, nik@mcs.st-andrews.ac.uk

Article author query
cain aj   [Google Scholar] 
robertson ef   [Google Scholar] 
ruskuc n   [Google Scholar] 
 

Abstract

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)



Footnotes

1 Work supported by the Carnegie Trust for the Universities of Scotland.

2 Partial financial support from INTAS 99/1224.