Groups with context-free co-word problem and embeddings into Thompson’s group \(V\). (English) Zbl 1430.20025
Broaddus, N. (ed.) et al., Topological methods in group theory. Proceedings of the conference, Ohio State University, Columbus, OH, USA, June 16–20, 2014 in honor of Ross Geoghegan’s 70th birthday. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 451, 19-37 (2018).
Summary: Let \(G\) be a finitely generated group, and \(\Sigma\) a finite subset that generates \(G\) as a monoid. The 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 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 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 \to G\). Our group is constructed using the cloning systems introduced by S. Witzel and M. C. B. Zaremsky [Groups Geom. Dyn. 12, No. 1, 289–358 (2018; Zbl 1456.20050)]. 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\), introduced by C. Bleak and O. Salazar-Díaz [Trans. Am. Math. Soc. 365, No. 11, 5967–5997 (2013; Zbl 1287.20053)], 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.
For the entire collection see [Zbl 1398.20002].
We describe a generalized Thompson group \(V_{(G,\theta)}\) for each finite group \(G\) and homomorphism \(\theta: G \to G\). Our group is constructed using the cloning systems introduced by S. Witzel and M. C. B. Zaremsky [Groups Geom. Dyn. 12, No. 1, 289–358 (2018; Zbl 1456.20050)]. 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\), introduced by C. Bleak and O. Salazar-Díaz [Trans. Am. Math. Soc. 365, No. 11, 5967–5997 (2013; Zbl 1287.20053)], 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.
For the entire collection see [Zbl 1398.20002].
MSC:
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20F65 | Geometric group theory |
| 20F05 | Generators, relations, and presentations of groups |
| 68Q45 | Formal languages and automata |
