Note on Dissecting Power of Regular Languages

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F25%3A00390506" target="_blank" >RIV/68407700:21340/25:00390506 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-031-97548-6_20" target="_blank" >http://dx.doi.org/10.1007/978-3-031-97548-6_20</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-97548-6_20" target="_blank" >10.1007/978-3-031-97548-6_20</a>

Result language
angličtina
Original language name
Note on Dissecting Power of Regular Languages
Original language description
Let c > 1 be a real constant. We say that a language L is c-constantly growing if for every word u is an element of L there is a word v. L with |u| < |v| <= c + |u|. We say that a language L is c-geometrically growing if for every word u is an element of L there is a word v is an element of L with |u| < |v| <= c|u|. Given a language L, we say that L is REG-dissectible if there is a regular language R such that | L R| infinity 8 and | L boolean AND R| = infinity. In 2013, it was shown that every c-constantly growing language L is REG-dissectible. In 2023, the following open question has been presented: "Is the family of geometrically growing languages REG-dissectible?" For every c > 1, we construct a c-geometrically growing language L that is not REGdissectible. Hence we answer negatively to the open question.
Czech name
—
Czech description
—

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

Similar results(10)