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)
1
2

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.

Dates and versions

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

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More