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).
A substitution is a morphism of the free monoid: each letter is mapped to a word, and the image of a word is the concatenation of the images of its letters. This paper introduces a generalization of the notion of substitution, where the image of a letter is not a word but a pattern, i.e., a “word with holes”: the image of a word is obtained by connecting the patterns corresponding to each of the letters by means of local rules. We completely characterize pattern substitutions which are defined on every biinfinite sequence, and we explain how to build them. We show that every biinfinite sequence which is a fixed point of a pattern substitution is substitutive, i.e., it is the image, by a letter to letter morphism, of a fixed point of a substitution (in the usual meaning).
@article{ITA_2007__41_3_267_0,
author = {Pytheas Fogg, N.},
title = {Substitutions par des motifs en dimension 1},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {41},
year = {2007},
pages = {267-284},
doi = {10.1051/ita:2007022},
mrnumber = {2354358},
zbl = {pre05211860},
language = {fr},
url = {http://dml.mathdoc.fr/item/ITA_2007__41_3_267_0}
}
Pytheas Fogg, N. Substitutions par des motifs en dimension 1. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) pp. 267-284. doi : 10.1051/ita:2007022. http://gdmltest.u-ga.fr/item/ITA_2007__41_3_267_0/
[1] , and, Sur la complexité des nombres algébriques. C. R. Acad. Sci. Paris Ser. I 339 (2004) 11-14. | Zbl 1119.11019
[2] and, Automatic sequences. Cambridge University Press (2003). | MR 1997038 | Zbl 1086.11015
[3] and, Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181-207. | Zbl 1007.37001
[4] , and, Discrete planes, -actions, Jacobi-Perron algorithm and substitutions. Ann. Inst. Fourier (Grenoble) 52 (2002) 1001-1045. | Numdam | Zbl 1017.11006
[5] , and, Two-dimensional iterated morphisms and discrete planes. Theoret. Comput. Sci. 319 (2004) 145-176. | Zbl 1068.37004
[6] , Uniform tag sequences. Math. Syst. Theory 6 (1972) 164-192. | Zbl 0253.02029
[7] , 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. | Zbl 1038.11016
[8] , Matching rules and substitution tilings. Ann. Math. 147 (1998) 181-223. | Zbl 0941.52018
[9] , Automatic sequences, de Gruyter Expositions in Mathematics 36 (2003). | MR 1958215 | Zbl 1057.11015
[10] , Dynamics of multi-dimensional substitutions. Ph.D. Thesis, George Washington University (2000).
[11] and, Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Systems 22 (2002) 1201-1214. | Zbl 1014.37003
[12] and, Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Systems 22 (2002) 1191-1199. | Zbl 1014.37004
[13] and, Tiling the line with translates of one tile. Invent. Math. 124 (1996) 341-365. | Zbl 0847.05037
[14] , Algebraic Combinatorics on words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press. | MR 1905123 | Zbl 1001.68093
[15] , Applied Combinatorics on words, Encyclopedia of Mathematics and its Applications 105, Cambridge University Press. | MR 2165687 | Zbl 1133.68067
[16] , An automata-theoretic decidability proof for first-order theory of with morphic predicate . J. Autom. Lang. Comb. 4 (1999), 229-245. | Zbl 0937.68078
[17] and, More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002) 351-376. | Zbl 1033.68069
[18] , Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794 (2002). | MR 1970385 | Zbl 1014.11015
[19] , Substitution dynamical systems. Spectral analysis. Lect. Notes Math. 1294 (1987). | MR 924156 | Zbl 0642.28013
[20] and, The mathematical theory of -systems. Academic Press (1980). | MR 561711 | Zbl 0508.68031
[21] , Approximation to real numbers by cubic algebraic integers I. Proc. London Math. Soc. 88 (2004) 42-62. | Zbl 1035.11028
[22] , Approximation to real numbers by cubic algebraic integers II. Ann. Math. 158 (2003) 1081-1087. | Zbl 1044.11061
[23] , 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. | Zbl 0653.10049
[24] , Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I 305 (1987) 501-504. | Zbl 0628.10007
[25] , Dynamics of self-similar tilings. Ergodic Theory Dynam. Systems 17 (1997) 695-738. | Zbl 0884.58062
[26] , Groups, tilings and finite state automata, Lectures notes distributed in conjunction with the Colloquium Series, AMS Colloquium lectures (1989).