Density of Rational Languages Under Shift Invariant Measures
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F25%3A00384488" target="_blank" >RIV/68407700:21240/25:00384488 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.4230/LIPIcs.ICALP.2025.143" target="_blank" >https://doi.org/10.4230/LIPIcs.ICALP.2025.143</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2025.143" target="_blank" >10.4230/LIPIcs.ICALP.2025.143</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Density of Rational Languages Under Shift Invariant Measures
Popis výsledku v původním jazyce
We study density of rational languages under shift invariant probability measures on spaces of two-sided infinite words, which generalizes the classical notion of density studied in formal languages and automata theory. The density for a language is defined as the limit in average (if it exists) of the probability that a word of a given length belongs to the language. We establish the existence of densities for all rational languages under all shift invariant measures. We also give explicit formulas under certain conditions, in particular when the language is aperiodic. Our approach combines tools and ideas from semigroup theory and ergodic theory.
Název v anglickém jazyce
Density of Rational Languages Under Shift Invariant Measures
Popis výsledku anglicky
We study density of rational languages under shift invariant probability measures on spaces of two-sided infinite words, which generalizes the classical notion of density studied in formal languages and automata theory. The density for a language is defined as the limit in average (if it exists) of the probability that a word of a given length belongs to the language. We establish the existence of densities for all rational languages under all shift invariant measures. We also give explicit formulas under certain conditions, in particular when the language is aperiodic. Our approach combines tools and ideas from semigroup theory and ergodic theory.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)
ISBN
—
ISSN
1868-8969
e-ISSN
—
Počet stran výsledku
20
Strana od-do
1-20
Název nakladatele
Dagstuhl Publishing,
Místo vydání
Saarbrücken
Místo konání akce
Aarhus
Datum konání akce
8. 7. 2025
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—