On normality in shifts of finite type

DOI10.1007/S00224-019-09953-9zbMATH Open1458.37016arXiv1807.07208OpenAlexW2992189211MaRDI QIDQ778523FDOQ778523

Authors: Olivier Carton, Nicolás Alvarez 

Publication date: 2 July 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

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.

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

Recommendations

• Normality and automata
• Normal numbers and finite automata
• Finite state incompressible infinite sequences
• Finite State Incompressible Infinite Sequences
• Automatic Kolmogorov complexity, normality, and finite-state dimension revisited

zbMATH Keywords

normalitycompressionfinite-state transducerfull shiftfinite type shift

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16) Dynamical aspects of cellular automata (37B15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Multidimensional shifts of finite type (37B51)

Cites Work

• Subshifts of finite type and sofic systems
• Title not available (Why is that?)
• An Introduction to Symbolic Dynamics and Coding
• Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
• Finite-state dimension
• Normal numbers and finite automata
• Non-negative matrices and Markov chains.
• Endliche Automaten und Zufallsfolgen
• Compression of individual sequences via variable-rate coding
• Markov Chains
• Normality and automata
• Title not available (Why is that?)
• Distribution modulo one and Diophantine approximation
• Title not available (Why is that?)
• Sofic systems and graphs
• Normality and two-way automata
• Normal numbers
• Normality in non-integer bases and polynomial time randomness
• On a paper of Niven and Zuckerman
• Normal numbers and symbolic dynamics

Cited In (5)

• Finite state incompressible infinite sequences
• Title not available (Why is that?)
• Normal numbers and finite automata
• Title not available (Why is that?)
• Preservation of normality by unambiguous transducers

This page was built for publication: On normality in shifts of finite type

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