Groups with Context-free Co-word Problem and Embeddings into Thompson’s Group V
Nathan Broaddus, Michael W. Davis, Jean‐François Lafont, Ivonne Johanna Ortiz · Cambridge University Press eBooks · 2018
Let G be a finitely generated group, and Σ a finite subset that generates G as a monoid. The word problem of G with respect to Σ consists of all words in the free monoid Σ* that are equal to the identity in G. The co-word problem of G with respect to Σ is the complement in Σ* of the word problem. We say that a group G is coCF if its co-word problem with respect to some (equivalently, any) finite generating set Σ is a context-free language. We describe a generalized Thompson group V(G,θ) for each finite group G and homomorphism θ: G → G. Our group is constructed using the cloning systems introduced by Witzel and Zaremsky. We prove that V(G,θ) is coCF for any homomorphism θ and finite group G by constructing a pushdown automaton and showing that the co-word problem of V(G,θ) is the cyclic shift of the language accepted by our automaton. Demonstrative subgroups of V, 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.