A characterization of multidimensional \(S\)-automatic sequences. (English) Zbl 1478.11036
Summary: An infinite word is \(S\)-automatic if, for all \(n \geq 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 \geq 2\), we state that a multidimensional infinite word \(x : \mathbb N^d \rightarrow \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.
References:
| [1] | J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, (2003). · Zbl 1086.11015 |
| [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. | · Zbl 0804.11024 |
| [3] | E. Charlier, T. Kärki, and M. Rigo, Multidimensional Generalized Automatic Sequences and Shape-Symmetric Morphic Words, submitted for publication. · Zbl 1231.05010 |
| [4] | A. Cobham, Uniform Tag Sequences, \(Math. Systems Theory\)6 (1972), 164-192. · Zbl 0253.02029 |
| [5] | P.B.A. Lecomte, M. Rigo, Numeration Systems on a Regular Language, \(Theory Comput. Syst.\)34 (2001), 27-44. · Zbl 0969.68095 |
| [6] | A. Maes, Decidability of the First-Order Theory of \(\langle \Bbb 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 0937.68078 |
| [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. · Zbl 1162.68032 |
| [10] | M. Rigo, Generalization of Automatic Sequences for Numeration Systems on a Regular Language, \(Theoret. Comp. Sci.\)244 (2000), 271-281. · Zbl 0945.68105 |
| [11] | M. Rigo and A. Maes, More on Generalized Automatic Sequences, \(J. Autom., Lang. and Comb.\)7 (2002), 351-376. · Zbl 1033.68069 |
| [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. | Copyright Cellule MathDoc 2018 · Zbl 0653.10049 |
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.
