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.