# A Characterization of Multidimensional $S$-Automatic Sequences

Emilie Charlier^{[1]}; Tomi Kärki^{[1]}; Michel Rigo^{[1]}

- [1] Institute of Mathematics, University of Liège, Grande Traverse 12 (B 37), B-4000 Liège, Belgium

Actes des rencontres du CIRM (2009)

- Volume: 1, Issue: 1, page 23-28
- ISSN: 2105-0597

## Access Full Article

top## Abstract

top## How to cite

topCharlier, Emilie, Kärki, Tomi, and Rigo, Michel. "A Characterization of Multidimensional $S$-Automatic Sequences." Actes des rencontres du CIRM 1.1 (2009): 23-28. <http://eudml.org/doc/10007>.

@article{Charlier2009,

abstract = {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\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.},

affiliation = {Institute of Mathematics, University of Liège, Grande Traverse 12 (B 37), B-4000 Liège, Belgium; Institute of Mathematics, University of Liège, Grande Traverse 12 (B 37), B-4000 Liège, Belgium; Institute of Mathematics, University of Liège, Grande Traverse 12 (B 37), B-4000 Liège, Belgium},

author = {Charlier, Emilie, Kärki, Tomi, Rigo, Michel},

journal = {Actes des rencontres du CIRM},

keywords = {automatic sequence; abstract numeration system; morphic word; multidimensional word; shape-symmetry},

language = {eng},

month = {3},

number = {1},

pages = {23-28},

publisher = {CIRM},

title = {A Characterization of Multidimensional $S$-Automatic Sequences},

url = {http://eudml.org/doc/10007},

volume = {1},

year = {2009},

}

TY - JOUR

AU - Charlier, Emilie

AU - Kärki, Tomi

AU - Rigo, Michel

TI - A Characterization of Multidimensional $S$-Automatic Sequences

JO - Actes des rencontres du CIRM

DA - 2009/3//

PB - CIRM

VL - 1

IS - 1

SP - 23

EP - 28

AB - 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\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.

LA - eng

KW - automatic sequence; abstract numeration system; morphic word; multidimensional word; shape-symmetry

UR - http://eudml.org/doc/10007

ER -

## References

top- J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, (2003). Zbl1086.11015MR1997038
- 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. Zbl0804.11024MR1318968
- E. Charlier, T. Kärki, and M. Rigo, Multidimensional Generalized Automatic Sequences and Shape-Symmetric Morphic Words, submitted for publication. Zbl1231.05010
- A. Cobham, Uniform Tag Sequences, Math. Systems Theory6 (1972), 164–192. Zbl0253.02029MR457011
- P.B.A. Lecomte, M. Rigo, Numeration Systems on a Regular Language, Theory Comput. Syst.34 (2001), 27–44. Zbl0969.68095MR1799066
- 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).
- 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. Zbl0937.68078MR1719367
- A. Maes, Morphic Predicates and Applications to the Decidability of Arithmetic Theories, Ph.D. Thesis, Univ. Mons-Hainaut, (1999).
- S. Nicolay, M. Rigo, About the Frequency of Letters in Generalized Automatic Sequences, Theoret. Comp. Sci.374 (2007), 25–40. Zbl1162.68032MR2317465
- M. Rigo, Generalization of Automatic Sequences for Numeration Systems on a Regular Language, Theoret. Comp. Sci.244 (2000), 271–281. Zbl0945.68105MR1774400
- M. Rigo and A. Maes, More on Generalized Automatic Sequences, J. Autom., Lang. and Comb.7 (2002), 351–376. Zbl1033.68069MR1957696
- 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. Zbl0653.10049

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.