Local structure theory for cellular automata

CA evolution finitely-parameterized models fixed points invariant measures iterative structures local structure operator local structure theory n-block measures nearest neighbor cellular automata tessellation automata uncorrelated initial distributions

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Other natural sciences (mathematical treatment) (92F05)

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).

Recommendations

Cites work

Cited in

(47)

This page was built for publication: Local structure theory for cellular automata

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