Groups with context-free co-word problem

by Derek Holt, Sarah Rees, Claas Röver and Richard Thomas

Keywords

word problems of groups, context-free languages

Abstract

We define a co-context-free group to be one whose co-word problem (the complement of its word problem) is context-free. This class is larger than the subclass of context-free groups, being closed under the taking of finite direct products, restricted standard wreath products with top context-free groups, and passing to finitely generated subgroups and finite index overgroups. We also prove that the only examples amongst polycyclic groups or the Baumslag-Solitar groups are virtually abelian. We do this by proving that languages with certain purely arithmetical properties cannot be context-free; this result may be of independent interest.

This is published in J. London Math. Soc. (2) 71 (2005), no. 3, 643-657.

Of course you can also ask me for a hard copy.