Dissecting power of intersection of two context-free languages
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 ev...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-10-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/9063/pdf |
| _version_ | 1797269970090983424 |
|---|---|
| author | Josef Rukavicka |
| author_facet | Josef Rukavicka |
| author_sort | Josef Rukavicka |
| collection | DOAJ |
| description | 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$. |
| first_indexed | 2024-04-25T01:56:50Z |
| format | Article |
| id | doaj.art-daf91981c3c74785915e9dc87d07610a |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:56:50Z |
| publishDate | 2023-10-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-daf91981c3c74785915e9dc87d07610a2024-03-07T15:48:46ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-10-01vol. 25:2Automata, Logic and Semantics10.46298/dmtcs.90639063Dissecting power of intersection of two context-free languagesJosef RukavickaWe 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$.https://dmtcs.episciences.org/9063/pdfcomputer science - formal languages and automata theorycomputer science - discrete mathematics68q45 |
| spellingShingle | Josef Rukavicka Dissecting power of intersection of two context-free languages Discrete Mathematics & Theoretical Computer Science computer science - formal languages and automata theory computer science - discrete mathematics 68q45 |
| title | Dissecting power of intersection of two context-free languages |
| title_full | Dissecting power of intersection of two context-free languages |
| title_fullStr | Dissecting power of intersection of two context-free languages |
| title_full_unstemmed | Dissecting power of intersection of two context-free languages |
| title_short | Dissecting power of intersection of two context-free languages |
| title_sort | dissecting power of intersection of two context free languages |
| topic | computer science - formal languages and automata theory computer science - discrete mathematics 68q45 |
| url | https://dmtcs.episciences.org/9063/pdf |
| work_keys_str_mv | AT josefrukavicka dissectingpowerofintersectionoftwocontextfreelanguages |