Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde

Allouche, Gabrielle ; Allouche, Jean-Paul ; Shallit, Jeffrey

Annales de l'Institut Fourier, Tome 56 (2006), p. 2115-2130 / Harvested from Numdam

Résumé

Nous montrons que le tracé d’un kolam indien classique, que l’on retrouve aussi dans la tradition des dessins sur le sable aux îles Vanuatu, peut être engendré par un morphisme de monoïde. La suite infinie morphique ainsi obtenue est reliée à la célèbre suite de Prouhet-Thue-Morse, mais elle n’est $k$-automatique pour aucun entier $k \ge 1$.

Abstract

We prove that the drawing of a classical Indian kolam (which one also finds in the tradition of drawings on the sand in the Vanuatu islands) can be described by a morphism of monoids. The corresponding infinite sequence is related to the celebrated Prouhet-Thue-Morse sequence, but it is not $k$-automatic for any integer $k \ge 1$.

Détail

Publié le : 2006-01-01

MR 2290776 | Zbl 1147.11015 | 1 citation dans Numdam

DOI : https://doi.org/10.5802/aif.2235
Classification:  11B85,  68R15,  28A80,  01A07
Mots clés: kolam, dessins sur le sable, courbe de Sierpinski, morphismes de monoïde, suites automatiques

Bibliographie

[1] Allouche, J.-P.; Arnold, A.; Berstel, J.; Brlek, S.; Jockusch, W.; Plouffe, S.; Sagan, B. E. A relative of the Thue-Morse sequence, Discrete Math., Tome 139 (1995), pp. 455-461 | Article | MR 1336854 | Zbl 0839.11007

[2] Allouche, J.-P.; Davison, J. L.; Queffélec, M.; Zamboni, L. Q. Transcendence of Sturmian or morphic continued fractions, J. Number Theory, Tome 91 (2001), pp. 39-66 | Article | MR 1869317 | Zbl 0998.11036

[3] Allouche, J.-P.; Mendès France, M.; Axel, F.; Gratias, D. Automata and automatic sequences, Beyond quasicrystals, Les Houches, 1994 (Les Éditions de Physique, Springer) (1995), pp. 293-367 | MR 1420422 | Zbl 0881.11026

[4] Allouche, J.-P.; Shallit, J.; Ding, C.; Helleseth, T.; Niederreiter, H. The ubiquitous Prouhet-Thue-Morse sequence, Sequences and Their Applications, Springer, Proceedings of SETA’98 (1999), pp. 1-16 | MR 1843077 | Zbl 1005.11005

[5] Allouche, J.-P.; Shallit, J. Automatic Sequences : Theory, Applications, Generalizations, Cambridge University Press (2003) | MR 1997038 | Zbl 01993704

[6] Ascher, M. Ethnomathematics : A Multicultural View of Mathematical Ideas, Pacific Grove, CA and Chapman & Hall, New York (1991) (Brooks Cole Publishing Co.) | MR 1343249 | Zbl 0855.01002

[7] Ascher, M. Mathématiques d’ailleurs. Nombres, formes et jeux dans les sociétés traditionnelles, Le Seuil, Paris (1998) (avec une postface de K. Chemla et S. Pahaut)

[8] Ascher, M. Mathematics Elsewhere : An Exploration of Ideas Across Cultures, Princeton University Press (2002) | MR 1918532 | Zbl 01817586

[9] Ascher, M. Les figures de kolam en Inde du sud, Dossier Pour La Science, Mathématiques Exotiques (2005), pp. 53-57

[10] Belotserkovets, A. Propriétés combinatoires de suites symboliques qui codent des courbes de Péano, Université de Novosibirsk (2003) (Masters thesis)

[11] Brlek, S. Enumeration of factors in the Thue-Morse word, Discrete Appl. Math., Tome 24 (1989), pp. 83-96 | Article | MR 1011264 | Zbl 0683.20045

[12] Carlitz, L.; Scoville, R.; E. Hoggatt, Jr., V. Representations for a special sequence, Fibonacci Quart., Tome 10 (1972), p. 499-518, 550 | MR 319880 | Zbl 0255.05001

[13] Cassaigne, J. Limit values of the recurrence quotient of Sturmian sequences, Theoret. Comput. Sci., Tome 218 (1999), pp. 3-12 | Article | MR 1687748 | Zbl 0916.68115

[14] Cobham, A. Uniform tag sequences, Math. Systems Theory, Tome 6 (1972), pp. 164-192 | Article | MR 457011 | Zbl 0253.02029

[15] Durand, F. A generalization of Cobham’s theorem, Theory Comput. Syst., Tome 31 (1998), pp. 169-185 | Article | MR 1491657 | Zbl 0895.68081

[16] Gerdes, P. Une tradition géométrique en Afrique, les dessins sur le sable, I, II & III, L’Harmattan (1995) | Zbl 0839.01003

