Groups with Context-Free Co-Word Problem and Embeddings into Thompson's Group $V$

Rose Berns-Zieve, Dana Fry, Johnny Gillings, Hannah Hoganson, Heather Mathews

Published 2014-07-29, updated 2014-12-03Version 2

Let $G$ be a finitely generated group, and let $\Sigma$ be a finite subset that generates $G$ as a monoid. The \emph{word problem of $G$ with respect to $\Sigma$} consists of all words in the free monoid $\Sigma^{\ast}$ that are equal to the identity in $G$. The \emph{co-word problem of $G$ with respect to $\Sigma$} is the complement in $\Sigma^{\ast}$ of the word problem. We say that a group $G$ is \emph{co$\mathcal{CF}$} if its co-word problem with respect to some (equivalently, any) finite generating set $\Sigma$ is a context-free language. We describe a generalized Thompson group $V_{(G, \theta)}$ for each finite group G and homomorphism $\theta$: $G \rightarrow G$. Our group is constructed using the cloning systems introduced by Witzel and Zaremsky. We prove that $V_{(G, \theta)}$ is co$\mathcal{CF}$ for any homomorphism $\theta$ and finite group G by constructing a pushdown automaton and showing that the co-word problem of $V_{(G, \theta)}$ is the cyclic shift of the language accepted by our automaton. A version of a conjecture due to Lehnert says that a group has context-free co-word problem exactly if it is a finitely generated subgroup of V. The groups $V_{(G,\theta)}$ where $\theta$ is not the identity homomorphism do not appear to have obvious embeddings into V, and may therefore be considered possible counterexamples to the conjecture. Demonstrative subgroups of $V$, which were introduced by Bleak and Salazar-Diaz, can be used to construct embeddings of certain wreath products and amalgamated free products into $V$. We extend the class of known finitely generated demonstrative subgroups of V to include all virtually cyclic groups.