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

Abstract

top
An infinite word is S -automatic if, for all n ≥ 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 ≥ 2 , we state that a multidimensional infinite word x : ℕ d → Σ 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.

How to cite

top

Charlier, 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
  1. J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, (2003). Zbl1086.11015MR1997038
  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. Zbl0804.11024MR1318968
  3. E. Charlier, T. Kärki, and M. Rigo, Multidimensional Generalized Automatic Sequences and Shape-Symmetric Morphic Words, submitted for publication. Zbl1231.05010
  4. A. Cobham, Uniform Tag Sequences, Math. Systems Theory6 (1972), 164–192. Zbl0253.02029MR457011
  5. P.B.A. Lecomte, M. Rigo, Numeration Systems on a Regular Language, Theory Comput. Syst.34 (2001), 27–44. Zbl0969.68095MR1799066
  6. A. Maes, Decidability of the First-Order Theory of 〈 ℕ ; &lt; , 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 , &lt; , P 〉 with Morphic Predicate P , J. Autom. Lang. Comb.4 (1999), 229–245. Zbl0937.68078MR1719367
  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. Zbl1162.68032MR2317465
  10. M. Rigo, Generalization of Automatic Sequences for Numeration Systems on a Regular Language, Theoret. Comp. Sci.244 (2000), 271–281. Zbl0945.68105MR1774400
  11. M. Rigo and A. Maes, More on Generalized Automatic Sequences, J. Autom., Lang. and Comb.7 (2002), 351–376. Zbl1033.68069MR1957696
  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. Zbl0653.10049

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.