Deciding Sparseness of Regular Languages of Finite Trees and Infinite Words Kord Eickmeyer, Georg Schindling Abstract We study the notion of sparseness for regular languages over finite trees and infinite words. A language of trees is called sparse if the relative number of n n -node trees in the language tends to zero, and a language of infinite words is called sparse if it has measure zero in the Bernoulli probability space. We show that sparseness is decidable for regular tree languages and for regular languages of infinite words. For trees, we provide characterisations in terms of forbidden subtrees and tree automata, leading to a linear time decision procedure. For infinite words, we present a characterisation via infix completeness and give a novel proof of decidability. Moreover, in the non-sparse case, our algorithm computes a measurable subset of accepted words that can serve as counterexamples in almost-sure model checking. Our findings have applications to automata based model checking in formal verifications and XML schemas, among others. 1 Introduction We call a language of finite objects sparse if the relative number of n -element objects in the language tends to zero: For a language L\subseteq\Sigma^{*} of words we set \mathbb{P}_{n}(L)\coloneqq\frac{{|L\cap\Sigma^{n}|}}{{|\Sigma^{n}|}} and call L sparse if \lim_{n\to\infty}\mathbb{P}_{n}(L)=0 . Likewise, if L_{T} is a language of \Sigma -labelled trees and \mathcal{B}_{n}^{\Sigma} is the set of all such trees with n nodes, we set \mathbb{P}_{n}(L_{T})\coloneqq\frac{{|L_{T}\cap\mathcal{B}_{n}^{\Sigma}|}}{{|\mathcal{B}_{n}^{\Sigma}|}} and call L_{T} sparse if \lim_{n\to\infty}\mathbb{P}_{n}(L_{T})=0 . For a language L_{\omega}\subseteq\Sigma^{\omega} of infinite words we turn \Sigma^{\omega} into a Bernoulli probability space and call L_{\omega} sparse if it has measure 0 . Regular languages play an important rôle both in applied and in theoretical computer science. Apart from appearing in practical applications such as pattern matching, one reason for their importance from a theoretical perspective is that they allow for several seemingly unrelated characterisations, in particular by finite monoids, finite automata, and as being definable in monadic second-order logic (MSO) by the Büchi-Elgot-Trakhtenbrot theorem [ Bü60 , Elg61 , Tra61 ] . Many problems that are undecidable or at least computationally hard for general classes of languages are computable for regular languages. In particular the emptiness problem and, more generally, the subset relation between regular languages is efficiently decidable. Naturally, the techniques used in dealing with regular languages have been adapted to other scenarios. Two of the most important and successful generalisations have been to languages of finite trees and languages of infinite words, also called \omega -languages. In both these settings, the correspondence between regular languages, automata, and definability in MSO still holds (see [ Don70 , TW68 ] and [ Bü90 ] ), yielding similar algorithmic properties as for regular languages of finite words. We provide a characterisation of sparse regular tree languages via forbidden subtrees and tree automata ( Theorem 3.7 ). As a consequence, we deduce that sparseness of regular tree languages is decidable in linear time ( Corollary 3.9 ). Furthermore, our results also provide a method for proving non-regularity of sparse tree languages ( Corollary 3.11 ). Finally, we observe that our characterisation by forbidden subtrees does not hold for non-uniform models of random binary trees, specifically the random binary search tree model ( Example 3.14 ). A major motivation for regular \omega -languages, on the other hand, is in model checking of reactive systems [ BKL08 ] . In this setting, we are given a formal specification of a system (e.g. some piece of hardware or software) and a specification of properties that the system should have or not have. If both the system and the property are specified in linear temporal logic (LTL), model checking essentially reduces to checking whether a certain regular \omega -language is empty or not. Theorem 4.4 extends this to almost sure model checking , i.e. the question whether a certain system almost surely satisfies a given property. If the system fails to do so, it is even possible to compute a counterexample, in this case a set of \omega -words of strictly positive measure that almost surely violates the condition to be checked. Note that because the complement of a regular language is again regular, and L is sparse if and only if its complement has (asymptotic) probability 1 , the same algorithms can be used to check whether a language of trees or \omega -words has (asymptotic) probability 1 . Techniques and Related Work Sparseness of regular languages was investigated by Sin’ya [ Sin15 ] . He showed that a regular language L\subseteq\Sigma^{*} over a finite alphabet \Sigma is sparse if, and only if, L has an excluded factor, i.e. \Sigma^{*}x\Sigma^{*}\cap L=\emptyset for some x\in\Sigma^{*} . The proof of this characterisation was simplified by Koga in [ Kog19 ] . We build on their insights and generalize them significantly to handle the richer settings of regular tree languages and \omega -languages. The trees we are most interested in are rooted , ordered , unranked trees, i.e. trees with a distinguished root node in which the number of children of a node is unbounded and for every node there is a linear order on the set of its children. The terms siblinged or planar are sometimes used for what we call ordered, e.g. in [ FS09 , BS09 ] . We state our results on regular tree languages in terms of binary trees with distinguished left and right children, cf. Section 2.2 . This allows for a simpler definition of tree automata and comes at no loss of generality because ordered unranked trees are bijectively MSO-interpretable in binary trees, a folklore technique that is spelled out, for example, in [ FG06 , Sec. 10.2] . Because regular languages exactly capture the expressive power of monadic second-order logic (MSO), the (asymptotic) probability of regular languages can be rephrased as the (asymptotic) probability that a random structure satisfies a certain MSO sentence. This has been well studied: For every first-order logic (FO) sentence with relational signature, the probability that a random labelled structure satisfies the sentence converges to either 0 or 1 (this was proved independently in [ GKLT69 ] and [ Fag76 ] , cf. [ EF99 , Ch. 4] ), a result that has been extended by Spencer [ Spe13 ] to Erdős-Rényi graphs with more general edge probabilities. The fact that every sentence is satisfied asymptotically with probability 0 or 1 is usually called 0 - 1 law . For monadic second-order logic (MSO), McColm [ McC02 ] showed a 0-1 law for MSO on labelled trees. Note that McColm (crucially) considers trees without a distinguished root, while our trees are rooted. More recently, Malyshkin and Zhukovskii [ MZ21 ] showed a 0-1 law for MSO on finite trees with probability measures other than uniform probabilities, namely uniform and preferential attachment. Further results on the limit behaviour of MSO sentences on various graph classes can be found in [ DK19 ] and [ AKNS18 ] . These results are not directly applicable to our setting. In fact, there can be no 0 - 1 law for regular languages: Both in trees and in \omega -words there is some designated element (such as the first position in a word or the root of a tree), and the set of all structures in which this element gets a specific label is a regular set with (asymptotic) density strictly between 0 and 1 . Recently, Niwiński et al. [ NPS23 ] proved that the exact probability of acceptance for MSO formulae in infinite random trees is computable. However, this can not be used to decide sparseness for languages of finite trees or infinite words. A necessary and sufficient condition for an \omega -language to have strictly positive measure has already been proved by Staiger [ Sta98 ] . However, Staiger does not address the question of decidability of this property, and his proof uses deep results from topology and Kolmogorov complexity, namely a connection between the subword complexity of an \omega -word \xi and the Hausdorff dimension of the regular \omega -languages containing \xi . Courcoubetis et al. [ CY95 ] treated the sparseness problem for \omega -languages under the name probabilistic emptyness and showed it to be decidable with methods similar to ours. By relating non-sparseness to infix completeness, our (shorter) proof has the additional feature of giving an exact characterisation of non-sparse \omega -languages. Furthermore, the algorithm we present in Thm. 4.4 is the first to provide a concise representation of a set M of \omega -words that is almost a subset of L , in the sense that \mathbb{P}(M\setminus L)=0 . This is extremely valuable in the context of LTL model checking, as it amounts to a non-negligible set of counterexamples. 2 Preliminaries 2.1 Languages and Automata By \Sigma we denote a finite alphabet assuming {|\Sigma|}>1 to avoid trivialities. For k\geq 0 we denote by \Sigma^{\ast} , \Sigma^{k} , and \Sigma^{\leq k} the sets of all strings, those of length k , and of length at most k , respectively. The empty string is denoted by \varepsilon . A language is any subset L\subseteq\Sigma^{*} . Concatenation of strings u,v\in\Sigma^{*} is denoted by u\cdot v or just uv , and for a language L we set L^{*}\coloneqq\{u_{1}\cdots u_{k}\mathbin{|}k\geq 0,u_{1},\ldots,u_{k}\in L\} . An \omega -word over the alphabet \Sigma is an infinite sequence a_{0}a_{1}a_{2}\cdots of letters a_{i}\in\Sigma . The set of all \omega -words is denoted by \Sigma^{\omega} , and an \omega -language is any subset L\subseteq\Sigma^{\omega} . A (finite) word u\in\Sigma^{*} and an \omega -word v\in\Sigma^{\omega} may be concatenated to uv\in\Sigma^{\omega} , and for a language U\subseteq\Sigma^{*} and an \omega -language V\subseteq\Sigma^{\omega} we set U^{\omega}\coloneqq\{u_{1}u_{2}u_{3}\cdots\mathbin{|}u_{1},u_{2},\ldots\in U\}\qquad\text{and}\qquad UV\coloneqq\{uv\mathbin{|}u\in U\text{ and }v\in V\}. A word u\in\Sigma^{*} is a prefix of v\in\Sigma^{*}\cup\Sigma^{\omega} , written u\preceq v , if v=uw for some w\in\Sigma^{*}\cup\Sigma^{\omega} . A deterministic finite automaton (DFA) over the alphabet \Sigma is a tuple \mathcal{A}=(\Sigma,Q,q_{0},\delta,A) consisting of a finite set Q of states , a designated initial state q_{0}\in Q , a transition function \delta\colon Q\times\Sigma\to Q and a set A\subseteq Q of accepting states . We extend \delta to a function \hat{\delta}\colon Q\times\Sigma^{*}\to Q by setting \hat{\delta}(q,\varepsilon)\coloneqq q and \hat{\delta}(q,aw)\coloneqq\hat{\delta}\big(\delta(q,a),w\big) for a\in\Sigma and w\in\Sigma^{*} . The automaton \mathcal{A} accepts a word w\in\Sigma^{*} if \hat{\delta}(q_{0},w)\in A . The language accepted by \mathcal{A} is the set of words accepted by it. A language is called regular if it is accepted by some DFA. For states q,q^{\prime}\in Q we say that q^{\prime} is reachable from q , written q\leadsto q^{\prime} , if \hat{\delta}(q,w)=q^{\prime} for some word w\in\Sigma^{*} . If q^{\prime} is reachable from the initial state q_{0} we just call q^{\prime} reachable. The relation \leadsto is obviously reflexive and transitive, so the relation q\approx q^{\prime}\Leftrightarrow(q\leadsto q^{\prime}\text{ and }q^{\prime}\leadsto q) is an equivalence relation. Its equivalence classes are called the reachability classes of \mathcal{A} . A reachability class C is called closed if \delta(q,a)\in C for all q\in C and a\in\Sigma There are various generalisations of finite automata to \omega -words, resulting in a robust concept of regular \omega -languages, cf. [ Tho97 ] . We use the following characterisation: Theorem 2.1 (cf. [ Sta97 ] , Thm. 3.2) . An \omega -language L\subseteq\Sigma^{\omega} is regular if and only if there is a k\geq 1 and regular languages U_{i},V_{i}\subseteq\Sigma^{*} for i=1,\ldots,k such that L=\bigcup_{i=1}^{k}U_{i}V_{i}^{\omega} . 2.2 Tree Languages We will mostly be concerned with binary trees in the sense of Knuth [ Knu97 , 2.3] . These trees have a distinguished root node, and every node may have a left and/or a right child. We formalise this as a prefix-closed language T\subseteq D^{\ast} over the alphabet D=\{l,r\} . The empty word \varepsilon denotes the root of the tree T , a node u\in T may have children ul,ur\in T and is the parent of these. For a finite alphabet \Sigma and binary tree T we call a function \lambda\colon T\to\Sigma a \Sigma -labelling of T and the pair (T,\lambda) a \Sigma -labelled binary tree. We denote the set of all finite \Sigma -labelled binary trees by \mathcal{B}^{\Sigma} . We often just write T\in\mathcal{B}^{\Sigma} and refer to the labelling as \lambda_{T} when necessary. A set L\subseteq\mathcal{B}^{\Sigma} is called a tree language . Note that \mathcal{B}^{\Sigma} contains the empty tree \emptyset . For S,T\in\mathcal{B}^{\Sigma} we say that S is a subtree of T and write S\preceq T if there exists u\in D^{\ast} such that uD^{\ast}\cap T=uS and \lambda_{S}(v)=\lambda_{T}(uv) for all nodes v\in S . Each node u\in T induces a subtree T(u) of T consisting of u and all its descendants. We write T_{l} for the left subtree T(l) and T_{r} for the right subtree T(r) of the root of T , respectively. For two trees S,T\in\mathcal{B}^{\Sigma} and a\in\Sigma we define the \Sigma -labelled binary tree \conc_{a}(S,T) which consists of the root labelled with a and has S and T as left and right subtrees respectively. For a tree language L\subseteq\mathcal{B}^{\Sigma} and T\in\mathcal{B}^{\Sigma} we define the tree languages \begin{split}LT&\coloneqq\bigcup_{a\in\Sigma}\{\conc_{a}(S,T)\mathbin{|}S\in L\}\\ LT^{-1}&\coloneqq\{S\in\mathcal{B}^{\Sigma}\mathbin{|}\text{ There exists }a\in\Sigma\text{ with }\conc_{a}(S,T)\in L\}\end{split} and TL,T^{-1}L are defined analogously. For trees T_{1},\dotsc,T_{k}\in\mathcal{B}^{\Sigma} we inductively set \begin{split}L[T_{1}]^{-1}&\coloneqq LT_{1}^{-1}\cup T_{1}^{-1}L\\ L[T_{k},\dotsc,T_{1}]^{-1}&\coloneqq(L[T_{k-1},\dotsc,T_{1}]^{-1})T^{-1}_{k}\cup T^{-1}_{k}(L[T_{k-1},\dotsc,T_{1}]^{-1}),\end{split} so L[T_{k},\dotsc,T_{1}]^{-1} is the language of all trees that can be concatenated successively with T_{k},\dotsc,T_{1} to obtain a tree from L . A tree automaton is a tuple \mathcal{A}=(\Sigma,Q,\Delta,A) consisting of a finite set Q of states , a finite alphabet \Sigma , a transition relation \Delta\subseteq(Q\cup\{\bot\})\times(Q\cup\{\bot\})\times\Sigma\times Q , and a set A\subseteq Q of accepting states. Given a \Sigma -labelled binary tree T , a run of \mathcal{A} on T is a function d\colon D^{\ast}\to(Q\cup\{\bot\}) such that - if u\notin T then d(u)=\bot , and - if u\in T then (d(ul),d(ur),\lambda_{T}(u),d(u))\in\Delta . A run d is called accepting if d(\varepsilon)\in A and we say that an automaton \mathcal{A} accepts a tree T if there is an accepting run of \mathcal{A} on T . For states q\in Q and q^{\prime}\in Q\cup\{\bot\} , we say that q^{\prime} is 1 -step reachable from q (written q\leadsto_{1}q^{\prime} ) if (q,\tilde{q},a,q^{\prime})\in\Delta or (\tilde{q},q,a,q^{\prime})\in\Delta for some a\in\Sigma and \tilde{q}\in Q\cup\{\bot\} . The reflexive transitive closure \leadsto\coloneqq\leadsto_{1}^{*} is called reachability, and a state q\in Q is called reachable if \bot\leadsto q . Equivalently, q is reachable if and only if there exists a tree T\in\mathcal{B}^{\Sigma} and a run d of \mathcal{A} on T with d(\varepsilon)=q . We call \mathcal{A} reduced if every state is reachable. 2.3 Random Trees and \omega -words For n\in\mathbb{N} we denote by \mathcal{B}^{\Sigma}_{n} and \mathcal{B}^{\Sigma}_{0 , and that i and j communicate (written i\leftrightarrow j ) if both i\to j and j\to i . Then \leftrightarrow is an equivalence relation on I and its equivalence classes are just called classes of states. A class C\subseteq I is called closed if i\in C and i\to j imply j\in C . We need the following theorem: Theorem 2.3 (cf. [ Nor97 , Thm. 1.5.6] ) . If C\subseteq I is a closed class, every i\in C is recurrent. Corollary 2.4 . If C\subseteq I is a closed class and i\in C , then \mathbb{P}(X_{t}=i\text{ infinitely often}\mathbin{|}X_{t}\in C\text{ for some }t)=1 for every s\in\mathbb{N} . 3 Characterising Sparseness of Regular Tree Languages In this section we exactly characterise regular tree languages with asymptotic density 0 by excluded factors, namely forbidden subtrees . This generalises Sin’ya’s result for regular languages. The well-known infinite monkey theorem states that a language of finite words L\subseteq\Sigma^{*} has asymptotic density 1 if \Sigma^{*}x\Sigma^{*}\subseteq L for some x\in\Sigma^{*} . This has been generalised to tree languages by Asada et al. [ AKST19 , Thm. 2.13] , who prove that contexts of up to logarithmic size appear asymptotically almost surely in certain regular tree languages. We only need a weaker version stated in Theorem 3.1 , and give a comparatively short proof of it using methods from analytic combinatorics [ FS09 ] . In Theorem 3.7 we then show that, for a regular tree language, the existence of a forbidden subtree is a necessary condition for sparseness. Theorem 3.1 . \mathds{P}_{\lim}(\{T\in\mathcal{B}^{\Sigma}\mathbin{|}S\preceq T\})=1 for every nonempty S\in\mathcal{B}^{\Sigma} . Proof. First, note that \begin{split}\overline{\mathds{P}}_{\lim}(\{T\in\mathcal{B}^{\Sigma}\mathbin{|}S\preceq T\})&=\limsup(1-\mathbb{P}\{T\in\mathcal{B}^{\Sigma}\mathbin{|}S\npreceq T\})\\ &=1-\liminf_{n\to\infty}\frac{{|\{T\in\mathcal{B}^{\Sigma}_{n}\mathbin{|}S\npreceq T\}|}}{C_{n}{|\Sigma|}^{n}}.\end{split} We fix a nonempty tree S\in\mathcal{B}^{\Sigma} and examine the asymptotic behaviour of the sequence a_{n}\coloneqq{|\{T\in\mathcal{B}^{\Sigma}_{n}\mathbin{|}S\npreceq T\}|} following the approach of [ FS09 , Example III.41] . To analyse the generating function of the sequence (a_{n})_{n} , we denote by f_{n,k} the number of \Sigma -labelled binary trees of size n that contain S as a subtree at k different positions, and let f(u,z)\coloneqq\sum_{n,k\geq 0}f_{n,k}z^{n}u^{k} be its bivariate generating function. In particular a_{n}=f_{n,0} and f(0,z)=\sum_{n}a_{n}z^{n} is the generating function of the sequence (a_{n})_{n\geq 0} . By \omega(T) we denote the number of distinct occurrences of S in a tree T\in\mathcal{B}^{\Sigma} . Then \omega(\emptyset)=0 and since S can occur in the left or right subtree, or be the whole tree T , we get \omega(T)=\omega(T_{l})+\omega(T_{r})+[T=S] , where [T=S] is 1 if T=S and 0 otherwise, for T\not=\emptyset . For the function u\mapsto u^{\omega(T)} this can be rewritten as u^{\omega(T)}=u^{\omega(T_{l})}u^{\omega(T_{r})}u^{[T=S]}=u^{\omega(T_{l})}u^{\omega(T_{r})}+[T=S](u-1), (1) and justifying algebraic manipulations of formal power series as in [ FS09 , A.5.] , we get: \displaystyle f(u,z) \displaystyle=\sum_{n=0}^{\infty}z^{n}\sum_{k=0}^{\infty}u^{k}f_{n,k}=\sum_{n=0}^{\infty}z^{n}\sum_{T\in\mathcal{B}^{\Sigma}_{n}}u^{\omega(T)} \displaystyle\overset{\eqref{eqn:occurrences}}{=}\sum_{n=0}^{\infty}z^{n}\sum_{T\in\mathcal{B}^{\Sigma}_{n}}\Big([T=S](u-1)+u^{\omega(T_{l})}u^{\omega(T_{r})}\Big) \displaystyle=\sum_{n=0}^{\infty}z^{n}\sum_{T\in\mathcal{B}^{\Sigma}_{n}}[T=S](u-1)+\sum_{n=0}^{\infty}z^{n}\sum_{T\in\mathcal{B}^{\Sigma}_{n}}u^{\omega(T_{l})}u^{\omega(T_{r})} \displaystyle=z^{m}(u-1)+1+\sum_{n=1}^{\infty}z^{n}\sum_{T\in\mathcal{B}^{\Sigma}_{n}}u^{\omega(T_{l})}u^{\omega(T_{r})} for m\coloneqq{|S|} . We set f_{n}(u)\coloneqq\sum_{T\in\mathcal{B}^{\Sigma}_{n}}u^{\omega(T)}=\sum_{k=0}^{\infty}u^{k}f_{n,k} and get \displaystyle f(u,z)-z^{m}(u-1)-1 \displaystyle=\sum_{n=1}^{\infty}z^{n}\sum_{T\in\mathcal{B}^{\Sigma}_{n}}u^{\omega(T_{l})}u^{\omega(T_{r})} \displaystyle=\sum_{n=1}^{\infty}z^{n}\sum_{j=0}^{n-1}{|\Sigma|}\Bigl(\sum_{T_{l}\in\mathcal{B}^{\Sigma}_{j}}u^{\omega(T_{l})}\Bigr)\Bigl(\sum_{T_{r}\in\mathcal{B}^{\Sigma}_{n-1-j}}u^{\omega(T_{r})}\Bigr) \displaystyle=z{|\Sigma|}\sum_{n=1}^{\infty}z^{n-1}\sum_{j=0}^{n-1}\Bigl(\sum_{T_{l}\in\mathcal{B}^{\Sigma}_{j}}u^{\omega(T_{l})}\Bigr)\Bigl(\sum_{T_{r}\in\mathcal{B}^{\Sigma}_{n-1-j}}u^{\omega(T_{r})}\Bigr) \displaystyle=z{|\Sigma|}\sum_{n=0}^{\infty}\sum_{j=0}^{n}z^{j}f_{j}(u)\cdot z^{n-j}f_{n-j}(u)=z{|\Sigma|}f(u,z)^{2}. Solving this quadratic equation for f(u,z) gives two candidate solutions f(u,z)=\frac{1\pm\sqrt{1-4z{|\Sigma|}-4{|\Sigma|}z^{m+1}(u-1)}}{2z{|\Sigma|}}, and since f(1,\frac{z}{{|\Sigma|}}) is the generating function of the Catalan numbers, subtracting the square root gives the right solution. The generating function f(0,z) of the sequence (a_{n})_{n\geq 0} is now given by f(0,z)=\frac{1-\sqrt{1-4z{|\Sigma|}+4{|\Sigma|}z^{m+1}}}{2z{|\Sigma|}}. The function f(0,z) is analytic at 0 by extending it to f(0,0)=1 . The radius around 0 , where f(0,z) is analytic is exactly the radius R , for which the polynomial p(z)\coloneqq 1-4{|\Sigma|}z+4{|\Sigma|}z^{m+1} is non-zero (cf. analyticity of \sqrt{1-z} ). Considering the reciprocal polynomial of p yields R>\frac{1}{4{|\Sigma|}} . Finally, by [ FS09 , Theorem IV.7 (Exponential Growth Formula)] there exist a subexponential factor (\eta_{n})_{n} such that a_{n}=R^{-n}\eta_{n} . Also, by Stirling’s formula there exists a subexponential factor (\theta_{n})_{n} such that C_{n}=4^{-n}\theta_{n} . In total, this yields \frac{{|\{T\in\mathcal{B}^{\Sigma}_{n}\mathbin{|}S\npreceq T\}|}}{{|\mathcal{B}^{\Sigma}_{n}|}}=\frac{a_{n}}{C_{n}{|\Sigma|}^{n}}=\frac{R^{-n}\eta_{n}}{4^{n}\theta_{n}{|\Sigma|}^{n}}=\Bigl(\frac{1}{4R{|\Sigma|}}\Bigr)^{n}\frac{\eta_{n}}{\theta_{n}}. Since the factors \eta_{n} and \theta_{n} are subexponential the sequence converges to 0 as n tends to infinity. ∎ In order to show the converse for regular tree languages, we lift the proof from [ Kog19 ] to the case of tree languages. First, we derive bounds for the asymptotic density of specific tree languages. Lemma 3.2 . For L\subseteq\mathcal{B}^{\Sigma} and T,T_{1},\dotsc,T_{k}\in\mathcal{B}^{\Sigma} the following hold: 1. \overline{\mathds{P}}_{\lim}(LT)=\frac{1}{{|\Sigma|}^{{|T|}}4^{{|T|}+1}}\overline{\mathds{P}}_{\lim}(L) 2. \overline{\mathds{P}}_{\lim}(LT^{-1}),\overline{\mathds{P}}_{\lim}(T^{-1}L)\leq{|\Sigma|}^{{|T|}}4^{{|T|}+1}\overline{\mathds{P}}_{\lim}(L) 3. \overline{\mathds{P}}_{\lim}(L[T_{k},\dotsc,T_{1}]^{-1})\leq 2^{k}{|\Sigma|}^{\sum_{i}{|T_{i}|}}4^{\sum_{i}{|T_{i}|}+k}\overline{\mathds{P}}_{\lim}(L) Proof. By \begin{split}\mathbb{P}_{n}(LT\cap\mathcal{B}^{\Sigma}_{n})&=\frac{{|(L\cap\mathcal{B}^{\Sigma}_{n-{|T|}-1})T|}}{{|\mathcal{B}^{\Sigma}_{n}|}}=\frac{{|L\cap\mathcal{B}^{\Sigma}_{n-{|T|}-1}|}}{{|\mathcal{B}^{\Sigma}_{n-{|T|}-1}|}}\frac{{|\Sigma|}\cdot{|\mathcal{B}^{\Sigma}_{n-{|T|}-1}|}}{{|\mathcal{B}^{\Sigma}_{n}|}}\\ &=\mathbb{P}_{n-{|T|}-1}(L\cap\mathcal{B}^{\Sigma}_{n-{|T|}-1})\frac{C_{n-{|T|}-1}{|\Sigma|}^{n-{|T|}}}{C_{n}{|\Sigma|}^{n}}\\ &=\mathbb{P}_{n-{|T|}-1}(L\cap\mathcal{B}^{\Sigma}_{n-{|T|}-1})\frac{1}{{|\Sigma|}^{{|T|}}}\frac{C_{n-{|T|}-1}}{C_{n}},\end{split} taking the limes superior on both sides together with the identity \lim_{n\to\infty}\frac{C_{n-k}}{C_{n}}=\frac{1}{4^{k}} proves the first part. For the second part note that (LT^{-1})T\subseteq L and hence by Lemma 2.2 together with the first part we obtain \overline{\mathds{P}}_{\lim}(L)\geq\overline{\mathds{P}}_{\lim}\big((LT^{-1})T\big)=\frac{1}{{|\Sigma|}^{{|T|}}4^{{|T|}+1}}\overline{\mathds{P}}_{\lim}(LT^{-1}), and likewise for \overline{\mathds{P}}_{\lim}(T^{-1}L) . Finally, for the third part we have \displaystyle\overline{\mathds{P}}_{\lim}(L[T_{k},\dotsc,T_{1}]^{-1}) \displaystyle=\overline{\mathds{P}}_{\lim}\Bigl((L[T_{k-1},\dotsc,T_{1}]^{-1})T^{-1}_{k}\cup T^{-1}_{k}(L[T_{k-1},\dotsc,T_{1}]^{-1})\Bigr) \displaystyle\leq\overline{\mathds{P}}_{\lim}\Bigl((L[T_{k-1},\dotsc,T_{1}]^{-1})T^{-1}_{k}\Bigr)+\overline{\mathds{P}}_{\lim}\Bigl((L[T_{k-1},\dotsc,T_{1}]^{-1})T^{-1}_{k}\Bigr) \displaystyle\leq 2{|\Sigma|}^{{|T_{k}|}}4^{{|T_{k}|}+1}\overline{\mathds{P}}_{\lim}(L[T_{k-1},\dotsc,T_{1}]^{-1}) by using the second part for the last inequality. Hence, the claim follows by induction. ∎ Lemma 3.3 . Let \mathcal{A}=(Q,\Sigma,\Delta,A) be a tree automaton. For every reachable state q\in Q there exists a tree T\in\mathcal{B}^{\Sigma} with {|T|}\leq 2^{{|Q|}}-1 such that a run of \mathcal{A} on T ends in q . Proof. Let q\in Q be reachable by \mathcal{A} , so there exists T\in\mathcal{B}^{\Sigma} such that a run of \mathcal{A} on T ends in q . If {|T|}\leq 2^{{|Q|}}-1 we are done, so assume {|T|}>2^{{|Q|}}-1 . Then there exists w\in T with {|w|}\geq{|Q|} . Let d\colon D^{\ast}\to Q\cup\{\bot\} be a run of \mathcal{A} on T , so for all u\in T it holds (d(ul),d(ur),\lambda(u),d(u))\in\Delta . We obtain a sequence [d(p^{n}(w))]_{n=0}^{{|w|}} of states, which \mathcal{A} passes from w to p^{{|w|}}(w)=\varepsilon . Since {|w|}\geq{|Q|} , by the pigeonhole principle, there must be a state in Q which occurs twice in [d(p^{n}(w))]_{n=0}^{{|w|}} . Let i,j\in\{0,\dotsc,{|w|}\} with i\neq j and d(p^{i}(w))=d(p^{j}(w)) , then either T(p^{i}(w))\preceq T(p^{j}(w)) or T(p^{j}(w))\preceq T(p^{i}(w)) . We assume T(p^{j}(w))\preceq T(p^{i}(w)) , so j>i (the other case is analogous). We obtain a new tree T by replacing T(p^{i}(w)) by T(p^{j}(w)) in T and set w^{1}\coloneqq w_{0}\dotsc w_{i-1}w_{j}\dotsc w_{{|w|}+1} , which is the new node at the position of w . Then {|w^{1}|}={|w|}-{|i-j|}<{|w|} . Since \mathcal{A} ends in the same state after running on T(p^{j}(w)) and T(p^{i}(w)) , it still ends in q after running on T_{1} . If {|w^{1}|}\geq{|Q|} the same argument applies for the sequence [d(w),d(p(w)),\dotsc,d(p^{j}(w)),d(p^{i+1}(w)),\dotsc,d(\varepsilon)] and we iteratively obtain {|w^{\ell}|}<{|Q|} after at most \ell iterations. The same argument can be applied to every node v\in T_{\ell} with {|v|}\geq{|Q|} until for all nodes v in the resulting tree it holds {|v|}<{|Q|} . A binary tree with this property has depth at most {|Q|}-1 , so its size is bounded by \sum_{k=0}^{{|Q|}-1}2^{k}=2^{{|Q|}}-1 . ∎ Next, we show that if a binary tree S occurs as a subtree in a regular language L , then there is a tree T\in L with S\preceq T that is ’not much larger’ than S : Lemma 3.4 . For every regular tree language L\subseteq\mathcal{B}^{\Sigma} there exists n\in\mathbb{N} such that for all S\in\mathcal{B}^{\Sigma} and T\in L with S\preceq T there exist T_{1},\dotsc,T_{k}\in\mathcal{B}^{\Sigma}_{<2^{n}} with k\leq n such that S\in L[T_{k},\dotsc,T_{1}]^{-1} . Proof. Let \mathcal{A}=(\Sigma,Q,\Delta,A) be a tree automaton recognising the language L . For T\in L and S\in\mathcal{B}^{\Sigma} with S\preceq T there exists w=w_{1}\cdots w_{\ell}\in T with S=T(w) . Let d\colon D^{\ast}\to Q\cup\{\bot\} be a run of \mathcal{A} on T and d_{i}=d(w_{1}\cdots w_{i})\in Q be state of \mathcal{A} at node w_{1}\cdots w_{i} in this run, for i=0,\ldots,\ell . Then d_{0}\in A (because \mathcal{A} accepts T ) and d_{i}\leadsto_{1}d_{i-1} for i=1,\ldots,\ell . If d_{i}=d_{j} for some i0 . ∎ This converse of the infinite monkey theorem for regular tree languages provides a characterisation of sparseness in terms of forbidden subtrees . In order to also obtain such a characterisation in terms of tree automata akin to [ Sin15 ] , we give the following definition. Definition 3.6 . Let \mathcal{A}=(\Sigma,Q,\Delta,A) be a tree automaton. A set of states V\subseteq Q is called a sink if for all q\in V and all q_{l},q_{r}\in Q\cup\{\bot\},a\in\Sigma it holds that \delta(q_{l},q,a),\delta(q,q_{r},a)\subseteq V . That is, V is a sink exactly if every run of \mathcal{A} remains in V once it entered a state in V . Finally, we conclude the following characterisation of sparse regular tree languages. Theorem 3.7 . Let L be a regular tree language and \mathcal{A}=(\Sigma,Q,\Delta,A) be a reduced tree automaton recognising L . Then the following assertions are equivalent: 1. \mathds{P}_{\lim}(L)=0 2. There exists a tree S\in\mathcal{B}^{\Sigma} such that \{T\in\mathcal{B}^{\Sigma}\mathbin{|}S\preceq T\}\subseteq\mathcal{B}^{\Sigma}\setminus L 3. \mathcal{A} has a sink V\subseteq Q with V\cap A=\emptyset Proof. Theorems 3.1 and 3.5 together imply 1 \Leftrightarrow 2 . 2 \Rightarrow 3 : Let S\in\mathcal{B}^{\Sigma} such that \{T\in\mathcal{B}^{\Sigma}\mathbin{|}S\preceq T\}\subseteq\mathcal{B}^{\Sigma}\setminus L . Let q_{0}\in Q be a state in which \mathcal{A} ends after reading S . Then q_{0}\in Q\setminus A since \mathcal{A} has to reject S because all trees which contain S as subtree have to be rejected. Therefore, all q_{l},q_{r}\in Q\cup\{\bot\} and a\in\Sigma satisfy \delta(q_{l},q_{0},a)\subseteq Q\setminus A and \delta(q_{0},q_{r},a)\subseteq Q\setminus A because otherwise one could construct a tree (since every state is reachable) which contains S as subtree and is accepted by \mathcal{A} . Hence, there exists a sink S\subseteq Q\setminus A which contains q_{0} . 3 \Rightarrow 2 : Let V\subseteq Q\setminus A be a sink of \mathcal{A} . There exists a tree S on which \mathcal{A} ends in a state of V . If \mathcal{A} runs on any tree containing S as a subtree, \mathcal{A} cannot leave the sink and thus cannot leave Q\setminus A . This yields \{T\in\mathcal{B}^{\Sigma}\mathbin{|}S\preceq T\}\subseteq L . ∎ Remark 3.8 . By duality, Theorem 3.7 also provides a characterisation of regular tree languages L with asymptotic density 1 : It holds \mathds{P}_{\lim}(L)=1 if and only if there exists a tree S such that S\preceq T implies T\in L , and this is the case if and only if an automaton recognising L has a sink consisting of accepting states. As a consequence of this characterisation, we obtain a simple linear time algorithm for deciding sparseness (or denseness) of regular tree languages akin to the algorithm in [ Sin15 ] . Note that in contrast to the characterisation given there, here we do not need to require that a sink is a strongly connected component. If there is a sink V\subseteq Q with V\subseteq Q\setminus A , there cannot be a sink V^{\prime}\subseteq A . Corollary 3.9 . Let L\subseteq\mathcal{B}^{\Sigma} be a regular tree language. There is an algorithm deciding whether L has asymptotic density 0 or 1 in time O(n) , where n is the number of states of a given deterministic tree automaton \mathcal{A} recognising L . Proof. We define the state graph of a deterministic tree automaton \mathcal{A}=(Q,\Sigma,\delta,A) as G_{\mathcal{A}}=(Q,\{(q,q^{\prime})\mathbin{|}\exists s\in Q,a\in\Sigma.\,\delta(s,q,a)=q^{\prime}\text{ or }\delta(q,s,a)=q^{\prime}\}) . For a set V\subseteq Q we define N^{+}_{G_{\mathcal{A}}}(V)\coloneqq\{q^{\prime}\in Q\setminus V:\exists q\in V.(q,q^{\prime})\in E(G_{\mathcal{A}})\} . A strongly connected component of \mathcal{A} is a strongly connected component of the directed graph G_{\mathcal{A}} . The linear time algorithm now is as follows: 1. Compute the set of strongly connected components of G_{\mathcal{A}} . 2. For each strongly connected component V\subseteq Q , check whether 2.1. N^{+}_{G_{\mathcal{A}}}(V)=\emptyset and 2.2. V\subseteq A or V\subseteq Q\setminus A . For the correctness, we observe that \mathcal{A} has a sink if and only if there exists a strongly connected component V\subseteq Q with N^{+}_{G_{\mathcal{A}}}(V)=\emptyset . Then the asymptotic density of L is determined by checking V\subseteq A or V\subseteq Q\setminus A by Theorem 3.7 . For the running time, the first step can be implemented to run in time O(n+n{|\Sigma|})=O(n) by [ Tar72 ] . Afterwards, for each of the at most n strongly connected components only constant-time accesses to the adjacency of G_{\mathcal{A}} and accepting states of \mathcal{A} are necessary. ∎ Unranked Trees. There is a well-known correspondence between binary trees in our sense (with left and right children) and forests of unranked trees, see, for example, Section 2.3.2 of [ Knu97 ] . Every unranked tree T can be uniquely encoded by a binary tree T^{\flat} , and the binary trees T^{\flat} obtained in this way are exactly those in which the root does not have a right child (i.e. T^{\flat}_{r}=\emptyset ). Again there are various approaches to defining regular languages of unranked trees (such as definability in monadic second-order logic), all of which are equivalent to saying that a set L of unranked trees is regular if the language L^{\flat}\coloneqq\{T^{\flat}\mathbin{|}T\in L\} of binary trees is regular in our sense. Theorem 3.7 therefore gives an exact and decidable characterisation of regular languages of unranked trees. However, this gives a necessary and sufficient condition on L^{\flat} for when a regular language L is sparse. We now show that in fact: Theorem 3.10 . A regular language L of unranked trees is sparse if, and only if, some unranked tree S does not appear as a subtree of any tree T\in L . Proof. Let S be an unranked tree with root label a\coloneqq\lambda_{S}(\epsilon)\in\Sigma . Then S is a subtree of an unranked tree T if, and only if, T^{\flat} has a node labelled a whose left subtree is exactly S^{\flat}_{l} , the left subtree of the root of S^{\flat} . (Note that S^{\flat} , being the encoding of an unranked tree, has S^{\flat}_{r}=\emptyset .) Let us say that S^{\flat}_{l} is an a -left subtree of T^{\flat} in this situation. Now if \conc_{a}(S^{\flat}_{l},\emptyset)\preceq T then in particular S^{\flat}_{l} is an a -left subtree of T , and with Theorem 3.1 we get that \mathds{P}_{\lim}(\{T^{\flat}\in\mathcal{B}\mathbin{|}S^{\flat}_{l}\text{ is an $a$-left subtreee of }T^{\flat}\})=1 for every S^{\flat}_{l}\in\mathcal{B} . Similarly, it is easy to adapt the statements and proofs of Lemma 3.4 and Theorem 3.5 to the case that S^{\flat}_{l} is an a -left subtree of T^{\flat} . ∎ Proving Non-Regularity. In another direction, Theorem 3.7 shows a sufficient condition for the non-regularity of tree languages: Corollary 3.11 . Let L\subseteq\mathcal{B}^{\Sigma} be a tree language with \mathds{P}_{\lim}(L)=0 . If L does not have a forbidden subtree, then L is not regular. Example 3.12 . We call a binary tree T\in\mathcal{B}^{\Sigma} symmetric if the left and right subtree obtained from the root are isomorphic. Let L_{\text{sym}} be the set of all symmetric binary trees, then for every a\in\Sigma and S\in\mathcal{B}^{\Sigma} we have \conc_{a}(S,S)\in L_{\text{sym}} and thus L_{\text{sym}} does not have a forbidden subtree. However, for the asymptotic density of L_{\text{sym}} we get {|L_{\text{sym}}\cap\mathcal{B}^{\Sigma}_{2n}|}=0 and \lim_{n\to\infty}\frac{{|L_{\text{sym}}\cap\mathcal{B}^{\Sigma}_{2n+1}|}}{{|\mathcal{B}^{\Sigma}_{2n+1}|}}=\lim_{n\to\infty}\frac{C_{n}{|\Sigma|}^{n+1}}{C_{2n+1}{|\Sigma|}^{2n+1}}=\lim_{n\to\infty}\frac{C_{n}}{C_{2n+1}{|\Sigma|}^{n}}=0, which yield \mathds{P}_{\lim}(L_{\text{sym}})=0 . By Corollary 3.11 we infer that L_{\text{sym}} is not a regular tree language. Random Binary Search Trees. Another prominent model for random binary trees are random binary search trees . These trees appear in the analysis of algorithms such as Quicksort and Find, cf. [ Dev86 ] . A random binary search tree on n nodes is obtained by taking a root and appending to it a left subtree of size k and a right subtree of size n-1-k independently, where k is chosen uniformly at random from \{0,\dotsc,n-1\} . Formally, we let \mathbb{P}^{\text{bst}}_{1}:\mathcal{B}^{\Sigma}_{1}\to[0,1],\penalty\ T\mapsto\frac{1}{{|\Sigma|}} and for n>1 and T\in\mathcal{B}^{\Sigma}_{n} set \mathbb{P}^{\text{bst}}_{n}(T)=\frac{1}{n{|\Sigma|}}\mathbb{P}^{\text{bst}}_{{|T_{l}|}}(T_{l})\mathbb{P}^{\text{bst}}_{{|T_{r}|}}(T_{r}) . For the asymptotic probability of a language L\subseteq\mathcal{B}^{\Sigma} we again set \mathds{P}_{\lim}^{\text{bst}}(L)\coloneqq\lim_{n\to\infty}\mathbb{P}^{\text{bst}}_{n}(L), given the limit exists. The characterisation from Theorem 3.7 however does not immediately hold for non-uniform probability measures. In the following, we consider random binary search trees and show that there are tree languages with asymptotic probability 0 which do not admit our characterisation. Lemma 3.13 . Let L\subseteq\mathcal{B}^{\Sigma} and T\in\mathcal{B}^{\Sigma} . Then \mathds{P}_{\lim}^{\text{bst}}(LT)=0 . Proof. We use the independence condition in the definition of the binary search tree distribution to obtain the following: \displaystyle\mathbb{P}^{\text{bst}}_{n}(LT\cap\mathcal{B}^{\Sigma}_{n}) \displaystyle=\sum_{S\in LT\cap\mathcal{B}^{\Sigma}_{n}}\mathbb{P}^{\text{bst}}_{n}(S) \displaystyle=\sum_{S\in L\cap\mathcal{B}^{\Sigma}_{n-1-{|T|}}}\sum_{a\in\Sigma}\mathbb{P}^{\text{bst}}_{n}(\conc_{a}(S,T)) \displaystyle=\sum_{S\in L\cap\mathcal{B}^{\Sigma}_{n-1-{|T|}}}\sum_{a\in\Sigma}\frac{1}{n|\Sigma|}\mathbb{P}^{\text{bst}}_{{|T|}}(T)\mathbb{P}^{\text{bst}}_{{|S|}}(S) \displaystyle=\sum_{S\in L\cap\mathcal{B}^{\Sigma}_{n-1-{|T|}}}\frac{1}{n}\mathbb{P}^{\text{bst}}_{{|T|}}(T)\mathbb{P}^{\text{bst}}_{{|S|}}(S) \displaystyle=\frac{1}{n}\mathbb{P}^{\text{bst}}_{{|T|}}(T)\sum_{S\in L\cap\mathcal{B}^{\Sigma}_{n-1-{|T|}}}\mathbb{P}^{\text{bst}}_{{|S|}}(S) \displaystyle=\frac{1}{n}\mathbb{P}^{\text{bst}}_{{|T|}}(T)\mathbb{P}^{\text{bst}}_{n-1-{|T|}}(L\cap\mathcal{B}^{\Sigma}_{n-1-{|T|}})\leq\frac{1}{n}. Taking the limit yields the desired result. ∎ Example 3.14 . Consider the tree language R that consists of all \Sigma -labelled binary trees T with T_{l}=\{\varepsilon\} , i.e., empty left subtree. The language R is regular because the automaton \mathcal{A}=(\{q_{0},q_{1},q_{2}\},\{a\},\Delta,\{q_{2}\}) with \Delta\coloneqq\{(\bot,\bot,a,q_{0})\}\cup\{(l,r,a,q_{1})\mathbin{|}r\neq q_{0},(l,r)\neq(\bot,\bot)\}\cup\{(l,q_{0},a,q_{2})\mathbin{|}l\in Q\cup\{\bot\}\} recognises R . By Lemma 3.13 we have \mathds{P}_{\lim}^{\text{bst}}(R)=0 , but on the other hand, for all S\in\mathcal{B}^{\Sigma} it holds that \{T\in\mathcal{B}^{\Sigma}\mathbin{|}S\preceq T\}\not\subseteq\mathcal{B}^{\Sigma}\setminus L since every tree might occur as a subtree in a right subtree from R . Also, the automaton \mathcal{A} does not have a sink. 4 Infinite Words We first review Sin’ya’s result and Koga’s simplified proof [ Kog19 ] of it and then see how it can be extended to infinite words. Definition 4.1 . For a language L\subseteq\Sigma^{*} , the infix language \infix(L) is defined as \infix(L)\coloneqq\{w\in\Sigma^{*}\mathbin{|}xwy\in L\text{ for some }x,y\in\Sigma^{*}\}. (2) The language is said to be infix complete if \infix(L)=\Sigma^{*} . In [ Sin15 ] , Sin’ya proved that a regular language L has asymptotic density strictly larger than 0 if and only if it is infix complete. Koga’s simplified proof in [ Kog19 ] hinges on the fact that for regular languages, the length of the prefix x and the suffix y in ( 2 ) may be bounded uniformly in L , independent of w . We need a slight strengthening of this in that the prefix x may actually be assumed to depend only on L , not on v . We prove this by giving an equivalent condition on DFAs accepting the language L : Lemma 4.2 . Let \mathcal{A}=(\Sigma,Q,q_{0},\delta,A) be a deterministic finite automaton in which every state is reachable. Then L(\mathcal{A}) is infix complete if, and only if, some closed reachability class contains an accepting state. In this case there is a word x\in\Sigma^{*} and a k\geq 0 such that for every v\in\Sigma^{*} there is a y\in\Sigma^{\leq k} with xvy\in L . Proof. Let us first assume that some closed reachability class C contains an accepting state q\in C\cap A . Since all states are assumed to be reachable, there is a string x\in\Sigma^{*} with \hat{\delta}(q_{0},x)=q . Now for every v\in\Sigma^{*} , q_{v}\coloneqq\hat{\delta}(q,v)\in C , and because q is reachable from every state in C there is a y_{v}\in\Sigma^{*} with \hat{\delta}(q_{v},y_{v})=q and therefore \hat{\delta}(q_{0},xvy_{v})=\hat{\delta}(q,vy_{v})=\hat{\delta}(q_{v},y_{v})=q\in A, so xvy\in L(\mathcal{A}) . Since C is finite and the string y depends only on q_{v}\in C we may assume {|y_{v}|}\leq k for some k depending only on \mathcal{A} . For the converse direction, we adversarially construct a string v such that for every q\in Q , \hat{\delta}(q,v) is an element of some closed reachability class. Then for all x,y\in\Sigma^{*} , \hat{\delta}(q,xvy) is an element of a closed reachability class, and if no such class contains an accepting state we get xvy\not\in L(\mathcal{A}) , so L(\mathcal{A}) is not infix complete. To construct v we first pick, for every state q\in Q , a string v_{q}\in\Sigma^{*} such that \hat{\delta}(q,v_{q}) is an element of some closed reachability class (such a v_{q} must exist because Q is finite). We enumerate the states as Q=\{q_{0},\ldots,q_{r}\} and set v_{0}\coloneqq\varepsilon\quad\text{and}\quad v_{i+1}\coloneqq v_{i}v_{\hat{\delta}(q_{i},v_{i})}\text{ for }i=0,\ldots,r. Then v_{r+1} has the desired property: If the automaton starts in some state q_{i} , then v_{i} takes it to some state q=\hat{\delta}(q_{i},v_{i}) , and from there v_{\hat{\delta}(q_{i},v_{i})}=v_{q} takes it to some closed reachability class C . Since this can not be left, also \hat{\delta}(q_{i},v_{r+1})\in C . ∎∎ Corollary 4.3 . Given a DFA \mathcal{A} , it is decidable whether L(\mathcal{A}) is infix complete. In fact, for a regular language L the language \infix(L) is again regular, and one can easily compute a DFA for \infix(L) given a DFA for L . An \omega -word \xi\in\Sigma^{\omega} is called rich if for every v\in\Sigma^{*} there are x\in\Sigma^{*} and y\in\Sigma^{\omega} such that \xi=xvy [ Sta98 ] . Our main result on the density of regular \omega -languages now reads: Theorem 4.4 . Let L\subseteq\Sigma^{\omega} be a regular \omega -language. Then \mathbb{P}(L)>0 if and only if L contains a rich \omega -word. Moreover, given a suitable description of L it is decidable whether \mathbb{P}(L)>0 or not. Proof. Let L=\bigcup_{i}U_{i}V_{i}^{\omega} with regular U_{i},V_{i}\subseteq\Sigma^{*} . Obviously L contains a rich \omega -word if, and only if, one of the languages U_{i}V_{i}^{\omega} does, which is the case if, and only if, V_{i}^{\omega} contains such a word. On the other hand, \mathbb{P}(L)\leq\sum_{i=1}^{k}\mathbb{P}(U_{i}V_{i}^{\omega}), so \mathbb{P}(L)>0 if and only if \mathbb{P}(U_{i}V_{i}^{\omega})>0 for some i . Therefore without loss of generality we may assume that L=UV^{\omega} for regular U,V\subseteq\Sigma^{*} . V^{\omega} contains a rich \omega -word if and only if V^{*} is infix complete: Since \Sigma^{*} is countable, if V^{*} is infix complete we may take a word w_{v}=xvy\in V for each v\in\Sigma^{*} and concatenate these words to get a rich \omega -word in V^{\omega} . On the other hand, if \xi\in V^{\omega} is rich, then every w\in\Sigma^{*} is contained in some finite prefix of \xi , which in turn is a prefix of some word in V^{*} . We now show the following: If U,V\subseteq\Sigma^{*} are regular languages and V^{*} is infix complete there is a word x\in\Sigma^{*} such that \mathbb{P}\big(\zeta\in L\mathbin{|}x\preceq\zeta)=1\qquad\text{or, equivalently,}\qquad\mathbb{P}\big(\{\zeta\in\Sigma^{\omega}\mathbin{|}x\preceq\zeta\}\setminus L\big)=0 Since (V^{*})^{\omega}=V^{\omega} we may actually assume that V itself is infix complete. Pick a DFA \mathcal{A}=(Q,q_{0},\delta,A) with L(\mathcal{A})=V . By Lemma 4.2 there is a closed reachability class C\subseteq Q that contains an accepting state \tilde{q}\in C\cap A . Let w=a_{1}\cdots a_{\ell}\in\Sigma^{*} be any word such that \hat{\delta}(q_{0},w)\in C . We define a new automaton \mathcal{A}^{\prime}=(\Sigma,Q^{\prime},q_{0},\delta^{\prime},A) by Q^{\prime}\coloneqq Q\cup\{q^{\prime}_{1},\ldots,q^{\prime}_{\ell}\} and \begin{split}\delta^{\prime}(q,a)&=\delta(q,a)\text{ if }q\not\in\{\tilde{q},q^{\prime}_{1},\ldots,q^{\prime}_{\ell}\},\\ \delta^{\prime}(\tilde{q},a)&=\begin{cases}q_{1}&\text{if }a=a_{1}\\ \delta(\tilde{q},a)&\text{if }a\not=a_{1}\end{cases}\\ \delta^{\prime}(q^{\prime}_{i},a)&=\begin{cases}q^{\prime}_{i+1}&\text{if }a=a_{i+1}\text{ and }i<\ell\\ \hat{\delta}(\tilde{q},a_{1}\cdots a_{i}a)&\text{if }a\not=a_{i+1}\end{cases}\\ \delta^{\prime}(q^{\prime}_{\ell},a)&=\delta(\hat{\delta}(q_{0},w),a)\end{split} Then C\cup\{q^{\prime}_{1},\ldots,q^{\prime}_{\ell}\} is a closed reachability class in \mathcal{A}^{\prime} and if \zeta=z_{0}z_{1}\cdots\in\Sigma^{\omega} is an \omega -word such that w\preceq\zeta and \hat{\delta}^{\prime}(q_{0},z_{0}\cdots z_{k})=q^{\prime}_{\ell} for infinitely many k\geq 0 (i.e. when reading the \omega -word \zeta , the automaton \mathcal{A}^{\prime} passes through the state q^{\prime}_{\ell} infinitely often), then \zeta\in V^{\omega} . In fact, let k_{1}