Preservation of normality by unambiguous transducers

DOI10.1007/978-3-031-05578-2_7MaRDI QIDQ2163983zbMATH OpenOpenAlexFDO

Authors Olivier Carton

Publication date 11 August 2022

Full work available at URL https://arxiv.org/abs/2006.00891

zbMATH Keywords

functional transducersnormal sequencesweighted automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We consider finite state non-deterministic but unambiguous transducers with infinite inputs and infinite outputs, and we consider the property of Borel normality of sequences of symbols. When these transducers are strongly connected, and when the input is a Borel normal sequence, the output is a sequence in which every block has a frequency given by a weighted automaton over the rationals. We provide an algorithm that decides in cubic time whether a unambiguous transducer preserves normality.

Recommendations

• Preservation of normality by transducers
• On normality in shifts of finite type
• Normality and automata
• Normal numbers and finite automata
• Normality and two-way automata

Cites work

• An Introduction to Symbolic Dynamics and Coding
• Computability and Randomness
• Distribution modulo one and Diophantine approximation
• Elements of automata theory. Translated from the French by Reuben Thomas
• scientific article; zbMATH DE number 1408334 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 3383900 (Why is no real title available?)
• Markov chains. Gibbs fields, Monte Carlo simulation and queues
• Normal numbers and computer science
• Preservation of normality by transducers

Cited in

(5)

• Preservation of normality by non-oblivious group selection
• Preservation of normality by transducers
• Normality and automata
• Deterministic pushdown automata can compress some normal sequences
• Opacity complexity of automatic sequences: the general case

This page was built for publication: Preservation of normality by unambiguous transducers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2163983)