Locally catenative sequences and Turtle graphics

Juhani Karhumäki; Svetlana Puzynina

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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 - Informatique Théorique et Applications 45.3 (2011): 311-330. <http://eudml.org/doc/272996>.

@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 - Informatique Théorique et Applications},
keywords = {combinatorics on words; locally catenative sequences; turtle graphics; Fibonacci word},
language = {eng},
number = {3},
pages = {311-330},
publisher = {EDP-Sciences},
title = {Locally catenative sequences and Turtle graphics},
url = {http://eudml.org/doc/272996},
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 - Informatique Théorique et Applications
PY - 2011
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
UR - http://eudml.org/doc/272996
ER -

References

top
  1. [1] J.-P. Allouche and J. Shallit, Automatic Sequences: theory, applications, generalizations. Cambridge (2003). Zbl1086.11015MR1997038
  2. [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. Zbl1147.11015MR2290776
  3. [3] M. Barnsley, Fractals everywhere. Academic Press Professional, San Diego, USA (1998). Zbl0784.58002MR977274
  4. [4] J. Berstel and D. Perrin, Theory of codes. Academic Press (1985). Zbl0587.68066MR797069
  5. [5] J. Cassaigne, On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701–715. Zbl1155.68062MR2458702
  6. [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. Zbl0766.68072MR1076837
  7. [7] C. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of Formal Languages. Springer (1997). Zbl0964.68119MR1469998
  8. [8] F.M. Dekking, Recurrent sets. Adv. Math.44 (1982) 78–104. Zbl0495.51017MR654549
  9. [9] F.M. Dekking, Replicating superfigures and endomorphisms of free groups. J. Comb. Theor. Ser. A32 (1982) 315–320. Zbl0492.05019MR657046
  10. [10] M.M. France and J. Shallit, Wire bending. J. Comb. Theor.50 (1989) 1–23. Zbl0663.10056MR978063
  11. [11] F.R. Gantmacher, The theory of matrices. Chelsea Publishing Company, New York (1962). Zbl0927.15001
  12. [12] L. Kari, G. Rozenberg and A. Salomaa, L Systems, in Handbook of Formal Languages. Springer (1997). Zbl0866.68057MR1469997
  13. [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. Zbl1083.68092MR2198708
  14. [14] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002). Zbl1221.68183MR1905123
  15. [15] M. Lothaire, Applied combinatorics on words. Cambridge University Press (2005). Zbl1133.68067MR2165687
  16. [16] S. Papert, Mindstorms: children, computers, and powerful ideas. Basic Books, New York (1980). 
  17. [17] P. Prusinkiewicz and A. Lindermayer, The algorithmoic beauty of plants. Springer-Verlag, New York (1990). Zbl0859.92003MR1067146
  18. [18] K. Saari, Private communication. 
  19. [19] P. Séébold, Tag-systems for the Hilbert Curve. Discr. Math. Theoret. Comput. Sci.9 (2007) 213–226. Zbl1152.68491MR2306529
  20. [20] J. Shallit, A generalization of automatic sequences. Theoret. Comput. Sci.61 (1988) 1–16. Zbl0662.68052MR974766

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.