Preservation of normality by transducers - Archive ouverte HAL Access content directly
Journal Articles Information and Computation Year : 2022

Preservation of normality by transducers

(1) , (2)


We consider input deterministic finite state transducers with infinite inputs and infinite outputs, and we consider the property of Borel normality on infinite words. When these transducers are given by a strongly connected set of states, and when the input is a Borel normal sequence, the output is an infinite word such that every word has a frequency given by a weighted automaton over the rationals. We prove that there is an algorithm that decides in cubic time whether an input deterministic transducer preserves normality.

Dates and versions

hal-03660658 , version 1 (06-05-2022)



Olivier Carton, Elisa Orduna. Preservation of normality by transducers. Information and Computation, 2022, 282, pp.104650. ⟨10.1016/j.ic.2020.104650⟩. ⟨hal-03660658⟩
8 View
0 Download



Gmail Facebook Twitter LinkedIn More