DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2025.143

Density of Rational Languages Under Shift Invariant Measures

Authors: Valérie Berthé, Herman Goulet-Ouellet, and Dominique Perrin

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

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.

Cite as

Valérie Berthé, Herman Goulet-Ouellet, and Dominique Perrin. Density of Rational Languages Under Shift Invariant Measures. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 143:1-143:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.ICALP.2025.143,
  author =	{Berth\'{e}, Val\'{e}rie and Goulet-Ouellet, Herman and Perrin, Dominique},
  title =	{{Density of Rational Languages Under Shift Invariant Measures}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{143:1--143:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.143},
  URN =		{urn:nbn:de:0030-drops-235203},
  doi =		{10.4230/LIPIcs.ICALP.2025.143},
  annote =	{Keywords: Automata theory, Symbolic dynamics, Semigroup theory, Ergodic theory}
}

Search Results

Documents authored by Goulet-Ouellet, Herman

Density of Rational Languages Under Shift Invariant Measures

Abstract

Cite as

Thanks for your feedback!

Could not send message