Special Issue: 9th International Conference on Developments in Language Theory (DLT'05)No Access

MULTIDIMENSIONAL STURMIAN SEQUENCES AND GENERALIZED SUBSTITUTIONS

FERNIQUE THOMAS

LIRMM, CNRS-UMR 5506 and Université Montpellier II, 161 rue Ada 34392 Montpellier Cedex 5, France

https://doi.org/10.1142/S0129054106004005Cited by:18 (Source: Crossref)

Abstract

This paper is devoted to a study on the way generalized substitutions - a multi-dimensional extension of substitutions - act on multi-dimensional Sturmian sequences. We give a sufficient condition under which these multi-dimensional Sturmian sequences are obtained by iterated compositions of generalized substitutions. This condition relies on Brun expansions - a multi-dimensional extension of continued fraction expansions.

Keywords:

References

P. Alessandri, "Codages de rotations et basses complexités," Ph. D thesis, Université Aix-Marseille II, 1996 . Google Scholar
I. M. Araújo and V. Bruyère, Sturmian words: dynamical systems and derivated words, Proc. DLT'05, Lect. Notes Comput. Sci. 3572 (2005) pp. 122–133. Google Scholar
P. Arnoux, V. Berthé and S. Ito, Ann. Inst. Fourier (Grenoble) 52, 1001 (2002). Google Scholar
P. Arnoux, V. Berthé, T. Fernique and D. Jamet, "Functional Stepped Surfaces, Flips and Generalized Substitutions," LIRMM research report 06014 (2006) . Google Scholar
P. Arnoux, V. Berthé and A. Siegel, Theoret. Comput. Sci. 319(1–3), 145 (2004), DOI: 10.1016/j.tcs.2004.02.017. Crossref, Web of Science, Google Scholar
P. Arnoux and S. Ito, Bull. Belg. Math. Soc. Simon Stevin 8(2), 181 (2001). Web of Science, Google Scholar
P. Arnoux and G. Rauzy, Bull. Soc. math. France 119, 199 (1991). Crossref, Web of Science, Google Scholar
P. Balázhi, Z. Masákovova and E. Pelantová, Integers 5, (2005). Google Scholar
J. Berstel and P. Séébold, A Characterization of Sturmian Morphisms, Proc. MFCS (1993) pp. 281–290. Google Scholar
V. Berthé, C. Holton, L. Q. Zamboni, "Initial powers of Sturmian sequences," Acta Arithmetica, to appear . Google Scholar
V. Berthé and L. Vuillon, Discrete Math. 223, 27 (2000), DOI: 10.1016/S0012-365X(00)00039-X. Crossref, Web of Science, Google Scholar
V. Berthé and L. Vuillon, J. Théor. Nombres Bordeaux 12, 179 (2000). Crossref, Google Scholar
A. J. Brentjes , Mathematical Centre Tracts 145 ( Matematisch Centrum , Amsterdam , 1981 ) . Google Scholar
V. Canterini and A. Siegel, Trans. Amer. Math. Soc. 353, 5121 (2001), DOI: 10.1090/S0002-9947-01-02797-0. Crossref, Web of Science, Google Scholar
J. Cassaigne, J. Autom. Lang. Comb. 4, 153 (1999). Web of Science, Google Scholar
J. Cassaigne, "Subword complexity and periodicity in two or more dimensions," World Scientific (2000), pp. 14–21 . Google Scholar
E. M. Coven and G. A. Hedlund, Math. Sys. Th. 7, 138 (1973). Crossref, Google Scholar
D. Crispet al., J. Théor. Nombres Bordeaux 5, 123 (1993). Crossref, Google Scholar
F. Durand, Inventiones Math. 132, 179 (1998). Web of Science, Google Scholar
F. Durand, Ergod. Th. and Dyn. Sys. 20, 1061 (2000), DOI: 10.1017/S0143385700000584. Crossref, Web of Science, Google Scholar
S. Ferenczi, Ergod. Th. and Dyn. Sys. 16, 663 (1996). Crossref, Web of Science, Google Scholar
T. Fernique, Bidimensional Sturmian Sequences and Substitutions, Proc. DLT'05, Lect. Notes Comput. Sci. 3572 (2005) pp. 236–247. Google Scholar
T. Fernique, Substitutions on Multi-dimensional Sequences, Words'05, Publications du LACIM 36, eds. S. Brlek and C. Rentenauer (2005) pp. 223–234. Google Scholar
T. Fujitaet al., Ergod. Th. and Dyn. Sys. 16, 1345 (1996). Crossref, Web of Science, Google Scholar
D. M. Hardcastle and K. Khanin, Ergod. Th. and Dyn. Sys. 20, 1711 (2000), DOI: 10.1017/S014338570000095X. Crossref, Web of Science, Google Scholar
S. Ito, M. Keane and M. Ohtsuki, Ergod. Th. and Dyn. Sys. 13, 319 (1993). Crossref, Web of Science, Google Scholar
M. Lothaire , Algebraic combinatorics on words ( Cambridge University Press , 2002 ) . Crossref, Google Scholar
R. Meester, Ergod. Th. and Dyn. Sys. 19, 1077 (1999), DOI: 10.1017/S0143385799133960. Crossref, Web of Science, Google Scholar
M. Morse and G. A. Hedlund, Amer. J. Math. 62, 1 (1940), DOI: 10.2307/2371431. Crossref, Google Scholar
M. Nivat, invited talk at ICALP'97 . Google Scholar
N. Priebe, Geom. Dedicata 79, 239 (2000), DOI: 10.1023/A:1005191014127. Crossref, Web of Science, Google Scholar
N. Pytheas Fogg , Substitutions in Dynamics, Arithmetics and Combinatorics , Lecture Notes in Math. 1794 ( Springer Verlag , 2002 ) . Crossref, Google Scholar
J.-P. Reveilles, "Calcul en nombres entiers et algorithmique," Ph. D Thesis, Univ. Louis Pasteur, Strasbourg, France, 1991 . Google Scholar
A. Quas and L. Q. Zamboni, Theoret. Comput. Sci. 319, 229 (2004), DOI: 10.1016/j.tcs.2004.02.026. Crossref, Web of Science, Google Scholar
O. Salon, C. R. Acad. Sci. Paris Sér. I Math 305, 501 (1987). Google Scholar
B. Solomyak, Ergod. Th. and Dyn. Sys. 17, 695 (1997), DOI: 10.1017/S0143385797084988. Crossref, Web of Science, Google Scholar
B. Solomyak, Zapiski Nauch. Semin. POMI 326, 198 (2005). Google Scholar
W. P. Thurston , Groups, tilings, and finite state automata , AMS Colloquium Lecture notes ( 1989 ) . Google Scholar
J. W. Sander and R. Tijdeman, Theoret. Comput. Sci. 270, 857 (2002), DOI: 10.1016/S0304-3975(01)00281-X. Crossref, Web of Science, Google Scholar
L. Vuillon, European Journal of Combinatorics 22, 263 (2001), DOI: 10.1006/eujc.2000.0444. Crossref, Web of Science, Google Scholar
L. Vuillon, Theoret. Comput. Sci. 209, 261 (1998), DOI: 10.1016/S0304-3975(97)00117-5. Crossref, Web of Science, Google Scholar
K. Wargan, "S-adic dynamical systems and Bratelli diagrams," Ph. D thesis, George Washington University, 2001 . Google Scholar
S. Yasutomi, Number theory and its applications (Kyoto, 1997), Dev. Math. 2 (Kluwer Acad. Publ., Dordrecht, 1999) pp. 347–373. Google Scholar