Construction of local structure maps for cellular automata

MaRDI QIDQ5396371zbMATH OpenFDO

Authors Henryk Fukś

Publication date 5 February 2014

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

zbMATH Keywords

cellular automatalocal structure theoryprobability measures

Mathematics Subject Classification ID

Dynamical systems and their relations with probability theory and stochastic processes (37A50) Dynamical aspects of cellular automata (37B15)

Abstract: The paper formalizes and extends the idea of local structure approximation for cellular automata originally proposed by Gutowitz et. al. We start with a review of the construction of a probability measure on the set of bi-infinite strings over a finite alphabet of $N$ symbols. We then demonstrate that for a shift-invariant probability measure, probabilities of all blocks of length up to $k$ can be expressed by $(N-1)N^{k-1}$ linearly independent block probabilities. Two choices of these independent blocks are discussed in detail, one in which we choose the longest possible blocks ("long form") and one in which we choose the shortest possible blocks ("short form"). We then proceed to review the method which allows to approximate probabilities of blocks longer than $k$ by blocks of length $k$ or less. This approximation, known as Bayesian extension or Markov measure, is then used to construct approximate orbits of shift-invariant probability measures under the action of probabilistic or deterministic cellular automaton. We show that the aforementioned approximate orbit is completely determined by an $(N-1)N^{k-1}$-dimensional map. When the short form of block probabilities is used, this map takes particularly simple form, often revealing important features of a particular cellular automaton.

Recommendations

• Minimal entropy approximation for cellular automata
• Local structure theory for cellular automata
• Evaluating the quality of local structure approximation using elementary rule 14
• On the prediction of local patterns in cellular automata
• Limit sets of cellular automata associated to probability measures

Cited in

(9)

• On the prediction of local patterns in cellular automata
• Local structure theory for cellular automata
• Evaluating the quality of local structure approximation using elementary rule 14
• Local structure approximation as a predictor of second-order phase transitions in asynchronous cellular automata
• Minimal entropy approximation for cellular automata
• An example of computation of the density of ones in probabilistic cellular automata by direct recursion
• CORRESPONDENCE BETWEEN LOCAL MAPS AND GLOBAL MAPS IN CELLULAR AUTOMATA
• Block approximations for probabilistic mixtures of elementary cellular automata
• Solving the initial value problem for cellular automata by pattern decomposition

This page was built for publication: Construction of local structure maps for cellular automata

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