Density of rational languages under shift invariant measures
Valérie Berthé, Herman Goulet-Ouellet, Dominique Perrin · 2025
Read Density of rational languages under shift invariant measures by Valérie Berthé, Herman Goulet-Ouellet, Dominique Perrin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16708.txt.
Introduction
Valérie Berthé, Herman Goulet-Ouellet, and Dominique Perrin ask whether the classical notion of density for formal languages survives under general shift-invariant measures. Their 2025 paper works on spaces of two-sided infinite words, where a language's density is the limiting average chance that a random word of a given length falls inside it. Classical theory fixes one counting measure; here any probability measure unchanged by shifting the word is allowed.
Their main result settles existence: densities exist for every rational language under every shift-invariant measure. When the language is aperiodic, they give explicit formulas for the value. The proof braids two toolkits that rarely meet, semigroup theory from the language side and ergodic theory from the measure side. The paper widens a foundational definition of automata theory to the natural generality of random infinite text.
Catalog record
| CREATOR | Valérie Berthé, Herman Goulet-Ouellet, Dominique Perrin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-16708
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Density of rational languages under shift invariant measures Valérie Berthé, Herman Goulet-Ouellet, Dominique Perrin 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. Université Paris Cité, IRIF, [email protected]://orcid.org/0000-0001-5561-7882 Faculty of Information Technology, Czech Technical University in [email protected]://orcid.org/0000-0003-3445-8469The second author was supported by the CTU Global Postdoc Fellowship program. LIGM, Université Gustave [email protected]://orcid.org/0000-0003-4036-141X ccs Theory of computation Regular languages keywords Automata theory, Symbolic dynamics, Semigroup theory, Ergodic theory † † runningauthor: V. Berthé, H. Goulet-Ouellet and D. Perrin † † copyright: Valérie Berthé, Herman Goulet-Ouellet and Dominique Perrin † † category: Track B: Automata, Logic, Semantics, and Theory of Programming † † editors: Keren Censor-Hillel, Fabrizio Grandoni, Joel Ouaknine, and Gabriele Puppis † † event-title: 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) † † event-shorttitle: ICALP 2025 † † event-acronym: ICALP † † year: 2025 † † event-date: July 8–11, 2025 † † event-location: Aarhus, Denmark † † series-volume: 334 † † articleno: 162 The natural density for a language L on a finite alphabet A is defined as the limit in average (if it exists) of the probability that a word of length n belongs to L , where letters are drawn independently with equal probabilities. This notion can be traced back to the work of Berstel [ 5 ] , who took inspiration from Schützenberger [ 37 ] . It has been widely studied in the context of automata theory, logic and the theory of codes [ 7 , 36 , 26 , 19 , 20 , 10 , 39 , 22 , 23 ] , and also appears in ergodic theory, for instance in the work of Veech [ 40 , 41 ] . Densities have also been studied in the more general case where words are drawn with a Bernoulli measure, i.e. letters are drawn independently with possibly different probabilities [ 7 ] . This paper is related with recent work on the density of group languages [ 9 ] using a more general notion of density motivated by symbolic dynamics. Let \mu be a probability measure on the space A^{\mathbb{Z}} of two-sided infinite words on the alphabet A . Then the density of a language L with respect to \mu is the limit \delta_{\mu}(L)=\lim_{n\to\infty}\frac{1}{n}\sum_{i=0}^{n-1}\mu(\{x\in A^{\mathbb{Z}}\mid x_{0}\dots x_{i-1}\in L\}), (1) if it exists. The classical definition discussed above corresponds to the case where \mu is a Bernoulli measure. Our main result states that the density of a rational language L under a shift invariant probability measure \mu always exists ( Theorem 20 ). A shift invariant measure is a probability measure that behaves well with respect to left extensions of words (see Equation ( 5 )). The proof closely combines dynamical and algebraic methods. On the dynamical side, the proof relies mainly on the construction of a skew product between the shift space (made of two-sided infinite words) that supports the measure \mu and an \mathrel{\mathscr{R}} -class of the finite monoid M defining the rational language L (the transition monoid). The skew product we use is closely related to the notion of wreath product used in semigroup and automata theory [ 16 , Chapter 1, Section 10] . We construct a natural measure on the skew product, called the weighted counting measure, which leads to a closed formula for the density under the condition that this measure is ergodic ( Theorem 27 ). This generalizes known results for the case of Bernoulli measures. We also consider in Theorem 16 aperiodic languages (also called star-free) for which densities are proved to exist in a strong sense. On the algebraic side, this construction relies crucially on the theory of Green’s relations and on the key notion of the \mathrel{\mathscr{J}} -class associated with a shift. Let the monoid M be the image of A^{*} by a morphism \varphi . The \mathrel{\mathscr{J}} -class of M associated with X is the set of generators of the least ideal of M which meets the image by \varphi of the language of the shift X . Therefore, it can be called the minimal \mathrel{\mathscr{J}} -class of the monoid M with respect to the shift X . The use of such a \mathrel{\mathscr{J}} -class is a useful tool in automata theory, and appears in several different contexts. See [ 13 ] for a survey on the use of this idea, originating in the proof by Schützenberger of the characterization of aperiodic languages and [ 29 ] for an application close to the present paper. Let us give a brief outline of the paper. In Section 1 we present preliminaries on symbolic dynamics. In Section 2 we show how to calculate the densities of ideals of A^{*} . In Section 3 , we study the \mathrel{\mathscr{J}} -class associated with a shift space in a finite monoid and derive an explicit formula for the density of aperiodic languages ( Theorem 16 ). We also discuss connections with the notion of degree of an automaton and decidability results concerning the \mathrel{\mathscr{J}} -class. In Section 4 , we introduce the skew products and weighted counting measures, give the proof of our main result ( Theorem 20 ), along with an explicit expression for the density when the weighted counting measure is ergodic ( Theorem 27 ). In Section 5 , we consider algebraic properties of the density (see Corollary 28 ). Lastly, Section 6 contains a discussion on the case of sofic measures, motivated by Corollary 28 . Additionally, we provide in Appendix A a brief introduction to semigroup theory, focusing on ideals and Green’s relations. 1 Symbolic dynamics This section covers some necessary material from symbolic dynamics. We refer to [ 14 ] for a complete exposition on the topic, including proofs, and also to [ 17 , 34 ] as alternative sources. For more specialized texts on topological dynamics and ergodic theory, we refer to [ 31 , 42 ] . 1.1 Topological dynamical systems We first recall some terminology from topological dynamics. A topological dynamical system is a pair (X,T) of a compact metric space X and a continuous transformation T\colon X\to X . A subset Y\subseteq X is called stable if T(Y)\subseteq Y . A nonempty topological dynamical system (X,T) is minimal if the only closed stable subsets of X are X and \varnothing . Equivalently, all x\in X have dense forward orbits \{T^{n}(x)\mid n\geq 0\} . As a weaker notion, (X,T) is transitive if there exists x\in X with dense forward orbit. Transitivity is equivalent to the condition that U\cap T^{-n}V\neq\emptyset for all pairs of open sets U,V\subseteq X . Let \mu be a Borel probability measure on X . The support of \mu is the smallest