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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2011104/
[1] Automatic Sequences: theory, applications, generalizations. Cambridge (2003). | MR | Zbl
and ,[2] 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
, and ,[3] Fractals everywhere. Academic Press Professional, San Diego, USA (1998). | MR | Zbl
,[4] Theory of codes. Academic Press (1985). | MR | Zbl
and ,[5] On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701-715. | EuDML | Numdam | MR | Zbl
,[6] 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] Combinatorics of words, in Handbook of Formal Languages. Springer (1997). | MR
and ,[8] Recurrent sets. Adv. Math. 44 (1982) 78-104. | MR | Zbl
,[9] Replicating superfigures and endomorphisms of free groups. J. Comb. Theor. Ser. A 32 (1982) 315-320. | MR | Zbl
,[10] Wire bending. J. Comb. Theor. 50 (1989) 1-23. | MR | Zbl
and ,[11] The theory of matrices. Chelsea Publishing Company, New York (1962). | Zbl
,[12] L Systems, in Handbook of Formal Languages. Springer (1997). | MR | Zbl
, and ,[13] Generating the Peano curve and counting occurrences of some patterns. Automata, Languages and Combinatorics 9 (2004) 439-455. | MR | Zbl
, and ,[14] Algebraic combinatorics on words. Cambridge University Press (2002). | MR | Zbl
,[15] Applied combinatorics on words. Cambridge University Press (2005). | MR | Zbl
,[16] Mindstorms: children, computers, and powerful ideas. Basic Books, New York (1980).
,[17] The algorithmoic beauty of plants. Springer-Verlag, New York (1990). | MR | Zbl
and ,[18] Private communication.
,[19] Tag-systems for the Hilbert Curve. Discr. Math. Theoret. Comput. Sci. 9 (2007) 213-226. | MR | Zbl
,[20] A generalization of automatic sequences. Theoret. Comput. Sci. 61 (1988) 1-16. | MR | Zbl
,Cité par Sources :