2014/07/29 by Rose Berns-Zieve, Berns-Zieve, Rose, Dana Fry +7 · 1 citation
Computer Science · Mathematics · #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Natural Language Processing Techniques #math.GR #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1407.7745
13 pages, 8 figures
openalex publication_date 2014/07/29 · arxiv created 2014/12/03 · arxiv updated 2014/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a finitely generated group, and let Σ be 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 \emphcoCF 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. 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,θ) where θ 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.