Premium
Groups with Context‐Free Co‐Word Problem
Author(s) -
Holt Derek F.,
Rees Sarah,
Röver Claas E.,
Thomas Richard M.
Publication year - 2005
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s002461070500654x
Subject(s) - context (archaeology) , free product , word (group theory) , mathematics , abelian group , complement (music) , class (philosophy) , combinatorics , group (periodic table) , arithmetic function , discrete mathematics , computer science , artificial intelligence , geometry , chemistry , paleontology , biochemistry , organic chemistry , complementation , gene , biology , phenotype
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.