[17] Gerdes, P. Ethnomathematics as a new research field, illustrated by studies of mathematical ideas in African history. Filling a Gap in the History of Science., Science and Cultural Diversity, Cuadernos de Quipu No 5. México, J. J. Saldaña (et al.), éd., IASCUD, International Association for Science and Cultural Diversity (2001) (http://iascud.univalle.edu.co/indicelibro.htm)

[18] Hall, R. W. A course in multicultural mathematics (Primus, à paraître)

[19] Kitaev, S.; Mansour, T.; Séébold, P. Generating the Peano curve and counting occurrences of some patterns, J. Autom. Lang. Comb., Tome 9 (2004), pp. 439-455 | MR 2198708 | Zbl 1083.68092

[20] Norman, M. G.; Moscato, P. The euclidean traveling salesman problem and a space-filling curve, Chaos, Solitons and Fractals, Tome 6 (1995), pp. 389-397 | Article | Zbl 0906.68073

[21] Platzman, L. K.; Bartholdi Iii, J. J. Spacefilling curves and the planar travelling salesman problem, J. Assoc. Comput. Mach., Tome 36 (1989), pp. 719-737 | MR 1072243 | Zbl 0697.68047

[22] Prusinkiewicz, P.; Samavati, F. F.; Smith, C.; Karwowski, R. L-System description of subdivision curves, Int. J. Shape Model., Tome 9 (2003), pp. 41-59 | Article | Zbl 1099.65506

[23] Rosenfeld, A.; Siromoney, R. Picture languages : a survey, Languages of Design, Tome 1 (1993), pp. 229-245

[24] Salon, O. Suites automatiques à multi-indices, Sém. Théor. Nombres Bordeaux (1986-1987), pp. 27 (Exposé 4, 4-01-4-27 ; suivi par un appendice par J. Shallit, 4-29A-4-36A) | Zbl 0653.10049

[25] Séébold, P. Tag-systems for the Hilbert curve (J. Autom. Lang. Comb., à paraître)

[26] Séébold, P. The Peano curve and iterated morphisms, 10 $^{\rm es}$ Journées Montoises d’Informatique Théorique, Liège (Belgique) (2004), pp. 338-351 (Rapport ULg, Institut de Mathématiques 04.006)

[27] Séébold, P.; Slowinski, K. The shortest way to draw a connected picture, Computer Graphics Forum, Tome 10 (1991), pp. 319-327 | Article

[28] Shallit, J. A generalization of automatic sequences, Theoret. Comput. Sci., Tome 61 (1988), pp. 1-16 | Article | MR 974766 | Zbl 0662.68052

[29] Shallit, J. Automaticity IV : sequences, sets, and diversity, J. Théorie Nombres, Bordeaux, Tome 8 (1996), pp. 347-367 | Article | Numdam | MR 1438474 | Zbl 0876.11010

[30] Shallit, J.; Stolfi, J. Two methods for generating fractals, Computers and Graphics, Tome 13 (1989), pp. 185-191 | Article

[31] Sierpinski, W. Sur une courbe dont tout point est un point de ramification, C. R. Acad. Sci., Tome 160 (1915), pp. 302-305

[32] Sierpinski, W. Sur une courbe cantorienne qui contient une image biunivoque et continue de toute courbe donnée, C. R. Acad. Sci., Tome 162 (1916), pp. 629-632

[33] Siromoney, G.; Siromoney, R.; Ehrig, H.; Nagl, M.; Rosenfeld, A.; Rozenberg, G. Rosenfeld’s cycle grammars and kolam, Graph grammars and their application to computer science, Springer, Third International Workshop (Lect. Notes Comput. Sci.) Tome 291 (1987), pp. 564-579 | MR 943166 | Zbl 0657.68076

[34] Siromoney, G.; Siromoney, R.; Krithivasan, K. Array grammars and kolam, Computer Graphics and Image Processing, Tome 3 (1974), pp. 63-82 | Article | MR 353725

[35] Siromoney, G.; Siromoney, R.; Robinsin, T. Kambi kolam and cycle grammars, A perspective in theoretical computer science-commemorative volume for Gift Siromoney, World Scientific, Singapore ((R. Narasimhan ed.). Series in Computer Science) Tome 16 (1989), pp. 267-300

[36] Siromoney, R.; Subramanian, K. G. Space-filling curves and infinite graphs, Graph-grammars and their application to computer science, Springer, Haus Ohrbeck/Ger. 1982, 2nd International. Workshop (Lect. Notes Comput. Sci.) Tome 153 (1983), pp. 380-391 | Zbl 0519.68068

[37] Tamura, J. Some problems having their origin in the power series $\sum _{n=1}^{\infty }z^{[\alpha n]}$, Reports of the meeting on analytic theory of numbers and related topics, Gakushuin University (1992), pp. 190-212