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

Abstract

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

How to cite

top

Karhumä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
  1. J.-P. Allouche and J. Shallit, Automatic Sequences: theory, applications, generalizations. Cambridge (2003).  
  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. Fourier56 (2006) 2115–2130.  
  3. M. Barnsley, Fractals everywhere. Academic Press Professional, San Diego, USA (1998).  
  4. J. Berstel and D. Perrin, Theory of codes. Academic Press (1985).  
  5. J. Cassaigne, On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl.42 (2008) 701–715.  
  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.  
  7. C. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of Formal Languages. Springer (1997).  
  8. F.M. Dekking, Recurrent sets. Adv. Math.44 (1982) 78–104.  
  9. F.M. Dekking, Replicating superfigures and endomorphisms of free groups. J. Comb. Theor. Ser. A32 (1982) 315–320.  
  10. M.M. France and J. Shallit, Wire bending. J. Comb. Theor.50 (1989) 1–23.  
  11. F.R. Gantmacher, The theory of matrices. Chelsea Publishing Company, New York (1962).  
  12. L. Kari, G. Rozenberg and A. Salomaa, L Systems, in Handbook of Formal Languages. Springer (1997).  
  13. S. Kitaev, T. Mansour and P. Seebold, Generating the Peano curve and counting occurrences of some patterns. Automata, Languages and Combinatorics9 (2004) 439–455.  
  14. M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002).  
  15. M. Lothaire, Applied combinatorics on words. Cambridge University Press (2005).  
  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).  
  18. K. Saari, Private communication.  
  19. P. Séébold, Tag-systems for the Hilbert Curve. Discr. Math. Theoret. Comput. Sci.9 (2007) 213–226.  
  20. J. Shallit, A generalization of automatic sequences. Theoret. Comput. Sci.61 (1988) 1–16.  

NotesEmbed ?

top

You must be logged in to post comments.