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 fo...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-10-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/9063/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344700575645696 |
|---|---|
| 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$. |
| format | Article |
| id | doaj-art-daf91981c3c74785915e9dc87d07610a |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-10-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-daf91981c3c74785915e9dc87d07610a2025-08-20T03:42:37ZengDiscrete 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 Rukavickahttps://orcid.org/0000-0002-4048-106XWe 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$.http://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 | http://dmtcs.episciences.org/9063/pdf |
| work_keys_str_mv | AT josefrukavicka dissectingpowerofintersectionoftwocontextfreelanguages |