Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-16T11:15:20.229Z Has data issue: false hasContentIssue false
  • English
  • Français

Substitutions par des motifs en dimension 1

Published online by Cambridge University Press:  25 September 2007

N. Pytheas Fogg
N. Pytheas Fogg*
Affiliation:
Institut de mathématiques de Luminy, CNRS UMR 6206 / FRUMAM, case 907, 163 avenue de Luminy, 13288 Marseille Cedex 9, France; [email protected]
Get access

Abstract

Une substitution est un morphisme de monoïdes libres : chaque lettre a pour image un mot, et l'image d'un mot est la concaténation des images de ses lettres. Cet article introduit une généralisation de la notion de substitution, où l'image d'une lettre n'est plus un mot mais un motif, c'est-à-dire un “mot à trous”, l'image d'un mot étant obtenue en raccordant les motifs correspondant à chacune de ses lettres à l'aide de règles locales. On caractérise complètement les substitutions par des motifs qui sont définies sur toute suite biinfinie, et on explique comment les construire. On montre que toute suite biinfinie qui est point fixe d'une substitution par des motifs est substitutive, c'est-à-dire est l'image, par un morphisme lettre à lettre, d'un point fixe de substitution (au sens usuel).

Keywords

Substitutionswordspatternstilings of the lineword combinatoricsSubstitutionsmotsmotifspavages de la droitecombinatoire des mots
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 41 , Issue 3 , July 2007 , pp. 267 - 284
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adamczewski, B., Bugeaud, Y. and Luca, F., Sur la complexité des nombres algébriques. C. R. Acad. Sci. Paris Ser. I 339 (2004) 11–14. CrossRef
J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press (2003).
Arnoux, P. and Ito, S., Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181–207.
Arnoux, P., Berthé, V. and Ito, S., Discrete planes, ${\mathbb Z}^2$ -actions, Jacobi-Perron algorithm and substitutions. Ann. Inst. Fourier (Grenoble) 52 (2002) 1001–1045. CrossRef
Arnoux, P., Berthé, V. and Siegel, A., Two-dimensional iterated morphisms and discrete planes. Theoret. Comput. Sci. 319 (2004) 145–176. CrossRef
Cobham, A., Uniform tag sequences. Math. Syst. Theory 6 (1972) 164–192. CrossRef
F. Durand, Combinatorial and dynamical study of substitutions around the theorem of Cobham. Dynamics and Randomness, edited by A. Maass et al., Kluwer Academic Publishers (2002) 53–94.
Goodman-Strauss, C., Matching rules and substitution tilings. Ann. Math. 147 (1998) 181–223. CrossRef
F. von Haeseler, Automatic sequences, de Gruyter Expositions in Mathematics 36 (2003).
C.W. Hansen, Dynamics of multi-dimensional substitutions. Ph.D. Thesis, George Washington University (2000).
Kamae, T. and Zamboni, L.Q., Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Systems 22 (2002) 1201–1214.
Kamae, T. and Zamboni, L.Q., Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Systems 22 (2002) 1191–1199.
Lagarias, J.C. and Wang, Y., Tiling the line with translates of one tile. Invent. Math. 124 (1996) 341–365. CrossRef
M. Lothaire, Algebraic Combinatorics on words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press.
M. Lothaire, Applied Combinatorics on words, Encyclopedia of Mathematics and its Applications 105, Cambridge University Press.
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.
Maes, A. and Rigo, M., More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002) 351–376.
N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794 (2002).
M. Queffélec, Substitution dynamical systems. Spectral analysis. Lect. Notes Math. 1294 (1987).
G. Rozenberg and A. Salomaa, The mathematical theory of L-systems. Academic Press (1980).
Approximation, D. Roy to real numbers by cubic algebraic integers I. Proc. London Math. Soc. 88 (2004) 42–62.
Approximation, D. Roy to real numbers by cubic algebraic integers II. Ann. Math. 158 (2003) 1081–1087.
O. Salon, Suites automatiques à multi-indices, Séminaire de Théorie des Nombres de Bordeaux, Exp. No. 4, Univ. Bordeaux-I (1986–1987) 4.01–4.27.
Salon, O., Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I 305 (1987) 501–504.
Solomyak, B., Dynamics of self-similar tilings. Ergodic Theory Dynam. Systems 17 (1997) 695–738. CrossRef
W.P. Thurston, Groups, tilings and finite state automata, Lectures notes distributed in conjunction with the Colloquium Series, AMS Colloquium lectures (1989).