Groups with context-free co-word problem

Derek F. Holt, Sarah E. Rees, Claas E. Röver, Richard M. Thomas

Keywords

decision problems, word problems, formal language classes, context-free languages

Status

Published in Journal of the London Mathematical Society 71 (2005) 643--657

Abstract

We study the class of co-contrext-free groups. 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 context-free top groups, and passing to finitely generated subgroups and finite index overgroups. But we do not know of otherexamples of co-context-free groups. We prove that the only examples amongst polycylic 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.

The preprint is available as a gzipped postscript file.

Alternatively, you can request a copy by e-mailing me.

Sarah Rees
20th August 2003.