Normality and automata
type: Item
instance of: scholarly article
title: Normality and automata
zbMATH Open document ID: 1329.68156
author: Verónica Becher
author: Olivier Carton
author: Pablo Ariel Heiber
published in: Journal of Computer and System Sciences
publication date: 2015-08-31T00:00:00Z
review text: The contribution discusses the compressibility of normal words by various finite-state devices. Roughly speaking, a normal word is an infinite word such that each given block of \(n\) letters occurs (in the limit) as often as each other block of \(n\) letters. This notion of normality is based on the classical notion for numbers established by Émile Borel. Compressibility is defined via a finite-state transducer (with potentially other facilities such as stacks or counters) that receives the input and transforms it into a string containing essentially the same information (bounded-to-one) in ultimately fewer symbols for the prefixes (adjusted for alphabet size). It is demonstrated that neither deterministic nor nondeterministic finite-state transducers can compress normal words. This result also does not depend on the real-time property (i.e., whether \(\varepsilon\)-transitions are permitted or not). Similarly, adding a single counter does not improve the situation and normal words are still not compressible. Since two counters are Turing-complete if \(\varepsilon\)-transitions are permitted, the first compressibility results is obtained. However, even with several counters real-time transducers cannot compress normal words, so the boundary here is clearly the ability to produce output without consuming input. With a single stack and a counter the device becomes powerful enough to compress normal words, whereas it is unclear whether this is also the case for deterministic pushdown transducers (i.e., those with just a single stack). Nondeterministic pushdown transducers and non-real-time transducers again are powerful enough to yield compressions of normal words so that the boundary could either be the presence of the stack or a stack together with some form of nondeterminism. In addition, the authors investigate selection from normal words by means of either prefixes, suffixes, or both. Selection constructs a new word from the given infinite word \(w\) by selecting…
reviewed by: Andreas Maletti
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 6476949
zbMATH Keywords: normal word
zbMATH Keywords: finite-state transducer
zbMATH Keywords: regular language
zbMATH Keywords: nondeterminism
zbMATH Keywords: pushdown transducer
zbMATH Keywords: counter transducer
Wikidata QID: Q61927005
MaRDI profile type: Publication
full work available at URL: j.jcss.2015.04.007
OpenAlex ID: W612499105
cites work: Q5653940
cites work: Determinization of transducers over infinite words: The general case
cites work: Normal numbers and finite automata
cites work: Q4037000
cites work: Distribution modulo one and Diophantine approximation
cites work: Normality and two-way automata
cites work: Unambiguous Büchi automata.
cites work: Finite-state dimension
cites work: Q4767350
cites work: Selection functions that do not preserve normality
cites work: Recursive unsolvability of Post's problem of ''Tag'' und other topics in theory of Turing machines
cites work: An unpredictability approach to finite-state randomness
cites work: Q5317419
cites work: Q3644388
cites work: Endliche Automaten und Zufallsfolgen
DBLP publication ID: journals/jcss/BecherCH15
DOI: 10.1016/J.JCSS.2015.04.007
description: scientific article; zbMATH DE number 6476949