Locally catenative sequences and Turtle graphics
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 3, pp. 311-330.

Motivated by striking properties of the well known Fibonacci word we consider pictures which are defined by this word and its variants via so-called turtle graphics. Such a picture can be bounded or unbounded. We characterize when the picture defined by not only the Fibonacci recurrence, but also by a general recurrence formula, is bounded, the characterization being computable.

DOI : 10.1051/ita/2011104
Classification : 68R15
Mots-clés : combinatorics on words, locally catenative sequences, turtle graphics, Fibonacci word 
@article{ITA_2011__45_3_311_0,
     author = {Karhum\"aki, Juhani and Puzynina, Svetlana},
     title = {Locally catenative sequences and {Turtle} graphics},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {311--330},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {3},
     year = {2011},
     doi = {10.1051/ita/2011104},
     mrnumber = {2836492},
     zbl = {1228.68042},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2011104/}
}
TY  - JOUR
AU  - Karhumäki, Juhani
AU  - Puzynina, Svetlana
TI  - Locally catenative sequences and Turtle graphics
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2011
SP  - 311
EP  - 330
VL  - 45
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011104/
DO  - 10.1051/ita/2011104
LA  - en
ID  - ITA_2011__45_3_311_0
ER  - 
%0 Journal Article
%A Karhumäki, Juhani
%A Puzynina, Svetlana
%T Locally catenative sequences and Turtle graphics
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 311-330
%V 45
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2011104/
%R 10.1051/ita/2011104
%G en
%F ITA_2011__45_3_311_0
Karhumäki, Juhani; Puzynina, Svetlana. Locally catenative sequences and Turtle graphics. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 3, pp. 311-330. doi : 10.1051/ita/2011104. http://www.numdam.org/articles/10.1051/ita/2011104/

[1] J.-P. Allouche and J. Shallit, Automatic Sequences: theory, applications, generalizations. Cambridge (2003). | MR | Zbl

[2] G. Allouche, J.-P. Allouche and J. Shallit, Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde. Ann. Inst. Fourier 56 (2006) 2115-2130. | EuDML | Numdam | MR | Zbl

[3] M. Barnsley, Fractals everywhere. Academic Press Professional, San Diego, USA (1998). | MR | Zbl

[4] J. Berstel and D. Perrin, Theory of codes. Academic Press (1985). | MR | Zbl

[5] J. Cassaigne, On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701-715. | EuDML | Numdam | MR | Zbl

[6] C. Choffrut, Iterated substitutions and locally catenative systems: a decidability result in the binary case, in Lindenmayer Systems: Impacts on theoretical computer science, computer graphics, and developmental biology. G. Rozenberg and A. Salomaa, Eds. Springer-Verlag, Berlin (1992) 49-92. Preliminary version: C. Choffrut, Iterated Substitutions and Locally Catanative Systems: A Decidability Result in the Binary Case. ICALP (1990) 490-500. | MR | Zbl

[7] C. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of Formal Languages. Springer (1997). | MR

[8] F.M. Dekking, Recurrent sets. Adv. Math. 44 (1982) 78-104. | MR | Zbl

[9] F.M. Dekking, Replicating superfigures and endomorphisms of free groups. J. Comb. Theor. Ser. A 32 (1982) 315-320. | MR | Zbl

[10] M.M. France and J. Shallit, Wire bending. J. Comb. Theor. 50 (1989) 1-23. | MR | Zbl

[11] F.R. Gantmacher, The theory of matrices. Chelsea Publishing Company, New York (1962). | Zbl

[12] L. Kari, G. Rozenberg and A. Salomaa, L Systems, in Handbook of Formal Languages. Springer (1997). | MR | Zbl

[13] S. Kitaev, T. Mansour and P. Seebold, Generating the Peano curve and counting occurrences of some patterns. Automata, Languages and Combinatorics 9 (2004) 439-455. | MR | Zbl

[14] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002). | MR | Zbl

[15] M. Lothaire, Applied combinatorics on words. Cambridge University Press (2005). | MR | Zbl

[16] S. Papert, Mindstorms: children, computers, and powerful ideas. Basic Books, New York (1980).

[17] P. Prusinkiewicz and A. Lindermayer, The algorithmoic beauty of plants. Springer-Verlag, New York (1990). | MR | Zbl

[18] K. Saari, Private communication.

[19] P. Séébold, Tag-systems for the Hilbert Curve. Discr. Math. Theoret. Comput. Sci. 9 (2007) 213-226. | MR | Zbl

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

Cité par Sources :