Suites automatiques à multi-indices. (Automatic sequences with multi- indices). Appendix by J. O. Shallit. (French) Zbl 0653.10049

Salon, Olivier

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

Keywords:

algebraic functions; finite automata; formal power series; multidimensional automata; multidimensional uniform tag systems; multidimensional substitutions; matrix-valued substitutions; Hadamard matrices; fractals; Sierpiński carpet; Menger sponge; Hilbert’s and Moore’s space filling curves

Citations:

Zbl 0472.10035; Zbl 0641.10041