HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Preservation of normality by transducers

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Contributor : Equipe Hal Université Paris Cité Connect in order to contact the contributor
Submitted on : Friday, May 6, 2022 - 10:12:47 AM
Last modification on : Sunday, May 8, 2022 - 3:10:03 AM

Links full text




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



Record views