Groups with poly-context-free word problem
Tara Brough · Warwick Research Archive Portal (University of Warwick) · 2010
We call a language poly-context-free if it is an intersection of finitely many contextfree languages. In this thesis, we consider the class of groups with poly-context-free word problem. This is a generalisation of the groups with context-free word problem, which have been shown by Muller and Schupp [17, 3] to be precisely the finitely generated virtually free groups. We show that any group which is virtually a finitely generated subgroup of a direct product of finitely many free groups has poly-context-free word problem, and conjecture that the converse also holds. We prove our conjecture for several classes of soluble groups, including the metabelian groups and torsion-free soluble groups, and present progress towards resolving the conjecture for soluble groups in general. Some results in the thesis may be of independent interest in formal language theory or group theory. In Chapter 2 we develop some tools for proving a language not to be poly-context-free, and in Chapter 5 we prove that every finitely generated soluble group which is not virtually abelian has a subgroup of one of a small number of types.