<p>$\newcommand{\CE}{\mathsf{CE}}$
$\newcommand{\NN}{\mathbb{N}}$</p>

<p>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$.</p>

<p>Let $\CE$ be the family of all c.e. subsets of $\NN$. Scott's <strong>graph model</strong> 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$".</p>

<p>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 <a href="https://pdfs.semanticscholar.org/359e/ca57fe42d97cbb67f0b5591869abe5eb5421.pdf" rel="noreferrer">"Datatypes as lattices"</a>, SIAM J. of Computing, Vol 5. No. 3, 1976, pp. 522–587.</p>

CC BY-SA 3.0
2017-10-14T11:05:12.083Z
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
CC BY-SA 3.0
2017-10-14T14:24:29.200Z
Can we assume  the $G$ is an unambiguous CFL?
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-10-14T14:46:33.537Z
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
CC BY-SA 3.0
2017-10-15T02:10:11.960Z
$.$, 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
CC BY-SA 3.0
2017-10-15T10:25:42.897Z
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
CC BY-SA 3.0
2017-10-14T09:03:52.413Z
2017-10-14T09:03:52.413Z
Andrej Bauer
<p>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$?</p>

<p>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?</p>

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

CC BY-SA 3.0
2017-10-14T07:23:18.120Z
What's the definition of "product of two languages" and "product of infinitely many languages"?
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-10-14T07:35:22.953Z
@BjørnKjos-Hanssen， thank you, I will edit the post.
XL _At_Here_There
<fl.formal-languages><computability><automata-theory>
Set of languages that can represent every c. e. languange
XL _At_Here_There
# Set of languages that can represent every c. e. languange

(Asked by: username_0 on 2017-10-14)

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.

**Tags:** fl.formal-languages, computability, automata-theory
> **Comments:**
> **username_1**: What's the definition of "product of two languages" and "product of infinitely many languages"?  
> **username_0**: @BjørnKjos-Hanssen， thank you, I will edit the post.  

---

## 1 answers

### Answer by username_2 on 2017-10-14. Score: 5 | Accepted answer

$\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"](https://pdfs.semanticscholar.org/359e/ca57fe42d97cbb67f0b5591869abe5eb5421.pdf), SIAM J. of Computing, Vol 5. No. 3, 1976, pp. 522–587.

> **Comments:**
> **username_0**: 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.  
> **username_1**: Can we assume  the $G$ is an unambiguous CFL?  
> **username_2**: I haven't thought carefully but I think $G$ must be a complete c.e. set in the sense of many-to-one reducibility.  
> **username_0**: $.$, 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.  
> **username_2**: 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.  

---

