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.

  • $\begingroup$ What's the definition of "product of two languages" and "product of infinitely many languages"? $\endgroup$ Oct 14, 2017 at 7:23
  • $\begingroup$ @BjørnKjos-Hanssen, thank you, I will edit the post. $\endgroup$ Oct 14, 2017 at 7:35

1 Answer 1


$\newcommand{\CE}{\mathsf{CE}}$ $\newcommand{\NN}{\mathbb{N}}$

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.

  • $\begingroup$ 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. $\endgroup$ Oct 14, 2017 at 11:05
  • $\begingroup$ Can we assume the $G$ is an unambiguous CFL? $\endgroup$ Oct 14, 2017 at 14:24
  • $\begingroup$ I haven't thought carefully but I think $G$ must be a complete c.e. set in the sense of many-to-one reducibility. $\endgroup$ Oct 14, 2017 at 14:46
  • $\begingroup$ $.$, 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. $\endgroup$ Oct 15, 2017 at 2:10
  • $\begingroup$ 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. $\endgroup$ Oct 15, 2017 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.