Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde
[Indian kolam, drawings on the sand in the Vanuatu Islands, Sierpinski curve, and morphisms of monoids]
Annales de l'Institut Fourier, Volume 56 (2006) no. 7, pp. 2115-2130.

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 k1.

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 k1.

DOI: 10.5802/aif.2235
Classification: 11B85,  68R15,  28A80,  01A07
Keywords: kolam, drawings on the sand, Sierpinski curve, morphisms of monoid, automatic sequences
Allouche, Gabrielle 1; Allouche, Jean-Paul 2; Shallit, Jeffrey 3

1 24 rue Marceau 37000 Tours (France)
2 CNRS, LRI, Bâtiment 490 91405 Orsay Cedex (France)
3 University of Waterloo School of Computer Science Waterloo, Ontario N2L 3G1 (Canada)
@article{AIF_2006__56_7_2115_0,
     author = {Allouche, Gabrielle and Allouche, Jean-Paul and Shallit, Jeffrey},
     title = {Kolam indiens, dessins sur le sable aux {\^\i}les {Vanuatu,} courbe de {Sierpinski} et morphismes de mono{\"\i}de},
     journal = {Annales de l'Institut Fourier},
     pages = {2115--2130},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {56},
     number = {7},
     year = {2006},
     doi = {10.5802/aif.2235},
     mrnumber = {2290776},
     zbl = {1147.11015},
     language = {fr},
     url = {http://www.numdam.org/articles/10.5802/aif.2235/}
}
TY  - JOUR
AU  - Allouche, Gabrielle
AU  - Allouche, Jean-Paul
AU  - Shallit, Jeffrey
TI  - Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde
JO  - Annales de l'Institut Fourier
PY  - 2006
DA  - 2006///
SP  - 2115
EP  - 2130
VL  - 56
IS  - 7
PB  - Association des Annales de l’institut Fourier
UR  - http://www.numdam.org/articles/10.5802/aif.2235/
UR  - https://www.ams.org/mathscinet-getitem?mr=2290776
UR  - https://zbmath.org/?q=an%3A1147.11015
UR  - https://doi.org/10.5802/aif.2235
DO  - 10.5802/aif.2235
LA  - fr
ID  - AIF_2006__56_7_2115_0
ER  - 
%0 Journal Article
%A Allouche, Gabrielle
%A Allouche, Jean-Paul
%A Shallit, Jeffrey
%T Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde
%J Annales de l'Institut Fourier
%D 2006
%P 2115-2130
%V 56
%N 7
%I Association des Annales de l’institut Fourier
%U https://doi.org/10.5802/aif.2235
%R 10.5802/aif.2235
%G fr
%F AIF_2006__56_7_2115_0
Allouche, Gabrielle; Allouche, Jean-Paul; Shallit, Jeffrey. Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde. Annales de l'Institut Fourier, Volume 56 (2006) no. 7, pp. 2115-2130. doi : 10.5802/aif.2235. http://www.numdam.org/articles/10.5802/aif.2235/

[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., Volume 139 (1995), pp. 455-461 | DOI | MR | Zbl

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

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

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

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

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

[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 | Zbl

[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., Volume 24 (1989), pp. 83-96 | DOI | MR | Zbl

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

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

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

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

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

[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 (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., Volume 9 (2004), pp. 439-455 | MR | Zbl

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

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

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

[23] Rosenfeld, A.; Siromoney, R. Picture languages : a survey, Languages of Design, Volume 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

[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 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, Volume 10 (1991), pp. 319-327 | DOI

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

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

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

[31] Sierpinski, W. Sur une courbe dont tout point est un point de ramification, C. R. Acad. Sci., Volume 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., Volume 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 (Lect. Notes Comput. Sci.), Volume 291 (1987), pp. 564-579 | MR | Zbl

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

[35] Siromoney, G.; Siromoney, R.; Robinsin, T. Kambi kolam and cycle grammars, A perspective in theoretical computer science-commemorative volume for Gift Siromoney ((R. Narasimhan ed.). Series in Computer Science), Volume 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 (Lect. Notes Comput. Sci.), Volume 153 (1983), pp. 380-391 | Zbl

[37] Tamura, J. Some problems having their origin in the power series n=1 z [αn] , Reports of the meeting on analytic theory of numbers and related topics, Gakushuin University, 1992, pp. 190-212

Cited by Sources: