Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-12T21:01:45.150Z Has data issue: false hasContentIssue false
  • English
  • Français

Locally catenative sequencesand Turtle graphics

Published online by Cambridge University Press:  22 August 2011

Juhani Karhumäki and
Svetlana Puzynina
Juhani Karhumäki
Affiliation:
University of Turku, Department of Mathematics, 20014 Turku, Finland Turku Centre for Computer Science, 20014 Turku, Finland. karhumak@utu.fi
Svetlana Puzynina
Affiliation:
University of Turku, Department of Mathematics, 20014 Turku, Finland Turku Centre for Computer Science, 20014 Turku, Finland. karhumak@utu.fiSobolev Institute of Mathematics, Novosibirsk 630090, Russia. svepuz@utu.fi

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Motivated by striking properties of the well known Fibonacci wordwe consider pictures which are defined by this word and itsvariants via so-called turtle graphics. Such a picture can bebounded or unbounded. We characterize when the picture defined bynot only the Fibonacci recurrence, but also by a generalrecurrence formula, is bounded, the characterization beingcomputable.

Keywords

Combinatorics on wordslocally catenative sequencesturtle graphicsFibonacci word

Information

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 45 , Issue 3 , July 2011, pp. 311 - 330
Copyright
© EDP Sciences, 2011

References

J.-P. Allouche and J. Shallit, Automatic Sequences: theory, applications, generalizations. Cambridge (2003).
Allouche, G., Allouche, J.-P. and Shallit, J., Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde. Ann. Inst. Fourier 56 (2006) 2115–2130. CrossRef
M. Barnsley, Fractals everywhere. Academic Press Professional, San Diego, USA (1998).
J. Berstel and D. Perrin, Theory of codes. Academic Press (1985).
Cassaigne, J., On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701–715. CrossRef
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).
Dekking, F.M., Recurrent sets. Adv. Math. 44 (1982) 78–104. CrossRef
Dekking, F.M., Replicating superfigures and endomorphisms of free groups. J. Comb. Theor. Ser. A 32 (1982) 315–320. CrossRef
France, M.M. and Shallit, J., Wire bending. J. Comb. Theor. 50 (1989) 1–23. CrossRef
F.R. Gantmacher, The theory of matrices. Chelsea Publishing Company, New York (1962).
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 Combinatorics 9 (2004) 439–455.
M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002).
M. Lothaire, Applied combinatorics on words. Cambridge University Press (2005).
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.
Séébold, P., Tag-systems for the Hilbert Curve. Discr. Math. Theoret. Comput. Sci. 9 (2007) 213–226.
Shallit, J., A generalization of automatic sequences. Theoret. Comput. Sci. 61 (1988) 1–16. CrossRef