Dissecting power of intersection of two context-free languages
Dissecting power of intersection of two context-free languages
复制标题
剖析两种上下文无关语言交集的力量
DOI：
10.46298/dmtcs.9063
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Josef Rukavicka
中科院分区：
文献类型：
--
作者：
Josef Rukavicka
如果存在一个语言，我们就说一种语言 $L$ 是 \emph{不断增长}
常数 $c$ 使得对于每个单词 $u\in L$ 都有一个单词 $v\in L$
$\vert u\vert<\vert v\vert\leq c+\vert u\vert$。我们说语言 $L$ 是
\emph{几何增长} 如果存在一个常数 $c$ 使得对于每个
单词 $u\in L$ 有一个单词 $v\in L$ 且 $\vert u\vert<\vert v\vert\leq
c\vert u\vert$。给定两种无限语言 $L_1,L_2$，我们说 $L_1$
\emph{解剖} $L_2$ 如果 $\vert L_2\setminus L_1\vert=\infty$ 和 $\vert
L_1\cap L_2\vert=\infty$。 2013 年，研究表明，对于每一个不断
不断增长的语言 $L$ 存在一种常规语言 $R$，使得 $R$ 能够剖析
$L$。
在当前的文章中，我们展示了如何剖析几何增长的
语言由两种上下文无关语言的交集的同态图像组成。
考虑三个字母 $\Gamma$、$\Sigma$ 和 $\Theta$，使得 $\vert
\Sigma\vert=1$ 和 $\vert \Theta\vert=4$。我们证明存在上下文无关
语言 $M_1,M_2\subseteq \Theta^*$，擦除字母同态
$\pi:\Theta^*\rightarrow \Sigma^*$，以及非擦除字母同态
$\varphi : \Gamma^*\rightarrow \Sigma^*$ 使得： 如果 $L\subseteq \Gamma^*$ 是
一种几何增长的语言 那么有一种常规语言 $R\subseteq
\Theta^*$ 使得 $\varphi^{-1}\left(\pi\left(R\cap M_1\cap
M_2\right)\right)$ 剖析了语言 $L$。
We say that a language $L$ is \emph{constantly growing} if there is a
constant $c$ such that for every word $u\in L$ there is a word $v\in L$ with
$\vert u\vert<\vert v\vert\leq c+\vert u\vert$. We say that a language $L$ is
\emph{geometrically growing} if there is a constant $c$ such that for every
word $u\in L$ there is a word $v\in L$ with $\vert u\vert<\vert v\vert\leq
c\vert u\vert$. Given two infinite languages $L_1,L_2$, we say that $L_1$
\emph{dissects} $L_2$ if $\vert L_2\setminus L_1\vert=\infty$ and $\vert
L_1\cap L_2\vert=\infty$. In 2013, it was shown that for every constantly
growing language $L$ there is a regular language $R$ such that $R$ dissects
$L$.
In the current article we show how to dissect a geometrically growing
language by a homomorphic image of intersection of two context-free languages.
Consider three alphabets $\Gamma$, $\Sigma$, and $\Theta$ such that $\vert
\Sigma\vert=1$ and $\vert \Theta\vert=4$. We prove that there are context-free
languages $M_1,M_2\subseteq \Theta^*$, an erasing alphabetical homomorphism
$\pi:\Theta^*\rightarrow \Sigma^*$, and a nonerasing alphabetical homomorphism
$\varphi : \Gamma^*\rightarrow \Sigma^*$ such that: If $L\subseteq \Gamma^*$ is
a geometrically growing language then there is a regular language $R\subseteq
\Theta^*$ such that $\varphi^{-1}\left(\pi\left(R\cap M_1\cap
M_2\right)\right)$ dissects the language $L$.