Languages obtained from infinite words
Languages of finite words occurring infinitely many times in an infinite word
We give necessary and sufficient conditions for a language to be the language of finite words that occur infinitely many times in an infinite word.
Languages of finite words occurring infinitely many times in an infinite word
We give necessary and sufficient conditions for a language to be the language of finite words that occur infinitely many times in an infinite word.
Languages under substitutions and balanced words
This paper consists of three parts. In the first part we prove a general theorem on the image of a language under a substitution, in the second we apply this to the special case when is the language of balanced words and in the third part we deal with recurrent Z-words of minimal block growth.
Lattice structures from planar graphs.
Least periods of factors of infinite words
We show that any positive integer is the least period of a factor of the Thue-Morse word. We also characterize the set of least periods of factors of a sturmian word. In particular, the corresponding set for the Fibonacci word is the set of Fibonacci numbers. As a by-product of our results, we give several new proofs and tightenings of well-known properties of sturmian words.
Least Periods of Factors of Infinite Words
We show that any positive integer is the least period of a factor of the Thue-Morse word. We also characterize the set of least periods of factors of a Sturmian word. In particular, the corresponding set for the Fibonacci word is the set of Fibonacci numbers. As a by-product of our results, we give several new proofs and tightenings of well-known properties of Sturmian words.
Les hiérarchies de parties et leur demi-treillis
Level planar embedding in linear time.
Level set structure of an integrable cellular automaton.
Linear size test sets for certain commutative languages
We prove that for each positive integer the finite commutative language possesses a test set of size at most Moreover, it is shown that each test set for has at least elements. The result is then generalized to commutative languages containing a word such that (i) and (ii) each symbol occurs at least twice in if it occurs at least twice in some word of : each such possesses a test set of size , where . The considerations rest on the analysis of some basic types of word equations....
Linear size test sets for certain commutative languages
We prove that for each positive integer n, the finite commutative language En = c(a1a2...an) possesses a test set of size at most 5n. Moreover, it is shown that each test set for En has at least n-1 elements. The result is then generalized to commutative languages L containing a word w such that (i) alph(w) = alph}(L); and (ii) each symbol a ∈ alph}(L) occurs at least twice in w if it occurs at least twice in some word of L: each such L possesses a test set of size 11n, where n = Card(alph(L))....
Linear time recognition of -indifference graphs.
Listing all plane graphs.
Locally catenative sequences and Turtle graphics
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.
Locally catenative sequences and Turtle graphics
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.
Logarithmic frequency in morphic sequences
We study the logarithmic frequency of letters and words in morphic sequences and show that this frequency must always exist, answering a question of Allouche and Shallit.
Logic and -recognizable sets of integers.
Look and Say Fibonacci
The (Look and Say) derivative of a word is obtained by writing the number of consecutive equal letters when the word is spelled from left to right. For example, (two , one , two ). We start the study of the behaviour of binary words generated by morphisms under the operator, focusing in particular on the Fibonacci word.
Look and Say Fibonacci
The LS (Look and Say) derivative of a word is obtained by writing the number of consecutive equal letters when the word is spelled from left to right. For example, LS( 1 1 2 3 3) = 2 1 1 2 2 3 (two 1, one 2, two 3). We start the study of the behaviour of binary words generated by morphisms under the LS operator, focusing in particular on the Fibonacci word.