×

zbMATH — the first resource for mathematics

Suites automatiques à multi-indices. (Automatic sequences with multi- indices). Appendix by J. O. Shallit. (French) Zbl 0653.10049
Sémin. Théor. Nombres, Univ. Bordeaux I 1986-1987, Exp. No. 4, 27 p. (1987); Appendix 29A-36A (1987).
The author gives a generalization of the theorem of G. Christol, T. Kamae, M. Mendès France and G. Rauzy [Suites algébriques, automates et substitutions, Bull. Soc. Math. Fr. 108, 401- 419 (1980; Zbl 0472.10035)] to the multidimensional case: A formal power series with variables \(X_ 1,...,X_ r\) and coefficients in a finite field F of characteristic p is algebraic over \(F(X_ 1,...,X_ r)\) if and only if the sequence of coefficients is p-automatic. He first defines multidimensional automata (actually multidimensional uniform tag systems, then defines multidimensional substitutions (essentially matrix-valued substitutions). The theorem is then proved by using the same technique as used in the paper cited above [see also the reviewer’s paper, Expo. Math. 5, 239-266 (1987; Zbl 0641.10041)].
The author also gives examples of automatic and non-automatic sequences (including the “handkerchief-folding” sequence). Finally an appendix by J. Shallit shows how, using matrix-valued substitutions, one can generate Hadamard matrices or classical fractals (Sierpiński carpet, Menger sponge, Hilbert’s and Moore’s space filling curves...).
Reviewer: J.-P.Allouche

MSC:
11B99 Sequences and sets
68Q70 Algebraic theory of languages and automata
68Q80 Cellular automata (computational aspects)
11R04 Algebraic numbers; rings of algebraic integers