Density of rational languages under shift invariant measures
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915433692528640 |
|---|---|
| author | Berthé, Valérie Goulet-Ouellet, Herman Perrin, Dominique |
| author_facet | Berthé, Valérie Goulet-Ouellet, Herman Perrin, Dominique |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16708 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Density of rational languages under shift invariant measures Berthé, Valérie Goulet-Ouellet, Herman Perrin, Dominique Formal Languages and Automata Theory 68Q45 (Primary) 37B10, 68Q70 (Secondary) 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. |
| title | Density of rational languages under shift invariant measures |
| topic | Formal Languages and Automata Theory 68Q45 (Primary) 37B10, 68Q70 (Secondary) |
| url | https://arxiv.org/abs/2504.16708 |