A Characterization of Multidimensional $S$-Automatic Sequences

Charlier, Emilie; Kärki, Tomi; Rigo, Michel

Actes des rencontres du CIRM, Tome 1 (2009) no. 1, pp. 23-28.

An infinite word is $S$-automatic if, for all $n\ge 0$, its $(n+1)$st letter is the output of a deterministic automaton fed with the representation of $n$ in the considered numeration system $S$. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for $d\ge 2$, we state that a multidimensional infinite word $x:{\mathbb{N}}^d\to \Sigma$ over a finite alphabet $\Sigma$ is $S$-automatic for some abstract numeration system $S$ built on a regular language containing the empty word if and only if $x$ is the image by a coding of a shape-symmetric infinite word.

[1] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, (2003). | DOI | Zbl

[2] V. Bruyère, G. Hansel, C. Michaux, and R. Villemaire, Logic and $p$-recognizable sets of integers, Bull. Belg. Math. Soc. 1 (1994), 191–238. | DOI | MR | Zbl

[3] E. Charlier, T. Kärki, and M. Rigo, Multidimensional Generalized Automatic Sequences and Shape-Symmetric Morphic Words, submitted for publication. | DOI | MR | Zbl

[4] A. Cobham, Uniform Tag Sequences, Math. Systems Theory 6 (1972), 164–192. | DOI | MR | Zbl

[5] P.B.A. Lecomte, M. Rigo, Numeration Systems on a Regular Language, Theory Comput. Syst. 34 (2001), 27–44. | DOI | MR | Zbl

[6] A. Maes, Decidability of the First-Order Theory of $\langle \mathbb{N};<,P\rangle$ for Morphic Predicates $P$, Preprint 9806, Inst. für Informatik und Praktische Math., Christian-Albrechts-Univ. Kiel (1998).

[7] A. Maes, An Automata-Theoretic Decidability Proof for First-Order Theory of $\langle \mathbf{N},<,P\rangle$ with Morphic Predicate $P$, J. Autom. Lang. Comb. 4 (1999), 229–245. | Zbl

[8] A. Maes, Morphic Predicates and Applications to the Decidability of Arithmetic Theories, Ph.D. Thesis, Univ. Mons-Hainaut, (1999).

[9] S. Nicolay, M. Rigo, About the Frequency of Letters in Generalized Automatic Sequences, Theoret. Comp. Sci. 374 (2007), 25–40. | DOI | MR | Zbl

[10] M. Rigo, Generalization of Automatic Sequences for Numeration Systems on a Regular Language, Theoret. Comp. Sci. 244 (2000), 271–281. | DOI | MR | Zbl

[11] M. Rigo and A. Maes, More on Generalized Automatic Sequences, J. Autom., Lang. and Comb. 7 (2002), 351–376. | Zbl

[12] O. Salon, Suites automatiques à multi-indices, Séminaire de théorie des nombres de Bordeaux, Exp. 4 (1986-1987), 4.01–4.27; followed by an Appendix by J. Shallit, 4-29A–4-36A. | Zbl