This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.
$\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)=\emptyset\}\quad\leq\quad\{\langle G_1,G_2\rangle\mid\mathcal{L}(G_1)\subseteq\overline{\mathcal{L}(G_2)}\}$
Reduce the empty intersection problem on CFGs over $\{a,b\}$ to the inclusion
problem between the language of a CFG and the complement of the language of
another CFG, in order to prove that such problem is not semi-decidable (not
recursively enumerable).
Authors: Carles Creus, Guillem Godoy
/
Documentation: