Dissecting power of intersection of two context-free languages

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F23%3A00374077" target="_blank" >RIV/68407700:21340/23:00374077 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.46298/dmtcs.9063" target="_blank" >https://doi.org/10.46298/dmtcs.9063</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.46298/dmtcs.9063" target="_blank" >10.46298/dmtcs.9063</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Dissecting power of intersection of two context-free languages

Popis výsledku v původním jazyce

We say that a language L is constantly growing if there is a constant c such that for every word u is an element of L there is a word v is an element of L with vertical bar u vertical bar < vertical bar v vertical bar <= c + vertical bar u vertical bar. We say that a language L is geometrically growing if there is a constant c such that for every word u is an element of L there is a word v is an element of L with vertical bar u vertical bar < vertical bar v vertical bar <= c vertical bar u vertical bar. Given two infinite languages L-1, L-2, we say that L-1 dissects L-2 if vertical bar L-2 L-1 vertical bar = infinity and vertical bar L-1 boolean AND L-2 vertical bar = infinity. 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 vertical bar Sigma vertical bar = 1 and vertical bar Theta vertical bar = 4. We prove that there are context-free languages M-1, M-2 subset of Theta*, an erasing alphabetical homomorphism pi : Theta* -> Sigma*, and a nonerasing alphabetical homomorphism phi : Gamma* -> Sigma* such that: If L subset of Gamma* is a geometrically growing language then there is a regular language R subset of Theta* such that phi(-1) (pi(R boolean AND M-1 boolean AND M-2)) dissects the language L.

Název v anglickém jazyce

Dissecting power of intersection of two context-free languages

Popis výsledku anglicky

We say that a language L is constantly growing if there is a constant c such that for every word u is an element of L there is a word v is an element of L with vertical bar u vertical bar < vertical bar v vertical bar <= c + vertical bar u vertical bar. We say that a language L is geometrically growing if there is a constant c such that for every word u is an element of L there is a word v is an element of L with vertical bar u vertical bar < vertical bar v vertical bar <= c vertical bar u vertical bar. Given two infinite languages L-1, L-2, we say that L-1 dissects L-2 if vertical bar L-2 L-1 vertical bar = infinity and vertical bar L-1 boolean AND L-2 vertical bar = infinity. 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 vertical bar Sigma vertical bar = 1 and vertical bar Theta vertical bar = 4. We prove that there are context-free languages M-1, M-2 subset of Theta*, an erasing alphabetical homomorphism pi : Theta* -> Sigma*, and a nonerasing alphabetical homomorphism phi : Gamma* -> Sigma* such that: If L subset of Gamma* is a geometrically growing language then there is a regular language R subset of Theta* such that phi(-1) (pi(R boolean AND M-1 boolean AND M-2)) dissects the language L.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Mathematics and Theoretical Computer Science

ISSN

1462-7264

e-ISSN

1365-8050

Svazek periodika

25

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

11

Strana od-do

—

Kód UT WoS článku

001083909900001

EID výsledku v databázi Scopus

2-s2.0-85174931542