Preservation of normality by transducers - Université Paris Cité Accéder directement au contenu
Article Dans Une Revue Information and Computation Année : 2022

Preservation of normality by transducers

Résumé

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.
Fichier principal
Vignette du fichier
1904.09133.pdf (162.91 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03660658 , version 1 (15-01-2024)

Identifiants

Citer

Olivier Carton, Elisa Orduna. Preservation of normality by transducers. Information and Computation, 2022, 282, pp.104650. ⟨10.1016/j.ic.2020.104650⟩. ⟨hal-03660658⟩
13 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More