Displaying similar documents to “Locally catenative sequences and Turtle graphics”

Locally catenative sequences and Turtle graphics

Juhani Karhumäki, Svetlana Puzynina (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Motivated by striking properties of the well known Fibonacci word we consider pictures which are defined by this word and its variants 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.

Return words in Sturmian and episturmian words

Jacques Justin, Laurent Vuillon (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Considering each occurrence of a word in a recurrent infinite word, we define the set of return words of to be the set of all distinct words beginning with an occurrence of and ending exactly just before the next occurrence of in the infinite word. We give a simpler proof of the recent result (of the second author) that an infinite word is Sturmian if and only if each of its factors has exactly two return words in it. Then, considering episturmian infinite words, which are a natural generalization...

Fewest repetitions in infinite binary words

Golnaz Badkobeh, Maxime Crochemore (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

A square is the concatenation of a nonempty word with itself. A word has period if its letters at distance match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property,...