Linear cellular automata, finite automata and Pascal’s triangle. (English) Zbl 0854.68065
Summary: We address the question whether double sequences produced by one-dimensional linear cellular automata can also be generated by finite automata. A complete solution for binomial coefficients and Lucas’ numbers is given and some partial results for the general case are presented.
Online Encyclopedia of Integer Sequences:
Sierpiński’s [Sierpinski’s] triangle (or gasket): triangle, read by rows, formed by reading Pascal’s triangle (A007318) mod 2.Triangle, read by rows, formed by reading Pascal’s triangle (A007318) mod 3.
Common residues of binomial(3n,n)/(2n+1) modulo 2: relates ternary trees (A001764) to the infinite Fibonacci word (A003849).
References:
| [1] | Allouche, J.-P, Automates finis en théorie des nombres, Expo. Math., 5, 239-266 (1986) · Zbl 0641.10041 |
| [2] | Allouche, J.-P, Finite automata in 1-dimensional and 2-dimensional physics, (Luck, J.-M; Moussa, P.; Waldschmidt, M., Number Theory and Physics. Number Theory and Physics, Proceedings in Physics, Vol. 47 (1990), Springer: Springer Berlin), 177-184 · Zbl 0713.11019 |
| [3] | Allouche, J.-P; Shallit, J., The ring of \(k\)-regular sequences, Theoret. Comput. Sci., 98, 163-197 (1992) · Zbl 0774.68072 |
| [4] | Berstel, J.; Morcrette, M., Compact representation of patterns by finite automata, (Proc. Pixim ’89. Proc. Pixim ’89, Hermes (1989)), 387-402 |
| [5] | Berstel, J.; Abdallah, A. Nait, Tétrarbres engendrés par des automates finis, (Publications du LITP 89-7 (1989) and: Bigre + Globule 61-62 (1989)), 167-175 |
| [6] | Bondarenko, B., Generalized Triangles and Pyramids of Pascal, Their Fractals, Graphs and Applications (1990), Fan: Fan Tashkent, (in Russian) · Zbl 0706.05002 |
| [7] | Christol, G.; Kamae, T.; France, M. Mendès; Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. Math. France, 108, 401-419 (1980) · Zbl 0472.10035 |
| [8] | Cobham, A., On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory, 3, 186-192 (1969) · Zbl 0179.02501 |
| [9] | Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029 |
| [10] | Culik, K.; Dube, S., Fractal and recurrent behavior of cellular automata, Complex Systems, 3, 253-267 (1989) · Zbl 0732.68079 |
| [11] | Denef, J.; Lipschitz, L., Algebraic power series and diagonals, J. Number Theory, 26, 46-67 (1987) · Zbl 0609.12020 |
| [12] | Eilenberg, S., (Automata, Languages and Machines, Vol. A (1985), Academic Press: Academic Press New York) |
| [13] | Furstenberg, H., Algebraic functions over finite fields, J. Algebra, 7, 271-277 (1967) · Zbl 0175.03903 |
| [14] | von Haeseler, F.; Peitgen, H.-O; Skordev, G., Pascal’s triangle, dynamical systems and attractors, Ergodic Theory Dynamical Systems, 12, 479-486 (1992) · Zbl 0784.58032 |
| [15] | von Haeseler, F.; Peitgen, H.-O; Skordev, G., Linear cellular automata, substitutions, hierarchical iterated systems, (Encarnasao, J. L.; etal., Fractal Geometry and Computer Graphics (1992), Springer: Springer Berlin) · Zbl 1090.37504 |
| [16] | von Haeseler, F.; Peitgen, H.-O; Skordev, G., On the fractal structure of rescaled evolution sets of cellular automata and attractors of dynamical systems, (Report 278 (1992), Inst. Dyn. Syst., University of Bremen) · Zbl 1090.37504 |
| [17] | von Haeseler, F.; Peitgen, H.-O; Skordev, G., Cellular automata, matrix substitutions and fractals, Ann. Math. Art. Intel., 8, 345-362 (1993) · Zbl 0866.68069 |
| [18] | Holte, J., The dimension of the set of multinomial coefficients not divisible by \(n\), (AMS Annual Meeting (1991)) |
| [19] | Kummer, E., Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math., 44, 93-146 (1852) · ERAM 044.1198cj |
| [20] | Litow, B.; Dumas, P., Additive cellular automata and algebraic series, Theoret. Comput. Sci., 119, 345-354 (1993) · Zbl 0787.68074 |
| [21] | Lucas, E., Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques, Bull. Soc. Math. France, 6, 49-54 (1878) · JFM 10.0139.04 |
| [22] | Peitgen, H.-O; Jürgens, H.; Saupe, D., Chaos and Fractals (1992), Springer: Springer Berlin · Zbl 0779.58004 |
| [23] | Robinson, A. D., Fast computation of additive cellular automata, Complex Systems, 1, 211-216 (1987) · Zbl 0655.68064 |
| [24] | Salon, O., Suites automatiques à multi-indices et algébraicité, C.R. Acad. Sci. Paris, 305, 501-504 (1987), (Sér. I) · Zbl 0628.10007 |
| [25] | Salon, O., Suites automatiques à multi-indices, Séminaire de Théorie des Nombres de Bordeaux, Exposé, 4, 4.01-4.27 (1986-1987), followed by an appendix by J. Shallit, 4-29A-4-36A · Zbl 0653.10049 |
| [26] | Shallit, J.; Stolfi, J., Two methods for generating fractals, Comput. Graphics, 13, 185-191 (1989) |
| [27] | Stanley, R., Enumerative Combinatorics, I (1986), Wadsworth and Brooks/Cole, Advanced Books and Software: Wadsworth and Brooks/Cole, Advanced Books and Software Monterey, CA · Zbl 0608.05001 |
| [28] | Sved, M.; Pitman, J., Divisibility of binomials by prime powers, a geometrical approach, Ars Combin., 26, 197-222 (1988) · Zbl 0673.10011 |
| [29] | Takahashi, S., Self-similarity of linear cellular automata, J. Comput. Sci., 44, 14-140 (1992) · Zbl 0743.68105 |
| [30] | Wilf, H. S., An aperiodic sequence, Problem E 3457, solution by J.R. Griggs, Amer. Math. Monthly, 100, 502-503 (1993) |
| [31] | Willson, S., Cellular automata can generate fractals, Discrete Appl. Math., 8, 91-99 (1984) · Zbl 0533.68051 |
| [32] | Willson, S., A use of cellular automata to obtain families of fractals, (Barnsley, M.; Demko, S., Chaotic Dynamics and Fractals (1986), Academic Press: Academic Press New York) · Zbl 0615.68042 |
| [33] | Willson, S., Calculating growth rates and moments for additive cellular automata, Discrete Appl. Math., 35, 47-65 (1992) · Zbl 0738.68060 |
| [34] | Wolfram, S., Theory and Application of Cellular Automata (1986), World Scientific: World Scientific Singapore |
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.
