×

Algebraic properties of cellular automata. (English) Zbl 0564.68038

Cellular automata are discrete dynamical systems, of simple construction but complex and varied behaviour. Algebraic techniques are used to give an extensive analysis of the global properties of a class of finite cellular automata. The complete structure of state transition diagrams is derived in terms of algebraic and number theoretical quantities. The systems are usually irreversible, and are found to evolve through transients to attractors consisting of cycles sometimes containing a large number of configurations.

MSC:

68Q80 Cellular automata (computational aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Wolfram, S.: Statistical mechanics of cellular automata. Rev. Mod. Phys.55, 601 (1983) · Zbl 1174.82319 · doi:10.1103/RevModPhys.55.601
[2] Golomb, S.W.: Shift register sequences. San Francisco: Holden-Day 1967 · Zbl 0267.94022
[3] Selmer, E.S.: Linear recurrence relations over finite fields. Dept. of Math., Univ. of Bergen, Norway (1966)
[4] Miller, J.C.P.: Periodic forests of stunted trees. Philos. Trans. R. Soc. Lond. A266, 63 (1970); A293, 48 (1980) · Zbl 0197.28701 · doi:10.1098/rsta.1970.0003
[5] ApSimon, H.G.: Periodic forests whose largest clearings are of size 3. Philos. Trans. R. Soc. Lond. A266, 113 (1970) · Zbl 0197.28801 · doi:10.1098/rsta.1970.0004
[6] ApSimon, H.G.: Periodic forests whose largest clearings are of sizen?4. Proc. R. Soc. Lond. A319, 399 (1970) · Zbl 0221.05023 · doi:10.1098/rspa.1970.0185
[7] Sutton, C.: Forests and numbers and thinking backwards. New Sci.90, 209 (1981)
[8] Moore, E.F.: Machine models of self-reproduction. Proc. Symp. Appl. Math.14, 17 (1962) reprinted in: Essays on cellular automata, A. W. Burks. Univ. of Illinois Press (1966) · Zbl 0126.32408
[9] Aggarwal, S.: Local and global Garden of Eden theorems. Michigan University technical rept. 147 (1973)
[10] Knuth, D.: Fundamental algorithms, Reading, MA: Addison-Wesley 1968. · Zbl 0191.17903
[11] Hardy, G.H., Wright, E.M.: An introduction to the theory of numbers. Oxford: Oxford University Press 1968 · Zbl 0020.29201
[12] Mac Williams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. Amsterdam: North-Holland 1977
[13] Griffiths, P., Harris, J.: Principles of algebraic geometry. New York: Wiley 1978 · Zbl 0408.14001
[14] Fredkin, E., Margolus, N.: Private communications
[15] Ronse, C.: Non-linear shift registers: A survey. MBLE Research Lab. report, Brussels (May 1980)
[16] Harao, M., Noguchi, S.: On some dynamical properties of finite cellular automaton. IEEE Trans. Comp. C-27, 42 (1978) · Zbl 0368.94054 · doi:10.1109/TC.1978.1674951
[17] Grassberger, P.: A new mechanism for deterministic diffusion. Phys. Rev. A (to be published) · Zbl 0562.68039
[18] Guibas, L.J., Odlyzko, A.M.: String overlaps, pattern matching, and nontransitive games. J. Comb. Theory (A)30, 83 (1981) · Zbl 0454.68109
[19] Knuth, D.: Seminumerical algorithms. 2nd ed. Reading, MA: Addison-Wesley 1981 · Zbl 0477.65002
[20] Gelfand, A.E.: On the cyclic behavior of random transformations on a finite set. Tech. rept. 305, Dept. of Statistics, Stanford Univ. (August 1981)
[21] Odlyzko, A.M.: Unpublished
[22] Lind, D.A.: Applications of ergodic theory and sofic systems to cellular automata. Physica D10 (to be published) · Zbl 0562.68038
[23] Wolfram, S.: Computation theory of cellular automata. Institute for Advanced Study preprint (January 1984)
[24] Lenstra, H.W., Jr.: Private communication
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.