Cellular automata, matrix substitutions and fractals. (English) Zbl 0866.68069
Summary: It has been observed that the long time evolution of a cellular automata (CA) can generate fractal sets. In this paper, we define a broad class of CA, all of which have a limit set. Moreover, we present an algorithm which associates with a CA of the above defined class a substitution system which deciphers the self-similarity structure of the limit set.
Keywords:
cellular automataReferences:
| [1] | J.-P. Allouche, Finite automata in 1-D and 2-D physics, in:Number Theory of Physics, ed. J.-M. Lucu, P. Moussa and M. Waldschmidt. · Zbl 0713.11019 |
| [2] | T. Bedford, Dynamics and dimension for fractal recurrent sets, J. London Math. Soc. 33(1986) 89-100. · Zbl 0606.28004 · doi:10.1112/jlms/s2-33.1.89 |
| [3] | F.M. Dekking, Recurrent sets, Adv. Math. 44(1982)78-104. · Zbl 0495.51017 · doi:10.1016/0001-8708(82)90066-4 |
| [4] | F.M. Dekking, Substitutions, branching processes and fractal sets, in:Fractal Geometry and Analysis, ed. J. Belair and S. Dubuc (Kluwer, 1991). |
| [5] | F. v. Haeseler, H.-O, Peitgen and G. Skordev, Pascal’s triangle, dynamical systems, and attractors, Ergodic Theory and Dynamical Systems 12(1992)479-486. · Zbl 0784.58032 · doi:10.1017/S0143385700006908 |
| [6] | F. v. Haeseler, H.-O, Peitgen and G. Skordev, Linear cellular automata, substitutions, hierarchical iterated function systems and attractors, in:Fractal Geometry and Computer Graphics, ed. J.L. Encarnacao, H.-O. Peitgen, G. Sakas and G. Englert (Springer, Heidelberg, 1992). |
| [7] | F. v. Haeseler, H.-O. Peitgen and G. Skordev, On the fractal structure of limit sets of cellular automata and attractors of dynamical systems, submitted. · Zbl 1070.37006 |
| [8] | G. Hedlund, Endomorphisms and automorphisms of the shift dynamical systems, Math. Syst. Th. 3(1969)320-375. · Zbl 0182.56901 · doi:10.1007/BF01691062 |
| [9] | B. Mandelbrot,The Fractal Geometry of Nature (Freeman, New York, 1982). · Zbl 0504.28001 |
| [10] | B. Mandelbrot, Y. Gefen, A. Aharony and J. Peyriere, Fractals, their transfer matrices and their eigen-dimensional sequences, J. Phys. A: Math. Gen. 18(1985)335-354. · doi:10.1088/0305-4470/18/2/024 |
| [11] | M. Queffelec,Substitutional Dynamical Systems, Lecture Notes in Math. 1294 (Springer, 1987). |
| [12] | J. Shallit and J. Stolfi, Two methods for generating fractals, Comp. Graphics 13(1989)185-191. · doi:10.1016/0097-8493(89)90060-5 |
| [13] | S. Takahashi, Cellular automata and multifractals: dimension spectra of linear cellular automata, Physica D45(1990)36-48. · Zbl 0711.58019 |
| [14] | S. Takahashi, Self-similarity of linear cellular automata, J. Comp. Sci. 44(1992)114-140. · Zbl 0743.68105 · doi:10.1016/0022-0000(92)90007-6 |
| [15] | S. Willson, Cellular automata can generate fractals, Discr. Appl. Math. 8(1984)91-99. · Zbl 0533.68051 · doi:10.1016/0166-218X(84)90082-9 |
| [16] | S. Willson, The equality of fractional dimension for certain cellular automata, Physica D24(1987) 179-189. · Zbl 0634.68046 |
| [17] | S. Willson, Computing fractal dimensions for additive cellular automata, Physica D24(1987) 190-206. · Zbl 0634.68047 |
| [18] | S. Wolfram, Statistical mechanics and cellular automata, Rev. Mod. Phys. 55(1983)601-644. · Zbl 1174.82319 · doi:10.1103/RevModPhys.55.601 |
| [19] | S. Wolfram, Universality and complexity in cellular automata, Physica D10(1984)1-35. · Zbl 0562.68040 |
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.
