×

Additive cellular automata and algebraic series. (English) Zbl 0787.68074

A class of one-dimensional cellular automata in which the value of each cell depends in additive manner of its neighbours is studied. Generating series are used to describe the behavior of a cell in time and their basic properties are proved. Also it is shown that proper generating functions can be computed directly in the cases where the values of a cell are elements of a finite field or are complex numbers.
In the second part of the paper a number of examples is given relating additive cellular automata and some “automatic sequences” like paper folding sequences, or Catalan or Motzkin numbers.

MSC:

68Q80 Cellular automata (computational aspects)
11B85 Automata sequences
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J.-P., Automates finis en théorie des nombres, Exposition. Math., 5, 239-266 (1987) · Zbl 0641.10041
[2] Christol, G.; Kamae, T.; Mendès France, M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. Math. France, 108, 401-419 (1980) · Zbl 0472.10035
[3] Comtet, L., Calcul pratique des coefficients de Taylor d’une fonction algébrique, Enseign. Math., 10, 267-270 (1964) · Zbl 0166.41702
[4] Furstenberg, H., Algebraic functions over finite fields, J. Algebra, 7, 271-277 (1967) · Zbl 0175.03903
[5] Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), Wiley: Wiley New York · Zbl 0519.05001
[6] van der Poorten, A.; Dekking, M.; Mendès France, M., Folds!, Math. Intelligencer, 4, 190-195 (1982) · Zbl 0493.10003
[7] Martin, O.; Odlyzko, A. M.; Wolfram, S., Algebraic properties of cellular automata, Commun. Math. Phys., 93, 219-258 (1984) · Zbl 0564.68038
[8] (Boas, R. P.; Pólya, Georges, Collected Papers Volume I. Collected Papers Volume I, Singularities of Analytic Functions (1974), The MIT Press: The MIT Press Cambridge) · JFM 48.0368.02
[9] Wolfram, S., Theory and Applications of Cellular Automata, (Advanced Series on Complex Systems, Vol. 1 (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.