Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn normality in shifts of finite type
60
0
0.0
(
0
)
Added by
Olivier Carton
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we consider the notion of normality of sequences in shifts of finite type. A sequence is normal if the frequency of each block exists and is equal to the Parry measure of the block. We give a characterization of normality in terms of incompressibility by lossless transducers. The result was already known in the case of the full shift.
rate research
Read More
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.
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.
We reveal an algorithm for determining the complete prefix code irreducibility (CPC-irreducibility) of dyadic trees labeled by a finite alphabet. By introducing an extended directed graph representation of tree shift of finite type (TSFT), we show that the CPC-irreducibility of TSFTs is related to the connectivity of its graph representation, which is a similar result to one-dimensional shifts of finite type.
We provide a direct proof of Agafonovs theorem which states that finite state selection preserves normality. We also extends this result to the more general setting of shifts of finite type by defining selections which are compatible the shift. A slightly more general statement is obtained as we show that any Markov measure is preserved by finite state compatible selection.
We revisit the complexity of procedures on SFAs (such as intersection, emptiness, etc.) and analyze them according to the measures we find suitable for symbolic automata: the number of states, the maximal number of transitions exiting a state, and the size of the most complex transition predicate. We pay attention to the special forms of SFAs: {normalized SFAs} and {neat SFAs}, as well as to SFAs over a {monotonic} effective Boolean algebra.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
