# Branching Densities of Cube-Free and Square-Free Words
## 4 Positions Fixed by Small Cubes
### Regular Approximations and Alo-Corasick Automata
: In \(\mathcal{A}_{i}\), consider the walk \(W\) from \(\lambda\) to \(\lambda.w\) labelled by \(w\). By Lemma 4, the number of fixed positions we need to estimate equals the number of occurrences of fixed states in \(W\), excluding the terminal occurrence of \(\lambda.w\). Note that \(W\), as well as any walk in \(\mathcal{A}_{i}\), can be obtained as follows: take a simple path between the initial and the terminal states of the walk and insert repeatedly simple cycles into the walk built so far. The simple path (say, of length \(n\)) contains, at most, \(d_{i}n+c_{i}\) fixed states, and the rest contains, at most, \(d_{i}(|w|-n)\) fixed states, whence the result. Corollary 1: _In an infinite cube-free word, the density of the set of letters fixed by cubes with periods of at most \(i\) is upper-bounded by \(d_{i}\)._  
The numbers \(d_{i}\) and \(c_{i}\) can be computed from \(\mathcal{A}_{i}\) in polynomial time using dynamic programming (due to Corollary 1, we need only \(d_{i}\)). A straightforward way to do this is to compute for each \(u,v\) in the order of increasing \(k\) the maximum fraction \(d[u,v,k]\) of fixed states in a \((u,v)\)-walk of length at most \(k\); then \(d_{i}=\max_{u}d[u,u,N_{i}]\), where \(\mathcal{A}_{i}\) has \(N_{i}\) states. This algorithm has cubic complexity, but we can do significantly better. We note that any automaton \(\mathcal{A}_{i}\) has a unique nontrivial strongly connected component; this quite nontrivial fact follows from the main result of [29]. Proposition 1: _Let \(N_{i}\) and \(n_{i}\) be the numbers of nodes in \(\mathcal{A}_{i}\) and its nontrivial strongly connected component, respectively. Then there exists an algorithm computing \(d_{i}\) from \(\mathcal{A}_{i}\) in time \(O(n_{i}^{2}+N_{i})\)._  
Proof. : Recall that the _mean cost_ of a walk in a weighted digraph is the ratio between its cost and its length. We reduce the problem of computing \(d_{i}\) to the problem of finding a cycle of the minimum mean cost. Considering \(\mathcal{A}_{i}\) as a digraph, we assign cost \(0\) to fixed edges and cost \(1\) to free edges. Then we replace \(\mathcal{A}_{i}\) with its unique nontrivial strongly connected component \(\mathcal{A}_{i}^{\prime}\) preserving the edge costs. This component contains all cycles of \(\mathcal{A}_{i}\). Now \(d_{i}=1-\mu\), where \(\mu\) is the minimum mean cost of a cycle in the weighted digraph \(\mathcal{A}_{i}^{\prime}\). The mean cost problem can be solved for an arbitrary strongly connected digraph with \(n\) nodes and \(m\) edges in \(O(nm)\) time and space using [PERSON]'s algorithm [30]. Noting that, in our case, \(m=O(n)\), and that the strongly connected component can be found in linear time by a textbook algorithm, we obtain the required time bound. For the sake of completeness, let us describe [PERSON]'s algorithm for our case. Fix an arbitrary state \(q\) and define \(C(j,v)\) to be the minimum cost of a length-\(j\) walk from \(q\) to \(v\) or \(\infty\) if no such walk exists. The \((n_{i}+1)\times n_{i}\) table with the values of \(C(j,v)\) for \(j=0,\ldots,n_{i}\) and all states of \(\mathcal{A}_{i}^{\prime}\) is filled using the following dynamic programming rule:  
\[C(j+1,v) =\min_{zz\preceq z_{p}}(C(j,z)+cost(z,v)), \tag{7}\] \[C(0,v) = \begin{cases}0,&\text{if $v=q$,}\\ \infty,&\text{otherwise.}\end{cases}  \tag{8}\]  
According to [30] (Theorem 1), \(\mu=\min_{v\in\mathcal{A}_{i}^{\prime}}\max_{0\leq j<n_{i}}\Big{(}\frac{C(n_ {i}v)-C(j,v)}{n_{i}-j}\Big{)}\). Remark 3: _[PERSON]'s algorithm also allows one to retrieve a cycle of minimum mean cost. To do this, one stores the node \(z=P(j,v)\), which gives the minimum in the computation (7) of \(C(j,v)\) (here, \(j=1,\ldots,n_{i}\), and \(P(j,v)\) is undefined if \(C(j,v)=\infty\)). The \(n_{i}\times n_{i}\) table \(P(j,v)\) is then used as follows.