Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-24T02:57:14.503Z 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. [email protected]
Svetlana Puzynina
Affiliation:
University of Turku, Department of Mathematics, 20014 Turku, Finland Turku Centre for Computer Science, 20014 Turku, Finland. [email protected] Sobolev Institute of Mathematics, Novosibirsk 630090, Russia. [email protected]
Get access

Abstract

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
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 45 , Issue 3 , July 2011 , pp. 311 - 330
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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