Frequencies of factors in Arnoux-Rauzy sequences
The necessary and sufficient conditions are extracted for periodicity of bi-ideals. They cover infinitely and finitely generated bi-ideals.
We extend the DSV method of computing the growth series of an unambiguous context-free language to the larger class of indexed languages. We illustrate the technique with numerous examples.
Parikh matrices have become a useful tool for investigation of subword structure of words. Several generalizations of this concept have been considered. Based on the concept of formal power series, we describe a general framework covering most of these generalizations. In addition, we provide a new characterization of binary amiable words – words having a common Parikh matrix.
Expansions in noninteger bases often appear in number theory and probability theory, and they are closely connected to ergodic theory, measure theory and topology. For two-letter alphabets the golden ratio plays a special role: in smaller bases only trivial expansions are unique, whereas in greater bases there exist nontrivial unique expansions. In this paper we determine the corresponding critical bases for all three-letter alphabets and we establish the fractal nature of these bases in dependence...
We prove that the generalized Thue-Morse word defined for and as , where denotes the sum of digits in the base- representation of the integer , has its language closed under all elements of a group isomorphic to the dihedral group of order consisting of morphisms and antimorphisms. Considering antimorphisms , we show that is saturated by -palindromes up to the highest possible level. Using the generalisation of palindromic richness recently introduced by the author and E. Pelantová,...
Let be the Thue-Morse sequence, i.e., the sequence defined by the recurrence equations:We consider , the double sequence of Hankel determinants (modulo 2) associated with the Thue-Morse sequence. Together with three other sequences, it obeys a set of sixteen recurrence equations. It is shown to be automatic. Applications are given, namely to combinatorial properties of the Thue-Morse sequence and to the existence of certain Padé approximants of the power series .
Let be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to is also in . Extending the classical Morse-Hedlund theorem, we show that either contains at least words of length for every or, for some , it contains at most words of length for every . More importantly, we prove the following quantitative extension of this result: if has words of length then, for every , it contains at most words of length...
Let P be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to P is also in P. Extending the classical Morse-Hedlund theorem, we show that either P contains at least n+1 words of length n for every n or, for some N, it contains at most N words of length n for every n. More importantly, we prove the following quantitative extension of this result: if P has m ≤ n words of length n then, for every k ≥ n + m, it contains at most...
We present two methods based on decimation for computing finite billiard words on any finite alphabet. The first method computes finite billiard words by iteration of some transformation on words. The number of iterations is explicitly bounded. The second one gives a direct formula for the billiard words. Some results remain true for infinite standard Sturmian words, but cannot be used for computation as they only are limit results.