On a kind of Fatou property of context-free groups (Q1186612): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:12, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a kind of Fatou property of context-free groups |
scientific article |
Statements
On a kind of Fatou property of context-free groups (English)
0 references
28 June 1992
0 references
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.
0 references
regular languages
0 references
word problem
0 references
free normal subgroup of finite index
0 references
finitely generated monoid
0 references
context-free groups
0 references
algebraic subsets
0 references
context-free languages
0 references
recursively enumerable languages
0 references