Preservation of normality by transducers (Q2064521)

This paper shows that it can be decided in cubic time with respect to the size of a complete and input-deterministic transducer whether it preserves normality. In this context, an alphabet is simply any finite set \(A\). An infinite word \(\alpha\) on a finite alphabet \(A\) is an infinite sequence \(\alpha\in A^\omega\), while a finite word \(w\in A^*\) is a finite sequence of elements of \(A\). For an infinite word \(\alpha\in A^\omega\) and a finite word \(w\in A^*\) the \emph{limiting frequency} \(\operatorname{freq}(\alpha,w)\) is furthermore defined as the limit, as \(n\) tends to infinity, of the proportion of positions smaller or equal to \(n\) where \(w\) occurs. An infinite word \(\alpha\) on a finite alphabet \(A\), \(\alpha\in A^\omega\), is \emph{normal} if \(\operatorname{freq}(\alpha,w)={1}/{\lvert A\rvert^{\lvert w\rvert}}\), for any finite words \(w\in A^*\), where \(\lvert w\rvert\) is the length of \(w\). Intuitively, all factors of the same length are equally present in \(\alpha\). A transducer \(\mathcal{T}\) is a computing machine model formed of a finite set \(Q\) of states, input \(A\) and output \(B\) alphabets, \(\delta \subseteq Q\times A\times B^*\times Q\) a finite transition relation and \(q_0\in Q\) an initial state. A \emph{run} of such a transducer is a finite or infinite sequence of transitions from \(\delta\) such that the first state of its first transition is the initial state \(q_0\) and for any other transition its first state is equal to the last of the previous transition. Such a run maps the concatenation of the elements of \(A\) appearing in it to the concatenation of the elements of \(B^*\) appearing in it. This is a pair of \(A^*\times B^*\). A transducer \(\mathcal{T}\) is furthermore \emph{input-deterministic} if any two transitions containing the same first state and input element from \(A\), also contain the same last state and output element of \(B^*\). A transducer \(\mathcal{T}\) is also complete if for any input symbol \(a\in A\) and state \(p\in Q\) there is a transition containing \(p\) as first state and \(a\) as input symbol. A complete and input-deterministic transducer hence maps any infinite input word \(\alpha\in A^\omega\) to a single word on \(B\), which could be finite, denoted by \(\mathcal{T}(\alpha)\). If for any normal word \(\alpha\), \(\mathcal{T}(\alpha)\) is normal when infinite, then the transducer \(\mathcal{T}\) is said to \emph{preserve normality}. The proof of the main theorem first reduces, using a result of \textit{C. P. Schnorr} and \textit{H. Stimm} [Acta Inf. 1, 345--359 (1972; Zbl 0238.68017)], to considering strongly connected components of \(\mathcal{T}\). An analysis of the frequencies of finite within infinite runs is then done using the stationary distribution of a Markov chain associated to the automaton. The proof then proceeds by considering weighted automata, where transitions are weighted by rational numbers, showing that \(\operatorname{freq}(\mathcal{T}(x),w)\) is equal to the weight of \(w\). Finally, the authors show that this weighted automaton can be computed in cubic time with respect to the size of the transducer \(\mathcal{T}\).