Density of Rational Languages Under Shift Invariant Measures
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Density of Rational Languages Under Shift Invariant Measures
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)
ISBN
—
ISSN
1868-8969
e-ISSN
—
Number of pages
20
Pages from-to
1-20
Publisher name
Dagstuhl Publishing,
Place of publication
Saarbrücken
Event location
Aarhus
Event date
Jul 8, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—