Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Journal of Computer ...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Journal of Computer and System Sciences
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
CONICET Digital
Article . 2015
License: CC BY NC ND
Data sources: CONICET Digital
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Journal of Computer and System Sciences
Article . 2015 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2015
Data sources: zbMATH Open
DBLP
Article . 2015
Data sources: DBLP
versions View all 6 versions
addClaim

Normality and automata

Authors: Verónica Becher; Olivier Carton; Pablo Ariel Heiber;

Normality and automata

Abstract

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 certain positions in it and disregarding others. In selection via prefix a regular language \(L\) essentially determines whether a position is taken or not. More precisely, the position \(i\) is selected if and only if the prefix of \(w\) up to but not including \(i\) is in \(L\). Suffix selection works similarly given a regular language of infinite words. It is shown that both selection via prefix and selection via suffix preserve the normality of the word, whereas both-sided selection does not. The paper is well written and very self-contained. All major constructions are first presented in a nice overview before the technical details are shown. A background in automata theory, more specifically, regular languages and finite-state transducers, is required to understand the contribution but that basic knowledge can be obtained from any undergraduate course or textbook.

Country
Argentina
Keywords

nondeterminism, pushdown transducer, Finite Automata, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Formal languages and automata, finite-state transducer, regular language, counter transducer, normal word, https://purl.org/becyt/ford/1.2, Non-Deterministic Automata, https://purl.org/becyt/ford/1, Normal Numbers

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    12
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
12
Top 10%
Top 10%
Top 10%
Green
hybrid