A Characterization of Multidimensional $S$-Automatic Sequences

Emilie Charlier; Tomi Kärki; Michel Rigo

doi:10.5802/acirm.5

A Characterization of Multidimensional

S

-Automatic Sequences

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

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

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

Abstract

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 : ℕ^{d} \to Σ$ over a finite alphabet $Σ$ 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.

Published online: 2010-08-30

Zbl: 06938553

DOI: 10.5802/acirm.5

Author's affiliations:

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

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

@article{ACIRM_2009__1_1_23_0,
     author = {Emilie Charlier and Tomi K\"arki and Michel Rigo},
     title = {A {Characterization} of {Multidimensional} $S${-Automatic} {Sequences}},
     journal = {Actes des rencontres du CIRM},
     pages = {23--28},
     publisher = {CIRM},
     volume = {1},
     number = {1},
     year = {2009},
     doi = {10.5802/acirm.5},
     zbl = {06938553},
     language = {en},
     url = {https://acirm.centre-mersenne.org/articles/10.5802/acirm.5/}
}

TY  - JOUR
AU  - Emilie Charlier
AU  - Tomi Kärki
AU  - Michel Rigo
TI  - A Characterization of Multidimensional $S$-Automatic Sequences
JO  - Actes des rencontres du CIRM
PY  - 2009
SP  - 23
EP  - 28
VL  - 1
IS  - 1
PB  - CIRM
UR  - https://acirm.centre-mersenne.org/articles/10.5802/acirm.5/
DO  - 10.5802/acirm.5
LA  - en
ID  - ACIRM_2009__1_1_23_0
ER  -

%0 Journal Article
%A Emilie Charlier
%A Tomi Kärki
%A Michel Rigo
%T A Characterization of Multidimensional $S$-Automatic Sequences
%J Actes des rencontres du CIRM
%D 2009
%P 23-28
%V 1
%N 1
%I CIRM
%U https://acirm.centre-mersenne.org/articles/10.5802/acirm.5/
%R 10.5802/acirm.5
%G en
%F ACIRM_2009__1_1_23_0

Emilie Charlier; Tomi Kärki; Michel Rigo. A Characterization of Multidimensional $S$-Automatic Sequences. Actes des rencontres du CIRM, Volume 1 (2009) no. 1, pp. 23-28. doi : 10.5802/acirm.5. https://acirm.centre-mersenne.org/articles/10.5802/acirm.5/

References
Cited by

[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 $〈 ℕ; <, P 〉$ 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 $〈 N, <, P 〉$ 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

Cited by Sources: