Note on Dissecting Power of Regular Languages

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Note on Dissecting Power of Regular Languages

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Note on Dissecting Power of Regular Languages

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2025

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 statě ve sborníku

Combinatorics on Words. WORDS 2025.

ISBN

978-3-031-97547-9

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

8

Strana od-do

230-237

Název nakladatele

Springer, Cham

Místo vydání

—

Místo konání akce

Nancy

Datum konání akce

30. 6. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001555635100020