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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/articles/10.1051/ita/2011104/

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

[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. | Zbl | MR | mathdoc-id | EuDML

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

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

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

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

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

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

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

[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). | Zbl | MR

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

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

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

[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). | Zbl | MR

[18] K. Saari, Private communication.

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

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

Cité par Sources :