Pattern subsitutions in dimension

N. Pytheas Fogg

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 3, page 267-284
  • ISSN: 0988-3754

Abstract

top
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).

How to cite

top

Pytheas Fogg, N.. "Substitutions par des motifs en dimension 1." RAIRO - Theoretical Informatics and Applications 41.3 (2007): 267-284. <http://eudml.org/doc/250062>.

@article{PytheasFogg2007,
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). },
author = {Pytheas Fogg, N.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Substitutions; mots; motifs; pavages de la droite; combinatoire des mots},
language = {fre},
month = {9},
number = {3},
pages = {267-284},
publisher = {EDP Sciences},
title = {Substitutions par des motifs en dimension 1},
url = {http://eudml.org/doc/250062},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Pytheas Fogg, N.
TI - Substitutions par des motifs en dimension 1
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/9//
PB - EDP Sciences
VL - 41
IS - 3
SP - 267
EP - 284
AB - 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).
LA - fre
KW - Substitutions; mots; motifs; pavages de la droite; combinatoire des mots
UR - http://eudml.org/doc/250062
ER -

References

top
  1. B. Adamczewski, Y. Bugeaud and F. Luca, Sur la complexité des nombres algébriques. C. R. Acad. Sci. Paris Ser. I339 (2004) 11–14.  
  2. J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press (2003).  Zbl1086.11015
  3. P. Arnoux and S. Ito, Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin8 (2001) 181–207.  Zbl1007.37001
  4. P. Arnoux, V. Berthé and S. Ito, Discrete planes, 2 -actions, Jacobi-Perron algorithm and substitutions. Ann. Inst. Fourier (Grenoble)52 (2002) 1001–1045.  Zbl1017.11006
  5. P. Arnoux, V. Berthé and A. Siegel, Two-dimensional iterated morphisms and discrete planes. Theoret. Comput. Sci.319 (2004) 145–176.  Zbl1068.37004
  6. A. Cobham, Uniform tag sequences. Math. Syst. Theory6 (1972) 164–192.  Zbl0253.02029
  7. 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.  Zbl1038.11016
  8. C. Goodman-Strauss, Matching rules and substitution tilings. Ann. Math.147 (1998) 181–223.  Zbl0941.52018
  9. F. von Haeseler, Automatic sequences, de Gruyter Expositions in Mathematics 36 (2003).  Zbl1057.11015
  10. C.W. Hansen, Dynamics of multi-dimensional substitutions. Ph.D. Thesis, George Washington University (2000).  
  11. T. Kamae and L.Q. Zamboni, Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Systems22 (2002) 1201–1214.  Zbl1014.37003
  12. T. Kamae and L.Q. Zamboni, Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Systems22 (2002) 1191–1199.  Zbl1014.37004
  13. J.C. Lagarias and Y. Wang, Tiling the line with translates of one tile. Invent. Math.124 (1996) 341–365.  Zbl0847.05037
  14. M. Lothaire, Algebraic Combinatorics on words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press.  Zbl1001.68093
  15. M. Lothaire, Applied Combinatorics on words, Encyclopedia of Mathematics and its Applications 105, Cambridge University Press.  Zbl1001.68093
  16. 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.  Zbl0937.68078
  17. A. Maes and M. Rigo, More on generalized automatic sequences. J. Autom. Lang. Comb.7 (2002) 351–376.  Zbl1033.68069
  18. N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math.1794 (2002).  Zbl1014.11015
  19. M. Queffélec, Substitution dynamical systems. Spectral analysis. Lect. Notes Math.1294 (1987).  Zbl0642.28013
  20. G. Rozenberg and A. Salomaa, The mathematical theory of L-systems. Academic Press (1980).  Zbl0508.68031
  21. D. Roy, Approximation to real numbers by cubic algebraic integers I. Proc. London Math. Soc.88 (2004) 42–62.  Zbl1035.11028
  22. D. Roy, Approximation to real numbers by cubic algebraic integers II. Ann. Math.158 (2003) 1081–1087.  Zbl1044.11061
  23. 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.  Zbl0653.10049
  24. O. Salon, Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I305 (1987) 501–504.  Zbl0628.10007
  25. B. Solomyak, Dynamics of self-similar tilings. Ergodic Theory Dynam. Systems17 (1997) 695–738.  Zbl0884.58062
  26. W.P. Thurston, Groups, tilings and finite state automata, Lectures notes distributed in conjunction with the Colloquium Series, AMS Colloquium lectures (1989).  

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.