On a kind of Fatou property of context-free groups (Q1186612): Difference between revisions

A cone is a family of languages closed under homomorphism, inverse homomorphism, and intersection with regular languages. A context-free group is a group whose word problem is context-free; algebraically, they are the groups possessing a finitely generated free normal subgroup of finite index. Let \(M\) be a finitely generated monoid and \(\mathfrak C\) a family of languages closed under homomorphism. Define \({\mathfrak C}^ \exists(M)=\{T\subseteq M\mid\) there is a surjective homomorphism \(\phi: X^*\to M\) and \(L\in{\mathfrak C}\) such that \(\phi(L)=T\}\). The author proves the following result: let \(\mathfrak C\) be a cone closed under union, \(G\) a context-free group, \(U\) a finitely generated subgroup of \(G\), and \(T\subseteq U\). Then \(T\in{\mathfrak C}^ \exists(G)\) iff \(T\in{\mathfrak C}^ \exists(U)\). As an application, the author shows that in infinite context-free groups the algebraic subsets, that are those subsets which are homomorphic images of context-free languages, are strictly included in those subsets which are homomorphic images of recursively enumerable languages.