论文标题
解剖两种无上下文语言的交点的力量
Dissecting power of intersection of two context-free languages
论文作者
论文摘要
我们说，如果有一个常数$ c $，则语言$ l $是\ emph {不断增长}，以便对于l $中的每个单词$ u \ in l $ in l $ in l $ in l $ in l $ in l $ a $ \ vert u \ vert u \ vert <\ vert v \ vert v \ vert v \ vert \ leq c+\ vert c+\ vert u \ vert $。我们说，如果有一个常数$ c $，则语言$ l $是\ emph {几何生长}，以使每个单词$ u \ in l $ in L $中，l $ in l $ in l $ in l $ in l $ \ vert u \ vert u \ vert <\ vert v \ vert v \ vert v \ vert \ leq c \ leq c \ vert u \ vert u \ vert u \ vert $。给定两种无限语言$ l_1，l_2 $，我们说$ l_1 $ \ emph {dissects} $ l_2 $如果$ \ vert l_2 \ setminus l_1 \ vert = \ infty = \ infty $和$ \ vert l_1 \ vert l_1 \ cap l_2 \ vert cap l_2 \ vert = \ fert = \ ferty $。在2013年，显示出每种不断增长的语言$ l $都有常规语言$ r $，因此$ r $ dysect $ l $。 在当前的文章中，我们展示了如何通过两种无上下文语言的相交的同态图像来剖析几何发展的语言。 考虑三个字母$γ$，$σ$和$θ$，以便$ \vertσ\ vert = 1 $和$ \vertθ\ vert = 4 $。我们证明，有没有上下文的语言$ m_1，m_2 \subseteqθ^*$，一种删除字母的同构$π$π：θ^*\ rightArrowσ^*$，以及一个非误差字母的字母同源$φ：γ^^*$ cumperAte：几何发展语言，然后有一种常规语言$ r \ subseteqθ^*$，使得$φ^{ - 1} \ left（π\ left（r \ cap m_1 \ cap m_2 \ cap m_2 \ right）\ right）\ right）$ dissect $ 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 $Γ$, $Σ$, and $Θ$ such that $\vert Σ\vert=1$ and $\vert Θ\vert=4$. We prove that there are context-free languages $M_1,M_2\subseteq Θ^*$, an erasing alphabetical homomorphism $π:Θ^*\rightarrow Σ^*$, and a nonerasing alphabetical homomorphism $φ: Γ^*\rightarrow Σ^*$ such that: If $L\subseteq Γ^*$ is a geometrically growing language then there is a regular language $R\subseteq Θ^*$ such that $φ^{-1}\left(π\left(R\cap M_1\cap M_2\right)\right)$ dissects the language $L$.
