Dissecting power of intersection of two context-free languages

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Dissecting power of intersection of two context-free languages

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

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

Name of the periodical

Discrete Mathematics and Theoretical Computer Science

ISSN

1462-7264

e-ISSN

1365-8050

Volume of the periodical

25

Issue of the periodical within the volume

2

Country of publishing house

FR - FRANCE

Number of pages

11

Pages from-to

—

UT code for WoS article

001083909900001

EID of the result in the Scopus database

2-s2.0-85174931542