pith. sign in

arxiv: 1904.09133 · v1 · pith:RPASMP4Onew · submitted 2019-04-19 · 💻 cs.FL

Preservation of normality by transducers

classification 💻 cs.FL
keywords infinitenormalitytransducersborelconsidergiveninput-deterministicwhen
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.