On normality in shifts of finite type
type: Item
instance of: scholarly article
title: On normality in shifts of finite type
zbMATH Open document ID: 1458.37016
author: Olivier Carton
author: Nicolás Alvarez
published in: Theory of Computing Systems
publication date: 2020-07-02T00:00:00Z
full work available at URL: https://arxiv.org/abs/1807.07208
review text: The contribution discusses an extension of the characterization of normality of infinite sequences in full shifts via non-compressibility by one-to-one finite-state transducers. Roughly speaking a sequence is normal if all subsequences of any given fixed length occur and occur with the same frequency. One-to-one finite-state transducers compute bijective functions that can easily be represented by a finite-state machine with output. The compression rate is defined as usual as the limit of the ratios between the lengths of the images of the finite prefixes of the sequence and the length of the prefixes. A given sequence is incompressible if there exists no one-to-one finite-state transducer that achieves a compression rate strictly below 1 for that sequence. The authors generalize the above-mentioned result to shifts of finite type instead of just full shifts. While full shifts are essentially all the infinite sequences that can be formed given a finite alphabet, a shift of finite type is obtained by declaring a finite set of subsequences, of which each is forbidden to occur anywhere in the sequence. To this end, they first show that various definitions of normality (aligned, strongly aligned, non-aligned) yield the same notion. Next, it is demonstrated that a sequence is compressible in the shift of finite type if and only if it is compressible beyond its relative entropy in the full shift, which is then used to establish the already mentioned main characterization theorem relating normality to incompressibility. The contribution is well written and should be generally understandable to any graduate of computer science or mathematics. It relies on a number of existing results, but full references are provided. The writing is slightly dense, but can be appreciated fully with some effort.
reviewed by: Andreas Maletti
Mathematics Subject Classification ID: 37B15
Mathematics Subject Classification ID: 37B51
Mathematics Subject Classification ID: 11K16
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68P30
zbMATH DE Number: 7217005
zbMATH Keywords: normality
zbMATH Keywords: compression
zbMATH Keywords: full shift
zbMATH Keywords: finite type shift
zbMATH Keywords: finite-state transducer
MaRDI profile type: Publication
OpenAlex ID: W2992189211
arXiv ID: 1807.07208
cites work: Q5653940
cites work: Normality in non-integer bases and polynomial time randomness
cites work: Normality and automata
cites work: Normal numbers and finite automata
cites work: Normal numbers
cites work: Distribution modulo one and Diophantine approximation
cites work: Normality and two-way automata
cites work: On a paper of Niven and Zuckerman
cites work: Finite-state dimension
cites work: Sofic systems and graphs
cites work: Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
cites work: Compression of individual sequences via variable-rate coding
cites work: An Introduction to Symbolic Dynamics and Coding
cites work: Normal Numbers and Symbolic Dynamics
cites work: Markov Chains
cites work: Q5317419
cites work: Endliche Automaten und Zufallsfolgen
cites work: Non-negative matrices and Markov chains.
cites work: Q3931654
cites work: Subshifts of finite type and sofic systems
DOI: 10.1007/S00224-019-09953-9
description: scientific article