# Set of languages that can represent every c. e. languange

Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e. L$?

For example, a lot of languages can be formed by it's union, intersection, complement of context-free languages, but some languages can not be, is, it possible that every L , computably enumerable language with infinity words be formed by union,complement,intersection (finite/infinite) of unabiguous CFLs with infinite words? If not, is it possible that every L , computably enumerable language with infinity words be formed by union,complement,intersection (finite/infinite) or any operation of unabiguous CFLs with infinite words plus some other languages such as some context-sensitive languages?

$\textbf{update:}$ although the question has been answered, I hope there will be more solution to this problem. Thanks in advance.

• What's the definition of "product of two languages" and "product of infinitely many languages"? – Bjørn Kjos-Hanssen Oct 14 '17 at 7:23
• @BjørnKjos-Hanssen， thank you, I will edit the post. – XL _At_Here_There Oct 14 '17 at 7:35


Because the set of c.e. languages over some alphabet $\Sigma$ is computably isomorphic to the set of c.e. subsets of $\NN$ (via a computable bijection between $\NN$ and $\Sigma^{*}$), we may as well consider c.e. subsets of $\NN$.

Let $\CE$ be the family of all c.e. subsets of $\NN$. Scott's graph model of the untyped $\lambda$-calculus is $\CE$ equipped with the application operation $$X \cdot Y = \{n \in \NN \mid \exists k_1, \ldots, k_m \in Y . \langle [k_1, \ldots, k_m], n\rangle \in X\}$$ where $\langle {-}, {-} \rangle : \NN \times \NN \to \NN$ is a pairing function e.g., $\langle u, v \rangle = 2^u (2 v + 1)$, and $[k_1, \ldots, k_m]$ is the coding of finite lists, e.g., $[] = 0$ and $[k_1, \ldots, k_m] = \langle k_1, [k_2, \ldots, k_m]\rangle$. Think of $\langle [k_1, \ldots, k_m], n\rangle \in X$ as encoding information of the form "if input contains all of $k_1, \ldots, k_m$ then output $n$".

Now we can ask whether it is possible to generate all of $\CE$ using application and starting from some generators. The answer is positive. In fact, there is a single $G \in \CE$ such that by forming all possible applications $$G, G \cdot G, (G \cdot G) \cdot G, G \cdot (G \cdot G), (G \cdot G) \cdot (G \cdot G), \ldots$$ we get precisely $\CE$. You can read more about it in Dana Scott's "Datatypes as lattices", SIAM J. of Computing, Vol 5. No. 3, 1976, pp. 522–587.

• Thanks, and let me have a look at scott's paper. Actually, if we have a hierarchy of computational complexity each of which has a complete member like npc, we can choose one from each class to form subset which can form every c. e. language by at most P time complexity. but we don't know what the member and hierarchy is. This is much interesting that it has just one member. – XL _At_Here_There Oct 14 '17 at 11:05
• Can we assume the $G$ is an unambiguous CFL? – Bjørn Kjos-Hanssen Oct 14 '17 at 14:24
• I haven't thought carefully but I think $G$ must be a complete c.e. set in the sense of many-to-one reducibility. – Andrej Bauer Oct 14 '17 at 14:46
• $.$, the application or operator is defined implicitily using one member every class of computable functions. So it is just a little transformation of hierarchy of languages. I try to find a reduced set of language which can represent every c. e. language. – XL _At_Here_There Oct 15 '17 at 2:10
• Application is no different in type or computational properties than the operations you suggested. I think you need to more carefully consider what you're looking for. – Andrej Bauer Oct 15 '17 at 10:25