# Locally catenative sequences and Turtle graphics

Juhani Karhumäki; Svetlana Puzynina

RAIRO - Theoretical Informatics and Applications (2011)

- Volume: 45, Issue: 3, page 311-330
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topKarhumäki, Juhani, and Puzynina, Svetlana. "Locally catenative sequences and Turtle graphics." RAIRO - Theoretical Informatics and Applications 45.3 (2011): 311-330. <http://eudml.org/doc/222012>.

@article{Karhumäki2011,

abstract = {
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.
},

author = {Karhumäki, Juhani, Puzynina, Svetlana},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Combinatorics on words; locally catenative sequences;
turtle graphics; Fibonacci word; combinatorics on words; turtle graphics},

language = {eng},

month = {9},

number = {3},

pages = {311-330},

publisher = {EDP Sciences},

title = {Locally catenative sequences and Turtle graphics},

url = {http://eudml.org/doc/222012},

volume = {45},

year = {2011},

}

TY - JOUR

AU - Karhumäki, Juhani

AU - Puzynina, Svetlana

TI - Locally catenative sequences and Turtle graphics

JO - RAIRO - Theoretical Informatics and Applications

DA - 2011/9//

PB - EDP Sciences

VL - 45

IS - 3

SP - 311

EP - 330

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

LA - eng

KW - Combinatorics on words; locally catenative sequences;
turtle graphics; Fibonacci word; combinatorics on words; turtle graphics

UR - http://eudml.org/doc/222012

ER -

## References

top- J.-P. Allouche and J. Shallit, Automatic Sequences: theory, applications, generalizations. Cambridge (2003). Zbl1086.11015
- 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. Fourier56 (2006) 2115–2130. Zbl1147.11015
- M. Barnsley, Fractals everywhere. Academic Press Professional, San Diego, USA (1998). Zbl0691.58001
- J. Berstel and D. Perrin, Theory of codes. Academic Press (1985). Zbl0587.68066
- J. Cassaigne, On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl.42 (2008) 701–715. Zbl1155.68062
- 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.
- C. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of Formal Languages. Springer (1997).
- F.M. Dekking, Recurrent sets. Adv. Math.44 (1982) 78–104. Zbl0495.51017
- F.M. Dekking, Replicating superfigures and endomorphisms of free groups. J. Comb. Theor. Ser. A32 (1982) 315–320. Zbl0492.05019
- M.M. France and J. Shallit, Wire bending. J. Comb. Theor.50 (1989) 1–23. Zbl0663.10056
- F.R. Gantmacher, The theory of matrices. Chelsea Publishing Company, New York (1962). Zbl0085.01001
- L. Kari, G. Rozenberg and A. Salomaa, L Systems, in Handbook of Formal Languages. Springer (1997).
- S. Kitaev, T. Mansour and P. Seebold, Generating the Peano curve and counting occurrences of some patterns. Automata, Languages and Combinatorics9 (2004) 439–455. Zbl1083.68092
- M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002). Zbl1001.68093
- M. Lothaire, Applied combinatorics on words. Cambridge University Press (2005). Zbl1133.68067
- S. Papert, Mindstorms: children, computers, and powerful ideas. Basic Books, New York (1980).
- P. Prusinkiewicz and A. Lindermayer, The algorithmoic beauty of plants. Springer-Verlag, New York (1990).
- K. Saari, Private communication.
- P. Séébold, Tag-systems for the Hilbert Curve. Discr. Math. Theoret. Comput. Sci.9 (2007) 213–226. Zbl1152.68491
- J. Shallit, A generalization of automatic sequences. Theoret. Comput. Sci.61 (1988) 1–16. Zbl0662.68052

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.