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

https://hal-univ-paris.archives-ouvertes.fr/hal-03660658
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 : Tuesday, September 6, 2022 - 1:26:53 PM

Links full text

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

8