Local structure theory for cellular automata
type: Item
instance of: scholarly article
title: Local structure theory for cellular automata
zbMATH Open document ID: 0634.92022
DOI: 10.1016/0167-2789(87)90120-5
author: Howard A. Gutowitz
author: Bruce Knight
author: Jonathan D. Victor
published in: Physica D
publication date: 1987-01-01T00:00:00Z
review text: In the present paper the local structure theory (LST) for cellular automata (CA) is presented. The LST is a sequence of finitely- parameterized models of the statistical features of a cellular automaton's evolution. The n-th model in the sequence takes into account correlations in terms of the probability of blocks of n states. A class of measures, the n-block measures, is introduced. The local structure operator of order n maps n-block measures to n-block measures in a manner which reflects the CA map on blocks of states. The fixed points of the map on measures approximate the invariant measures of the CA. The ability of the LST to model evolution from uncorrelated initial distributions is studied. The theory gives exact results in simple cases. In more complex cases, Monte Carlo numerical experiments suggest that an accurate statistical portrait of CA evolution is obtained. The invariant measures of CA and the stability of these measures may be obtained from the LST. Nearest neighbour CA with two states per cell are studied using the method of the LST. To the results of the paper directly belong the results of the reviewer's paper, Izv. Akad. Nauk Ehst. SSR, Fiz. Mat. 20, 205-208 (1971; Zbl 0218.92002).
Mathematics Subject Classification ID: 92F05
Mathematics Subject Classification ID: 68Q80
zbMATH DE Number: 4033572
zbMATH Keywords: nearest neighbor cellular automata
zbMATH Keywords: iterative structures
zbMATH Keywords: tessellation automata
zbMATH Keywords: local structure theory
zbMATH Keywords: finitely-parameterized models
zbMATH Keywords: n-block measures
zbMATH Keywords: local structure operator
zbMATH Keywords: fixed points
zbMATH Keywords: invariant measures
zbMATH Keywords: uncorrelated initial distributions
zbMATH Keywords: CA evolution
MaRDI profile type: Publication
full work available at URL: 0167-2789(87)90120-5
OpenAlex ID: W1973204073
cites work: Q3944542
cites work: Q3268609
cites work: Ergodic theory on compact spaces
cites work: Ergodic theory of chaos and strange attractors
cites work: Comments on a simple cellular automaton in spin representation
cites work: Toward a quantitative theory of self-generated complexity
cites work: Q3802626
cites work: Q3234755
cites work: Endomorphisms and automorphisms of the shift dynamical system
cites work: Algebraic properties of cellular automata
cites work: Q5533878
cites work: On the prediction of local patterns in cellular automata
cites work: On the ergodic theory of cellular automata
cites work: Statistical mechanics of cellular automata
cites work: Random sequence generation by cellular automata
cites work: Q3750126
description: scientific article; zbMATH DE number 4033572