[Suite double de Thue–Morse–Pascal et structures semblables]
Si une suite bidimensionnelle récurrente avec conditions initiales définies par substitution linéaire et une suite bidimensionnelle engendrée par substitution plane sont identiques sur un carré initial assez grand, alors elles coïncident partout. Après avoir démontré ce principe on lʼapplique à quelques exemples concrets. Lʼun dʼentre-eux est la suite bidimensionnelle de Thue–Morse–Pascal définie par deux exemplaires de la suite de Prouhet–Thue–Morse comme couple de conditions initiales et lʼaddition du triangle de Pascal modulo 2 comme règle de récurrence. Il sʼensuit que la suite bidimensionnelle de Thue–Morse–Pascal est le résultat de 15 règles de substitution, chacune dʼentre-elles consistant de la substitution dʼune certaine matrice avec une matrice .
If a recurrent two-dimensional sequence with initial conditions defined by linear substitution and a two-dimensional sequence that is generated by planar substitution are identical over a sufficiently large initial square, then they will coincide over all. After proving this general principle, we apply it to some concrete examples. One of them, the Thue–Morse–Pascal two-dimensional sequence, is defined by two copies of the Prouhet–Thue–Morse sequence as pair of initial conditions and by the Pascal Triangle Addition modulo 2 as rule of recurrence. As it follows, the Thue–Morse–Pascal two-dimensional sequence is the result of 15 substitution rules, each of them consisting of the substitution of some matrix with an matrix.
Accepté le :
Publié le :
@article{CRMATH_2011__349_17-18_939_0,
author = {Mihai Prunescu},
title = {The {Thue{\textendash}Morse{\textendash}Pascal} double sequence and similar structures},
journal = {Comptes Rendus. Math\'ematique},
pages = {939--942},
publisher = {Elsevier},
volume = {349},
number = {17-18},
year = {2011},
doi = {10.1016/j.crma.2011.07.022},
language = {en},
}
Mihai Prunescu. The Thue–Morse–Pascal double sequence and similar structures. Comptes Rendus. Mathématique, Volume 349 (2011) no. 17-18, pp. 939-942. doi : 10.1016/j.crma.2011.07.022. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2011.07.022/
[1] Automatic Sequences – Theory, Applications, Generalizations, Cambridge University Press, 2003
[2] The ubiquitous Prouhet–Thue–Morse sequence, Singapore, 1998 (Springer Series Discrete Mathematics in Theoretical Computer Science), Springer, London (1999), pp. 1-16
[3] Functional stepped surfaces, flips and generalized substitutions, Theoretical Computer Science, Volume 380 (2007), pp. 251-265
[4] Directions in Mathematical Quasicrystals (M. Baake; R.V. Moody, eds.), CRM Monograph Series, AMS, Providence, RI, 2000
[5] Duality of model sets generated by substitution, Romanian Journal of Pure and Applied Mathematics, Volume 50 (2005), pp. 619-639
[6] Tilings and Patterns, Dover Publications, 2011
[7] Theory of cellular automata: A survey, Theoretical Computer Science, Volume 334 (2005), pp. 3-33
[8] The Algorithmic Beauty of Plants, Springer-Verlag, 1996
[9] The Fractal Geometry of Nature, W.H. Freeman and Company, San Francisco, 1977 (p. 1982)
[10] The Mathematics of Aperiodic Order (R.V. Moody, ed.), Proceedings of the NATO Advanced Study Institute on Long Range Aperiodic Order, Kluwer Academic Publishings, 1997
[11] Sequences close to periodic, Russian Mathematical Surveys, Volume 64 (2009) no. 5, pp. 805-871
[12] Carpets and rugs: An exercise in numbers, Leonardo, Volume 25 (1992) no. 1, pp. 69-71
[13] Pentaplexity, Mathematical Intelligencer, Volume 2 (1979) no. 1, pp. 32-37
[14] Multi-dimensional constant-length substitution sequences, Topology and Applications, Volume 152 (2005), pp. 44-69
[15] Undecidable properties of recurrent double sequences, Notre Dame Journal of Formal Logic, Volume 49 (2008) no. 2, pp. 143-151
[16] Self-similar carpets over finite fields, European Journal of Combinatorics, Volume 30 (2009) no. 4, pp. 866-878
[17] Recurrent double sequences that can be generated by context-free substitutions, Fractals, Volume 18 (2010) no. 1, pp. 65-73
[18] M. Prunescu, Some new counterexamples to context-free substitution in recurrent double sequences over finite sets, Preprint, 2010, submitted for publication, http://home.mathematik.uni-freiburg.de/prunescu/RecDoubleCounterexe.pdf.
[19] M. Prunescu, Recurrent two-dimensional sequences generated by homomorphisms of finite abelian p-groups with periodic initial conditions, Preprint, 2010, Fractals, in press, http://home.mathematik.uni-freiburg.de/prunescu/RecDoublePerBord.pdf.
[20] Linear recurrent double sequences with constant border in are classified according to their geometric content, Symmetry (An MDPI Journal), Volume 3 (2011) no. 3, pp. 402-442
[21] Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, Volume 12 (1971) no. 3, pp. 177-209
[22] Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, Springer-Verlag, 1992
[23] O. Salon, Suites automatiques à multi-indices, in: Séminaire de Théorie des Nombres de Bordeaux, Exposé 4, 1986–1987, 4-01–4-27; followed by an Appendix by J. Shallit, 4-29A–4-36A.
[24] Suites automatiques à multi-indices et algébricité, C. R. Acad. Sci. Paris, Sér. I, Volume 305 (1987), pp. 501-504
[25] Proving theorems by pattern recognition, Bell System Technical Journal, Volume 40 (1961) no. 1, pp. 1-41
[26] Cellular automata can generate fractals, Discrete Applied Mathematics, Volume 8 (1984), pp. 91-99
[27] A New Kind of Science, Wolfram Media, 2002 (ISBN: 1-57955-008-8)
Cité par Sources :
Commentaires - Politique