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.
@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},
volume = {45},
year = {2011},
pages = {311-330},
doi = {10.1051/ita/2011104},
mrnumber = {2836492},
zbl = {1228.68042},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 311-330. doi : 10.1051/ita/2011104. http://gdmltest.u-ga.fr/item/ITA_2011__45_3_311_0/
[1] and , Automatic Sequences: theory, applications, generalizations. Cambridge (2003). | MR 1997038 | Zbl 1086.11015
[2] , and , Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde. Ann. Inst. Fourier 56 (2006) 2115-2130. | Numdam | MR 2290776 | Zbl 1147.11015
[3] , Fractals everywhere. Academic Press Professional, San Diego, USA (1998). | MR 977274 | Zbl 0784.58002
[4] and , Theory of codes. Academic Press (1985). | MR 797069 | Zbl 0587.68066
[5] , On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701-715. | Numdam | MR 2458702 | Zbl 1155.68062
[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 1076837 | Zbl 0766.68072
[7] and , Combinatorics of words, in Handbook of Formal Languages. Springer (1997). | MR 1469998
[8] , Recurrent sets. Adv. Math. 44 (1982) 78-104. | MR 654549 | Zbl 0495.51017
[9] , Replicating superfigures and endomorphisms of free groups. J. Comb. Theor. Ser. A 32 (1982) 315-320. | MR 657046 | Zbl 0492.05019
[10] and , Wire bending. J. Comb. Theor. 50 (1989) 1-23. | MR 978063 | Zbl 0663.10056
[11] , The theory of matrices. Chelsea Publishing Company, New York (1962). | Zbl 0927.15001
[12] , and , L Systems, in Handbook of Formal Languages. Springer (1997). | MR 1469997 | Zbl 0866.68057
[13] , and , Generating the Peano curve and counting occurrences of some patterns. Automata, Languages and Combinatorics 9 (2004) 439-455. | MR 2198708 | Zbl 1083.68092
[14] , Algebraic combinatorics on words. Cambridge University Press (2002). | MR 1905123 | Zbl 1221.68183
[15] , Applied combinatorics on words. Cambridge University Press (2005). | MR 2165687 | Zbl 1133.68067
[16] , Mindstorms: children, computers, and powerful ideas. Basic Books, New York (1980).
[17] and , The algorithmoic beauty of plants. Springer-Verlag, New York (1990). | MR 1067146 | Zbl 0859.92003
[18] , Private communication.
[19] , Tag-systems for the Hilbert Curve. Discr. Math. Theoret. Comput. Sci. 9 (2007) 213-226. | MR 2306529 | Zbl 1152.68491
[20] , A generalization of automatic sequences. Theoret. Comput. Sci. 61 (1988) 1-16. | MR 974766 | Zbl 0662.68052