Density of Rational Languages Under Shift Invariant Measures
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.
Keywords and phrases:
Automata theory, Symbolic dynamics, Semigroup theory, Ergodic theoryCategory:
Track B: Automata, Logic, Semantics, and Theory of ProgrammingFunding:
Valérie Berthé: The first author was supported by the Agence Nationale de la Recherche through the projects “SymDynAr” (ANR-23-CE40-0024) and “IZES” (ANR-22-CE40-0011), as well as by the 2024 ERC Synergy Project DynAMiCs (101167561).Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Regular languagesEditors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

Introduction
The natural density for a language on a finite alphabet is defined as the limit in average (if it exists) of the probability that a word of length belongs to , 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 be a probability measure on the space of two-sided infinite words on the alphabet . Then the density of a language with respect to is the limit
(1) |
if it exists. The classical definition discussed above corresponds to the case where is a Bernoulli measure. Our main result states that the density of a rational language under a shift invariant probability measure always exists (Theorem 4.1). 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 and an -class of the finite monoid defining the rational language (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 4.8). This generalizes known results for the case of Bernoulli measures. We also consider in Theorem 3.6 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 -class associated with a shift. Let the monoid be the image of by a morphism . The -class of associated with is the set of generators of the least ideal of which meets the image by of the language of the shift . Therefore, it can be called the minimal -class of the monoid with respect to the shift . The use of such a -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 . In Section 3, we study the -class associated with a shift space in a finite monoid and derive an explicit formula for the density of aperiodic languages (Theorem 3.6). We also discuss connections with the notion of degree of an automaton and decidability results concerning the -class. In Section 4, we introduce the skew products and weighted counting measures, give the proof of our main result (Theorem 4.1), along with an explicit expression for the density when the weighted counting measure is ergodic (Theorem 4.8). In Section 5, we consider algebraic properties of the density (see Corollary 5.1). Lastly, Section 6 contains a discussion on the case of sofic measures, motivated by Corollary 5.1.
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 of a compact metric space and a continuous transformation . A subset is called invariant if . A nonempty topological dynamical system is minimal if the only closed invariant subsets of are and . Equivalently, all have dense forward orbits . As a weaker notion, is transitive if there exists with dense forward orbit.
Let be a Borel probability measure on . The support of is the smallest closed set of measure 1. We say that is invariant if for every Borel set . Note that the support of an invariant measure is a closed invariant subset.
The measure is called ergodic if it is invariant and every Borel set such that has measure or . By Birkhoff’s ergodic theorem, ergodicity can be interpreted as a form of asymptotic independence. More precisely, an invariant measure is ergodic if and only if
(2) |
for every pair of Borel sets (see [31]). In particular, note that the support of an ergodic measure is a transitive system. As a stronger property, the measure is mixing if
(3) |
for every pair of Borel sets. Every mixing measure is ergodic but the converse is false.
Let be the set of invariant probability measures on and be the subset of those measures which are ergodic. We can view as a subset of the dual of the space of continuous maps . If we equip with the weak- topology, then is a compact convex subset and is its set of extreme points. In particular if the system has only one invariant measure, it must be ergodic; and we call uniquely ergodic. Standard results from functional analysis imply that any invariant measure can be decomposed in terms of ergodic measures. More precisely, for every invariant measure , there exists a Borel probability measure on such that
(4) |
More details can be found in e.g. [32, Chapter 12].
1.2 Shift spaces
We now turn to symbolic dynamics. Let be a finite alphabet. We denote by the set of two-sided infinite sequences over equipped with the product topology, where has the discrete topology. We denote by the shift transformation on , defined by if for all . A shift space on the alphabet is, by definition, a closed subset of which is invariant under the shift transformation. Note that is a topological dynamical system.
Let be the free monoid on , be the empty word, and . We denote by the set of finite words which appear in the elements and by the set of words of length in . For a shift space, transitivity and minimality can be characterized in terms of the language . A shift space is transitive if and only if for every , there is some such that . Moreover is minimal if and only if for every , there is an such that every word of appears in every word of . Shift spaces which are transitive are also called irreducible.
For words of length respectively, we define the right and two-sided cylinders by
The two-sided cylinders form a clopen basis for the topology of . For , we define
Let be a Borel probability measure on a shift space . By a slight abuse of notation, we also denote by the map which assigns to a word the number . With this notation, we have and
We extend this to subsets by letting . When the cylinders for are disjoint, we have . Moreover, if is an invariant measure, then
(5) |
When the cylinders for are disjoint, we have .
Observe that the support of an invariant measure on is a shift space of measure 1, and when the measure is ergodic, is irreducible.
A Bernoulli measure is the simplest case of an ergodic measure on . The values for are given by a morphism such that . It corresponds, in classical terms of probability theory, to a sequence of independent identically distributed random variables, where . A Bernoulli measure is in fact mixing. Further mixing examples can be found among sofic measures, also called rational measures or hidden Markov measures [20, 11]. See Section 6 for a discussion on this topic.
Another important source of examples is the following. A substitution is a monoid morphism . The substitution is primitive if there is an such that every occurs in every . The shift , called a substitution shift, is the set of all such that all words in appear in some , , . If is primitive then is minimal, and uniquely ergodic [27].
Example 1.1.
The Fibonacci substitution is the morphism defined by . It is primitive and the substitution shift is called the Fibonacci shift. A description of its unique ergodic measure can be found e.g. in [14, Example 3.8.19].
The Fibonacci shift also belongs to the family of Sturmian shifts, whose definition may be recalled in [25]. More precisely, the Fibonacci shift is Sturmian of slope . The following is an example of an automatic sequence (see [1]).
Example 1.2.
The primitive substitution is called the Thue–Morse substitution. The shift is called the Thue–Morse shift. Its unique ergodic measure is described in [14, Example 3.8.20].
1.3 Density of a language
Let be a language on and let be an ergodic measure on with support . We define the density of relative to as
whenever the limit exists. In other words is the Cesàro limit of . When the classical limit of exists, we say that has a density in the strong sense. It is known that when is a Bernoulli measure, the density of any rational language exists, and if has rational values on letters, all densities are rational numbers [5, Theorem 2.1].
Let us note some basic properties of the density. If has a density, then , as for every . Moreover, since when , we have . Thus if satisfy then . The density is also finitely additive: if have densities and , then has density . Additionally, we have , and if then has density . However, the density of an intersection might not exist, even when the density of both and exist.
Example 1.3.
On a fixed finite alphabet , consider the two languages:
It is clear that (no matter the measure ). However, it can be shown that the sequence of sums has subsequences and converging to and respectively, thus does not exist.
In the above example, the language is not rational. When both languages are rational our main result (Theorem 4.1) implies that the density of the intersection also exists.
2 Density of ideals
In this section, we show how to calculate densities for languages that are ideals of (and thus not necessarily rational). We start with right ideals, that is, languages such that . The set is the minimal generating set of as a right ideal, which means that and is contained in every other set with this property. Moreover the set is a prefix code, meaning that no element of is a proper prefix of another element of . For example, for , the language is the set of words that have the letter as a prefix. Then one has .
Proposition 2.1.
Let be a probability measure on and be a right ideal of . Then has a density in the strong sense and where .
Proof.
Let be the support of . Since is a prefix code,
where the last equality uses the fact that for all . Clearly this tends to when .
Next we establish a similar result for left ideals of , that is, languages such that . Similar to the right-sided case, the set is the minimal generating set of as a left ideal and also a suffix code, i.e., no element of is proper suffix of another.
Proposition 2.2.
Let be an invariant probability measure of and be a left ideal of . Then has a density in the strong sense and where .
Proof.
Let be the support of . Since is a suffix code,
where the last equality uses the fact that since is invariant, for all . By invariance of again, this tends to when .
The density of a left ideal may not exist if the measure is not invariant, as shown next.
Example 2.3.
Let and let be the Dirac measure of , that is, the probability measure on such that if and otherwise. Then, for , the density of is the frequency of in the sequence . If the frequency of does not exist in , the language does not have a density. For example, if , then the frequency of does not exist. Indeed, the frequency of is in , while it is close to in .
Next we consider the case of a quasi-ideal, that is, the intersection of a left ideal and a right ideal. In this case we need the stronger assumption that is ergodic.
Proposition 2.4.
Let be an ergodic measure on , be a right ideal of , and be a left ideal of . Then has a density and where and . Moreover, if is mixing, then has a density in the strong sense.
Proof.
Let be the support of . Fix and and let . Then if and otherwise
and thus using Equation (2),
This shows that
If is mixing, then with similar arguments
which shows that the density exists in the strong sense.
Example 2.5.
If , then the language has density with respect to the unique invariant measure on . However is not mixing and the density does not exist in the strong sense as alternates between 0 and 1.
Next we turn to two-sided ideals, that is, languages such that .
Proposition 2.6.
Let be an ergodic measure on with support . Every two-sided ideal that intersects has density in the strong sense.
Proof.
Let and . Then and by the formulas for right and left ideals, the density exists in the strong sense and . But, using the formula for quasi-ideals, we also have , so or 1. The fact that implies .
Let be a shift space. We derive from Proposition 2.6 the following property for -thin codes, where the languages such that there exists satisfying are called -thin by the terminology of [6]. A suffix code is -maximal if it is not properly included in a suffix code . A dual notion holds for prefix codes. For example, every , for , is an -maximal suffix code.
Proposition 2.7.
Let be an ergodic measure with support and let be an -maximal prefix or suffix code. If is -thin, then .
Proof.
We assume that is an -maximal suffix code. Let be such that . We claim that . Indeed, let be such that . Since is -maximal, either has a suffix in or is a suffix of some . The second case being impossible, we conclude that , which proves the claim. Therefore, we have . Then by Propositions 2.6 and 2.2, we have . The proof for the dual statement for prefix codes works analogously. In particular, a finite prefix or prefix code is -maximal if and only if for an ergodic measure with support .
3 J-class of a shift space
This section is devoted to -classes of finite monoids associated with shift spaces. The reader who is not familiar with semigroup theory and Green’s relations might want to consult textbooks such as [7, 24, 18, 21, 15, 16]. The notion of a -class discussed here also appeared in [28, 29], and is tangentially related with the work of Almeida on free profinite semigroups [2]. See also the survey [13] for more on the connections between Green’s relations and automata theory.
3.1 Definition and first properties
Let be a shift space on and let be a morphism onto a finite monoid . We first introduce two subsets of naturally associated with .
Definition 3.1.
Let be the intersection of all two-sided ideals of such that , called the -minimal ideal of . Let be the set of elements of which generate as a two-sided ideal, i.e.,
It follows from the definition that is a -class. Consider the quasi-order defined on by . Note that if and only if and . The next proposition establishes some basic properties of when is irreducible.
Proposition 3.2.
Let be an irreducible shift space on and let be a morphism onto a finite monoid . Then
-
1.
is an ideal of which meets ;
-
2.
;
-
3.
is the non-empty set of -minimal elements of ;
-
4.
Either is the minimal ideal of , or is the unique 0-minimal ideal in the quotient of by the largest ideal of which does not meet .
Proof.
1. Let be two ideals which meet . Let be such that and . Since is irreducible, there is a word such that . Then . This proves that is an ideal which meets .
2. Let and let . Then is in . This proves the inclusion from left to right. Conversely, let be such that . Then, the ideal generated by is contained in and it meets . This implies and therefore is in .
3. Let be -minimal in . Fix . By irreducibility there is such that . It follows that , which by minimality implies . This shows that generates an ideal contained in every ideal which meets , thus .
Assume next that . Let . It is clear that is the largest ideal of which does not meet . It is non-empty since it contains the minimal ideal by assumption. Let us show that is a prime monoid (see [7, Section 1.12]). Take which are . Then there exist such that and , where . By irreducibility there is such that , hence , and in particular . This shows that is prime, and thus it admits a unique 0-minimal ideal, by [7, Proposition 1.12.9]. Finally notice that any non-zero element of the quotient must satisfy for some , thus it is -above some element of . This implies that is the 0-minimal ideal of .
Example 3.3.
Let be the automaton depicted, alongside its transition monoid, in Figure 1 and be the Fibonacci shift (Example 1.1). Let be the transition morphism of . Then , and since does not contain , it follows that is the -class of . In this example, the automaton is the minimal automaton of the -maximal prefix code .
The following result links the -class with the densities of the languages recognized by . Roughly speaking, it shows that the -class concentrates the density.
Proposition 3.4.
Let be an ergodic measure on with support . Let be a morphism onto a finite monoid . Then the density of exists in the strong sense and .
Proof.
It follows from Proposition 3.2 that , hence . But the density of exists in the strong sense and is by Proposition 2.6.
Let us highlight a simple consequence of this.
Corollary 3.5.
Let be an ergodic measure with support a shift space . Let be a morphism onto a finite monoid . For every , the density of exists in the strong sense and is 0.
Proof.
Indeed, let , . Then as and the density of has density 1 in the strong sense,
3.2 On aperiodic languages
The next theorem concerns the density of aperiodic languages. Recall that a language is aperiodic if it can be recognized by an aperiodic monoid. By Schützenberger’s theorem [38], aperiodic languages are precisely the star-free languages, as well as the languages defined by first-order formulas (see [30, Theorem 4.1]). The density of aperiodic languages was also studied, from a logic perspective, by Lynch [26]. Lynch’s definition of density involves sequences of Bernoulli measures, thus it is both more general than our definition (since we use only one measure) and much more particular, since we use more general measures than Bernoulli measures.
Theorem 3.6.
An aperiodic language has a density with respect to an ergodic measure . More precisely, there exist a finite number of pairs of a prefix code and a suffix code such that and
(6) |
Moreover, if the measure is mixing, then the density exists in the strong sense.
Proof.
Let be an ergodic measure and be a morphism onto an aperiodic monoid . Let , let and let . It is enough to prove that Equation (6) holds for such . If , then in the strong sense by Corollary 3.5, so we may assume that . We claim that
Indeed, assume that . Then , and thus by the second part of Proposition 3.2. But then and since is aperiodic, we have . It follows that and . This concludes the proof of the claim, as the other inclusion is trivial. Finally, we can use Proposition 2.4 to deduce that , where and , and that the density exists in the strong sense if is mixing.
Let us give two examples to illustrate Theorem 3.6, starting with an aperiodic language.
Example 3.7.
Let , whose minimal automaton may be found in [33, Chapter 4, Example 2.1]. Let stand for its transition monoid. Note that is aperiodic and thus star-free, which is not obvious. A star-free expression of may be found in [33, Chapter 4, Example 2.1]. Let be Thue–Morse shift and let be the unique invariant measure on (Example 1.2). The -class is the -class of in [33, Chapter 4, Example 2.1]. Combining Equation (6) with the expression of in [33, Chapter 4, Example 2.1], we get
With the values of from [14, Example 3.8.20], we find
and similarly . Thus .
The next example is a group language whose intersection with the shift space behaves like an aperiodic language.
Example 3.8.
Let be the orbit of the periodic sequence . Thus consists of three elements and has for unique ergodic measure the uniform probability measure . Let be defined by and . Consider the rational language . Then one sees
and thus .
The same result can be obtained using Theorem 3.6. First, observe that has the same intersection with as the language where . The language is recognized by the automaton depicted in Figure 2. The transition monoid of is an aperiodic monoid with 27 elements, hence turns out to be star-free. The -class , depicted in Figure 2, consists of 9 elements, 5 of which belong to the image of (indicated in yellow). Taking for instance , we find that and , and thus by Equation (6); likewise for all other elements using Equation (6). Thus we recover the fact that .
3.3 Decidability and degree
Next we consider the question of whether membership in is decidable. We say that a shift space is rationally decidable if the emptiness of is decidable for every rational language . Sofic shifts are obviously rationally decidable. The class of rationally decidable shift spaces also includes all substitution shifts by a result of [35, Lemma 3] (see also [4, Lemma 3.15] and [12]).
Proposition 3.9.
Let be a rationally decidable shift space. Then for every morphism , there is an algorithm which decides which elements are in .
Proof.
We have if and only if for every such that . Since is rationally decidable, this is decidable for every . Therefore, we can decide whether , and then whether .
The -class is also linked with the following notion of degree. Let be an automaton on and be its transition morphism. The minimal rank of the elements of viewed as partial mappings is called the -degree of the automaton, denoted . Note that [28, Proposition 3.2] states that contains all elements of rank . For instance the automaton from Example 3.8 has -degree 2, while the one in Example 3.3 has -degree 1. This result also implies that is computable if and only if membership in is decidable (cf. Proposition 3.9 for cases where the latter is decidable).
The notion of -degree has also been studied in relation with codes [6, 3]. Let be an irreducible shift, let be a rational prefix code and let be the minimal automaton of . If is -maximal, then its -degree (that is, ) is larger than or equal to . When is a finite -maximal bifix code (i.e. both prefix and suffix), then the -degree of can also be defined in terms of the number of parses of elements of [6].
4 Existence of the density
The goal of this section is to establish the existence of density of regular languages under all invariant measures. More precisely, we will prove the following, which is our main theorem.
Theorem 4.1.
Let be an invariant measure on . Then every rational language has a density with respect to .
The main ingredient for the proof is the dynamical system defined as follows, called a skew product. Let be an irreducible shift space and a morphism onto a finite monoid. Fix an -class of such that . Let act on the right of by if and otherwise. The specific choice of an -class class plays no role here, as long as satisfies .
Definition 4.2.
The skew product is the system where
Note that the projection satisfies . It follows that if is an invariant (respectively ergodic) measure on , then is an invariant (respectively ergodic) measure on . When is a group, then and forms a subsystem of , which in effect means we can get rid of 0. In particular we recover the type of skew products studied in the preprint [9]. Next, we introduce a natural probability measure on induced by a measure on . In the group case, we recover the product of with the normalized counting measure on the group considered in [9].
Definition 4.3.
Fix an invariant probability measure on . The weighted counting measure on the skew product is the Borel measure defined by , and for every and ,
where is the cardinality of the -classes of and , for , is the suffix code such that .
That is a well-defined Borel measure on follows from Carathéodory’s extension theorem, since the above formula defines a pre-measure on the Boolean algebra of clopen sets of . Note that if , then . For an -class , let be the common value of for . The following technical lemma will be useful. In its proof, we use the following notion: we call a monoid stable if for every , the implications and hold. Every finite monoid is stable [18, Lemma 1.1, Chapter V].
Lemma 4.4.
The union over all -classes of is a suffix code such that .
Proof.
The fact that is a suffix code is a consequence of the fact that the monoid is stable. Moreover, is -maximal since, for all , there exists such that , by irreducibility and the fact that . Note that a word such that cannot be a proper factor of any element of , since is a suffix code. Thus there must exist such that (simply fix and then take ). It follows that by Proposition 2.7.
Next we establish some properties of the weighted counting measure.
Proposition 4.5.
The weighted counting measure is an invariant probability measure on the skew product which satisfies .
Proof.
First we show that is invariant under the map . Note that it suffices to check invariance for sets of the form . First, assume that . If we let , , then can be expressed as the disjoint union
and from the definition of we find
Next let us treat the case where , or in other words where . Observe that
where the unions are taken over pairs such that . Since is a suffix code by Lemma 4.4, the second union in the above equation is disjoint (as is the first, for obvious reasons). Thus we have
Finally, let us show that for every Borel set . Using Lemma 4.4 together with the invariance of , we have
where the last equality follows since . Taking , we find that , which shows that is indeed a probability measure.
The following lemma will also be needed for the proof of Theorem 4.1. Its proof uses standard arguments from ergodic theory. We include it for the sake of completeness.
Lemma 4.6.
For every ergodic measure on , there exists an ergodic measure on such that and .
Proof.
Let be the set of all invariant probability measures on and the subset of those measures such that and . Note that contains the weighted counting measure by Proposition 4.5 and thus . Moreover, is a closed convex subspace of , so it must contain an extreme point by the Krein–Milman theorem. Let us show that is also an extreme point of . Suppose that for some and . It is clear that both and must give to zero measure, and the fact that is an extreme point in the convex set of invariant measures on implies that . Thus , contradicting the fact that is an extreme point of . Since the extreme points of are precisely the ergodic measure on , we are done.
The next proposition is a more precise form of Theorem 4.1 for the case where is ergodic. Note that the statement uses Lemma 4.6 implicitly for the existence of .
Proposition 4.7.
Let be an ergodic measure on with support a shift space . Let be a morphism onto a finite monoid and let for some . Fix an -class of the -class . We set the notation . Then if and otherwise
(7) |
where is any ergodic measure on such that and .
Proof.
If , then by Corollary 3.5. We may now assume that . Let be the prefix code such that . For , let
We claim that for every such that , one has
The left-to-right inclusion is obvious. For the converse, we take such that . This means that there exists some , with , such that and furthermore where . Clearly , hence by Proposition 3.2 and stability of . Moreover our choice of guarantees that , thus by stability. By Green’s lemma, is a bijection between the -classes of and . Since it follows that , i.e. . Thus which proves the claim.
As a result, we have
Next we claim that for , there is such that for every . First observe that
since projects to . Moreover since is a prefix code, the cylinders for are all disjoint, and thus we may write
But note that this is a tail of the series
and thus the claim immediately follows.
Using the above claim together with the ergodicity of , this gives
On the other hand, we have
concluding the proof.
In order to conclude the proof of Theorem 4.1, we need to deduce the existence of densities for a general invariant measure. This is done using the ergodic decomposition discussed at the end of Section 1.1.
Proof of Theorem 4.1.
Let be a rational language and be an invariant measure. Let be the set of ergodic measure on the support of and consider the ergodic decomposition of as in Equation (4). By Proposition 4.7, exists for every . Finally by the dominated convergence theorem
When the weighted counting measure is ergodic, we can apply Proposition 4.7 to obtain formulas based on the density of ideals, which are easily computable (Section 2). This generalizes a result of [7] where the same formula is proved for a Bernoulli measure.
Theorem 4.8.
Let be an ergodic measure on with support a shift space . Let be a morphism onto a finite monoid. Fix an -class of . If the weighted counting measure is an ergodic measure on the skew product , then, for every , the density of is
(8) |
where is the cardinality of the -classes of .
Proof.
Let be the weighted counting measure on . Let be the prefix code such that . Then Equation (7) reduces to
where runs over the -classes of and is the common value of for the elements . By Lemma 4.4 and since is a prefix code,
and therefore by Propositions 2.1 and 2.2
There are known examples where the skew product has more than one ergodic measure. In Example 3.8, the skew product of with has two orbits, each one being the support of an ergodic measure, and the weighted counting measure is non-ergodic.
5 On algebraic properties of the density
Let us highlight a corollary which generalizes the fact that, when is a Bernoulli measure with rational values, the density of a rational language is rational [5].
Corollary 5.1.
Let be an extension of such that for every rational language . Then, for every rational language on the alphabet which satisfies the hypotheses of Theorem 4.8, the density of belongs to .
The hypothesis that is satisfied when is a Markov measure (or, more generally, a sofic measure) defined by a transition matrix and an initial vector with coefficents in . More details can be found in Section 6. It is also satisfied when all the values of on are in and the support of is minimal. Indeed, in this case, consider a rational language . If every word of is a factor of some word of , then by Equation (8), which implies . Otherwise, the intersection is finite and thus the conclusion follows. Let us finish with an example.
Example 5.2.
Let be the Fibonacci shift (Example 1.1) and be the automaton depicted in Figure 3. Let be the unique ergodic measure on .
Let be the transition morphism of and , . Let be the -class of . Note that is an idempotent which belongs to the -class .
Let be the weighted counting measure on . We claim that is an ergodic measure. First observe that has two closed invariant subsets
Note that and (in fact is the support of ). Consider the morphism defined by and and the corresponding skew product . The weighted counting measure on this skew product is ergodic by [9, Corollary 8.12]. Furthermore, one can show that
is a continuous map such that and . Therefore the weighted counting measure on is ergodic, and the hypotheses of Theorem 4.8 are satisfied.
The values for are all in the quadratic extension where is the golden ratio [8, Theorem 2]. By Corollary 5.1 it follows that for every . For instance the language satisfies . Since (cf. [14, Example 3.8.19]), we get that from Theorem 4.8 (noting that the -classes of have size 2). Notice also that the language has the same intersection with as the submonoid generated by . The language is recognized by with as initial and terminal state. Since is uniquely ergodic, we have .
6 Markov and sofic measures
This section discusses how our results may be applied to the case of Markov, and more generally sofic measures. The main result, Proposition 6.4, shows that sofic measures satisfy the condition on field extensions from Corollary 5.1.
First, recall that a Markov measure (also called a Markov chain) is given by an -stochastic matrix (its transition matrix) and a stochastic -vector (its initial vector) which is a left eigenvector of for the eigenvalue . Then, for , with , we define
The measure is invariant because . It is ergodic if the matrix is irreducible and it is mixing if is primitive (see [31]). A shift space has finite type if for some finite set , called the set of forbidden blocks. The support of a Markov measure is the shift of finite type defined by the set of forbidden blocks where are such that . In terms of probability theory, a Markov measure is defined by a sequence of random variables , as for a Bernoulli measure, but this time depends on . When depends on we say that is a Markov measure of order .
A sofic measure (also called a hidden Markov chain) is given by a shift of finite type on the alphabet , a Markov measure on , and a map from onto an alphabet . We extend to a morphism from to . Its extension to a map from to is called a -block map. Then, for , we define
The support of is contained in the sofic shift (a shift is called sofic if is rational). A sofic measure is invariant. It is ergodic if is ergodic (see [11]).
Example 6.1.
Consider the Markov measure on defined by the pair
The support of is the shift of finite type represented in Figure 4 on the left. Using the -block map and , we obtain an invariant sofic measure defined by the diagram of Figure 4 on the right.
It can be shown that this sofic measure is not a Markov measure of order for any (see [11]).
A map is -rational if there is a morphism from into the monoid of -matrices with coefficients in , a row vector and a column vector such that
for every . The triple is called a linear representation of . The following is from [20] (see also the survey [11]).
Proposition 6.2.
A probability measure on is sofic if and only if the associated probability distribution is -rational.
The probability measure will be invariant if and only if the linear representation can be chosen such that the matrix is stochastic, with and .
Example 6.3.
Let be a language and be a probability measure on . The generating series of is the formal series
Therefore, the density of (if it exists) is the limit in average of the coefficients of .
A formal series , with , is -rational if the map is -rational. In this case, we have for two polynomials with real coefficients. The following statement, originally due to Berstel, is well known (see [15] for example).
Proposition 6.4.
Let be a rational language. If is a sofic measure, then is -rational. Let be a subfield of containing the values of on . Then and .
Proof.
Let be defined by
Thus, is the product of the values of and of the characteristic function of . The map is -rational by Proposition 6.2 and is -rational since is rational. Therefore, by [15, Theorem 5.2], the map is -rational. Set . Then is -rational. Since , this proves that is -rational.
By [15, Theorem 7.2], there is an integer such that exists for . Moreover whenever . This implies that exists and is in . Finally, we have for two polynomials . Since , we may assume by [15, Proposition 3.2]. Thus, if is finite, the radius of convergence of is and the sum is equal to , which is in .
Example 6.5.
Let be the Bernoulli measure on defined by , . Let . Then
and consequently .
References
- [1] Jean-Paul Allouche and Jeffrey Shallit. Automatic Sequences. Cambridge University Press, 2003. doi:10.1017/cbo9780511546563.
- [2] Jorge Almeida. Profinite semigroups and applications. In V. Kudryavtsev and I. G. Rosenberg, editors, Structural Theory of Automata, Semigroups, and Universal Algebra, volume 207 of NATO Science Series II: Mathematics, Physics and Chemistry, pages 1–45. Springer, 2005. doi:10.1007/1-4020-3817-8_1.
- [3] Jorge Almeida, Alfredo Costa, Revekka Kyriakoglou, and Dominique Perrin. On the group of a rational maximal bifix code. Forum Math., 32(3):553–576, 2020. doi:10.1515/forum-2018-0270.
- [4] Marie-Pierre Béal, Dominique Perrin, and Antonio Restivo. Decidable problems in substitution shifts. J. Comput. System Sci., 143, 2024. doi:10.1016/j.jcss.2024.103529.
- [5] Jean Berstel. Sur la densité asymptotique de langages formels. In M. Nivat, editor, Automata Languages and Programming, pages 345–358. North-Holland, 1972.
- [6] Jean Berstel, Clelia De Felice, Dominique Perrin, Christophe Reutenauer, and Giuseppina Rindone. Bifix codes and Sturmian words. J. Algebra, 369:146–202, 2012.
- [7] Jean Berstel, Dominique Perrin, and Christophe Reutenauer. Codes and Automata. Cambridge University Press, 2009.
- [8] Valérie Berthé. Fréquences des facteurs des suites sturmiennes. Theor. Comput. Sci., 165(2):295–309, 1996. doi:10.1016/0304-3975(95)00224-3.
- [9] Valérie Berthé, Herman Goulet-Ouellet, Carl-Fredrik Nyberg-Brodda, Dominique Perrin, and Karl Petersen. Density of group languages in shift spaces, 2024. doi:10.48550/arXiv.2403.17892.
- [10] Manuel Bodirsky, Tobias Gärtner, Timo von Oertzen, and Jan Schwinghammer. Efficiently computing the density of regular languages. In LATIN 2004: Theoretical Informatics, pages 262–270. Springer Berlin Heidelberg, 2004. doi:10.1007/978-3-540-24698-5_30.
- [11] Mike Boyle and Karl Petersen. Hidden Markov processes in the context of symbolic dynamics, pages 5–71. Cambridge University Press, 2011. doi:10.1017/cbo9780511819407.002.
- [12] Olivier Carton and Wolfgang Thomas. The monadic theory of morphic infinite words and generalizations. Inf. Comput., 176(1):51–65, 2002. doi:10.1006/inco.2001.3139.
- [13] Thomas Colcombet. Green’s relations and their use in automata theory. In Adrian-Horia Dediu, Shunsuke Inenaga, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, volume 6638 of Lecture Notes in Computer Science, pages 1–21. Springer, 2011. doi:10.1007/978-3-642-21254-3_1.
- [14] Fabien Durand and Dominique Perrin. Dimension Groups and Dynamical Systems. Cambridge University Press, 2022. doi:10.1017/9781108976039.
- [15] Samuel Eilenberg. Automata, Languages and Machines, vol. A. Pure and applied mathematics. Academic Press, 1974.
- [16] Samuel Eilenberg. Automata, Languages and Machines, vol. B. Pure and applied mathematics. Academic Press, 1976.
- [17] N. Pytheas Fogg. Substitutions in dynamics, arithmetics and combinatorics, volume 1794 of Lecture Notes in Mathematics. Springer-Verlag, 2002.
- [18] Pierre A. Grillet. Semigroups: An Introduction to the Structure Theory. Marcel Dekker, 1995. doi:10.4324/9780203739938.
- [19] G. Hansel and D. Perrin. Codes and Bernoulli partitions. Math. Syst. Theory, 16(1):133–157, 1983. doi:10.1007/BF01744574.
- [20] G. Hansel and D. Perrin. Rational probability measures. Theor. Comput. Sci., 65(2):171–188, 1989. doi:10.1016/0304-3975(89)90042-x.
- [21] John M. Howie. Fundamentals of semigroup theory. Oxford science publications. Oxford University Press, 1995. doi:10.1093/oso/9780198511946.001.0001.
- [22] Toshihiro Koga. On the density of regular languages. Fundam. Inform., 168(1):45–49, 2019. doi:10.3233/fi-2019-1823.
- [23] Jakub Kozik. Conditional densities of regular languages. Electron. Notes Theor. Comput. Sci., 140:67–79, 2005. doi:10.1016/j.entcs.2005.06.023.
- [24] G. Lallement. Semigroups and Combinatorial Applications. Wiley, 1979.
- [25] M. Lothaire. Combinatorics on Words. Cambridge University Press, 1997. doi:10.1017/cbo9780511566097.
- [26] James F. Lynch. Convergence laws for random words. Australas. J. Combin., 7:145–156, 1993. URL: http://ajc.maths.uq.edu.au/pdf/7/ocr-ajc-v7-p145.pdf.
- [27] Pierre Michel. Stricte ergodicité d’ensembles minimaux de substitution. C. R. Acad. Sci., 278:811–813, 1974.
- [28] Dominique Perrin. Codes and automata in minimal sets. In Florin Manea and Dirk Nowotka, editors, Combinatorics on Words, volume 9304 of Lecture Notes in Computer Science, pages 35–46. Springer, 2015. doi:10.1007/978-3-319-23660-5_4.
- [29] Dominique Perrin and Paul E. Schupp. Automata on the integers, recurrence distinguishability, and the equivalence and decidability of monadic theories. In Proceedings of the First Annual IEEE Symposium on Logic in Computer Science (LICS 1986), pages 301–304. IEEE Computer Society Press, 1986.
- [30] Dominique Perrin and Jean Éric Pin. Infinite Words: Automata, Semigroups, Logic and Games. Elsevier, 2004.
- [31] Karl E. Petersen. Ergodic Theory. Cambridge University Press, 1983. doi:10.1017/cbo9780511608728.
- [32] Robert R. Phelps. Lectures on Choquet’s theorem. Lecture Notes in Mathematics. Springer Berlin Heidelberg, 2001. doi:10.1007/b76887.
- [33] Jean-Éric Pin. Varieties of formal languages. Springer New York, 1986.
- [34] M. Queffélec. Substitution Dynamical Systems: Spectral Analysis, volume 1294 of Lecture Notes in Mathematics. Springer-Verlag, 2010. doi:10.1007/978-3-642-11212-6.
- [35] Ville Salo. Decidability and universality of quasiminimal subshifts. J. Comput. Syst. Sci., 89:288–314, 2017. doi:10.1016/j.jcss.2017.05.017.
- [36] Arto Salomaa and Matti Soittola. Automata-Theoretic Aspects of Formal Power Series. Springer New York, 1978. doi:10.1007/978-1-4612-6264-0.
- [37] M. P. Schützenberger. Sur certains sous-monoïdes libres. Bull. Soc. Math. Fr., 93:209–223, 1965. doi:10.24033/bsmf.1623.
- [38] Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Inform. Control, 8(2):190–194, 1965. doi:10.1016/s0019-9958(65)90108-7.
- [39] Ryoma Sin’ya. An automata theoretic approach to the zero-one law for regular languages: Algorithmic and logical aspects. Electron. Proc. Theor. Comput. Sci., 193:172–185, 2015. doi:10.4204/eptcs.193.13.
- [40] William A. Veech. Strict ergodicity in zero dimensional dynamical systems and the Kronecker–Weyl theorem mod 2. Trans. Amer. Math. Soc., 140:1, 1969. doi:10.2307/1995120.
- [41] William A. Veech. Finite group extensions of irrational rotations. Israel J. Math., 21(2):240–259, 1975. doi:10.1007/BF02760801.
- [42] Peter Walters. An Introduction to Ergodic Theory, volume 79 of Graduate Texts in Mathematics. Springer, 1982.