2026-07-23T07:41:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23520 2025-10-02T12:57:37Z ddc:004 open_access

Density of Rational Languages Under Shift Invariant Measures Berthé, Valérie Goulet-Ouellet, Herman Perrin, Dominique Automata theory Symbolic dynamics Semigroup theory Ergodic theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Valérie Berthé and Herman Goulet-Ouellet and Dominique Perrin 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.143 urn:nbn:de:0030-drops-235203 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.143 eng https://creativecommons.org/licenses/by/4.0/legalcode