Please use this identifier to cite or link to this item:
Title: Groups with a context-free co-word problem
Authors: Holt, D. F.
Rees, Sarah
Röver, Claas E.
Thomas, Richard M.
First Published: 2005
Citation: Journal of the London Mathematical Society, 2005, 71, (3), pp.643-657
Abstract: The class of co-context-free groups is studied. A co-context-free group is defined as 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. No other examples of co-context-free groups are known. It is proved that the only examples amongst polycyclic groups or the Baumslag–Solitar groups are virtually abelian. This is done by proving that languages with certain purely arithmetical properties cannot be context-free; this result may be of independent interest.
DOI Link: 10.1112/S002461070500654X
ISSN: 0024-6107
Type: Article
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
There are no files associated with this item.

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.