AP05_5.vp 1 Introduction In recent years, the combinatorial properties of finite and infinite words have become significantly important in fields of physics, biology, mathematics and computer science. One of the first impulses for extensive research in this field was the discovery of quasi-crystals. Normal crystal structures show rotational and translation- al symmetry. In 1982, however, Dan Shechtman discovered an aperiodic structure (which was formed by rapidly-quenched aluminum alloys) that has a perfect long-range order, but no three-dimensional translational periodicity (see e.g. [1] or [2]). Since then many stable and unstable aperiodic structures have been discovered. They are now known as quasi-crystals. The problematics of aperiodic structures has been studied from various points of view and there are numerous relations with other applications (besides solid-state physics), such as pseudo-random number generators [3], pattern recognition and symbolic dynamical systems. Early results are reported in [4] or [5]. This paper is devoted to Sturmian words. Sturmian words are infinite words over a binary alphabet with exactly n � 1 fac- tors of length n for each n � 0. They represent the simplest family of quasi-crystals. The history of Sturmian words dates back to the astronomer J. Bernoulli III [6]. He considered the sequence � � � �( )n n� � � �1 1 2 1 2� � , where n � 1 and � is a positive irrational. Based on the continued fraction expan- sion of �, he gave (without proof) an explicit description of the terms of the sequence. There also exist some early works by Christoffel and Markoff. A. A. Markoff was the first to prove the validity of Ber- noulli’s description. He did that in his work [7], where he described the terms of the sequence � � � � � �( )n n� � �1 � � � , n � 1 (later known as a mechanical sequence). The first detailed investigation of Sturmian words is due to Hedlund and Morse [4], who studied such words from the point of view of symbolic dynamics and, in fact, introduced the term „Sturmian“; named after the mathematician Charles Francois Sturm. It appears that there are several equivalent ways of con- structing Sturmian words. We will describe some of them and show the relationship with other notions from the combina- torics on words such as palindromes and return words. Then we make some notes on an extension of Sturmian words using the cut-and-project scheme. The next section is devoted to the important question of the invariance of Sturmian words on a substitution. In the last section we present some open problems related to generalizations of Sturmian words. 2 Sturmian words An infinite one-sided word w w w w wn n N� ��( ) ,0 0 1 2 � is a sequence of letters from a finite set A which is called an alphabet. We use the notation N for the set of integers and N N0 0� { }. A finite word v v v vn� �0 1 1� is a finite string of letters from A and v n� is the length of v. The set of all finite words over the alphabet A is denoted by A*. A finite word u A * is a factor of w if there exist 0 � �k l such that u w wk l� � . The empty word is denoted by �. The set of fac- tors of w of length n is written Ln(w) and the set of all factors of w is denoted by L(w). The set L(w) is often called the language. An infinite word w is ultimately periodic if there exist a word u and a word v such that w uv� � where v� is the infinite concatenation of the word v. It is periodic if u is the empty word. If the infinite word w does not have any of the previous forms we say that it is aperiodic. We say that u is a prefix (resp. suffix) of v v v vn� �0 1 1� , v L wn� ( ), if there exists 0 1� � �l n such that u v vl� 0� (resp. u v v vl l n� � �1 1� ). The infinite word w, l � 0, is a suffix of w. An infinite word w is uniformly recurrent if for every inte- ger k there exists an integer l such that each word of L wk( ) occurs in every word of length l. The usual way of defining Sturmian words is via the complexity function. Let w be an infinite word and Cw be a mapping N N0 � , such that C nw( ) is the number of different factors of length n of w; i.e. C n L ww n( ) # ( )� . Cw is called the complexity and we say that the word w is Sturmian if C n nw( ) � � 1 for all n. Since Cw( )1 2� , Sturmian words are de- fined over a binary alphabet, say A � { , }0 1 . Clearly Cw( )0 1� for any w. There have been some attempts to extend Sturmian words to words over alphabets with more than two letters, for in- stance [8] or [9], but none of these constructions show such nice properties as Sturmian words. However, the approach of Arnoux and Rauzy presented in [8] resulted in another inter- esting family of words called Arnoux-Rauzy sequences. Another combinatorial definition of Sturmian words is based on the distribution of letters in the word. Let w be an in- finite word, u v L w, ( )� be two factors of the same length u v� and function � be defined �( , )u v u v� �0 0 , © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 19 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 5/2005 Various Properties of Sturmian Words P. Baláži This overview paper is devoted to Sturmian words. The first part summarizes different characterizations of Sturmian words. Besides the well known theorem of Hedlund and Morse it also includes recent results on the characterization of Sturmian words using return words or palindromes. The second part deals with substitution invariant Sturmian words, where we present our recent results. We generalize one-sided Sturmian words using the cut-and-project scheme and give a full characterization of substitution invariant Sturmian words. Keywords: Sturmian words, mechanical words, 2-interval exchange map, palindromes, return words, substitutions. where u 0 denotes the number of occurrences of 0 in u. We say that w is balanced if and only if �( , )u v � 1 for all u v L w, ( )� with u v� . Note that the structure of a balanced word over the alphabet A � { , }0 1 is formed, either by a block of 0’s be- tween two consecutive 1’s, or by a block of 1’s between two consecutive 0’s. It is easy to see that the length of the blocks of 0’s between two consecutive 1’s (resp. blocks of 1’s between two consecutive 0’s) differs at most by 1 in a balanced word. As we will see balanced words are equivalent to Sturmian words. In the literature one can find several constructions of binary words. We start with the construction presented by Hedlund and Morse in [4]. Let �, � be real numbers, where � �( , )0 1 and � �[ , )0 1 . Then s s n� � � �, , ( )� , s s n� � � �, , ( )� are sequences defined by, � �s n n n� � � � � �, ( ): ( )� � � � �1 , for n � 0, � � � �s n n n� � � � � �, ( ): ( )� � � � �1 , for n � 0. These words are usually referred to as mechanical words and � is called the slope and � the intercept. Mechani- cal words of s � �, resp. s � �, have a nice geometrical interpretation. Consider the integer lattice Z2, the straight line y x� �� �, x � 0, and two sequences of integer points �� �X n nn � �, � � and � �� �Y n nn � �, � � . The elements of Xn cover integer points of the lattice just below the line y x� �� � and the elements of Yn cover points just above the line. If s n� �, ( ) � 0 then the points Xn and Xn�1 lie on the hori- zontal line, and if s n� �, ( ) � 1 then they lie on the diagonal line. The same holds for s n� �, ( ) and Yn. In fact, the sequences s � �, , s � �, are the coding of a discretization of a straight line. Note that if � is irrational then s � �, and s � �, differ by at most for two values of n. Clearly, this can happen only if n� �� is an integer for some n. If we consider � � 0 and n � 0, then s �, ( )0 0 0� and s �, ( )0 0 1� and we obtain the important special case of mechanical words s c� �,0 0� , s c� �,0 1� ; n � 0. The infinite word c� is called the characteristic sequence of �. Crisp et al. study, in their work [10], another way of constructing characteristic sequences. Consider again the in- teger lattice Z2 and the straight line y x� � , where � is a positive irrational and x � 0. We label the intersections of the line y x� � with verticals of the grid using 0, and we label by 1 the intersections of y x� � with horizontals. The sequence of labels forms the so called cutting sequence and is denoted by S�. It can be shown that c� �� S if and only if � � �� �( )1 (see e.g. [10]). One can often encounter the term r-interval exchange map in connection with infinite words. Properties of words generated by the r-interval exchange map (called the coding of the r-interval exchange map) are studied from different as- pects in [11], [12] or [13]. Let us closely mention the 2-interval exchange map and its reference to Sturmian words. Let � �( , )0 1 be an irrational number and x �[ , )0 1 . Let I1 0 1� �[ , )� , I2 1 1� �[ , )� be the decompositions of the inter- val [ , )0 1 . The map T�, given by the rule T x x x x x� � �� � � � ( ) , [ , , , [ , , � � � � � � � � � � � for for 0 1 1 1 1 is called the 2-interval exchange map. It can be written in a more complex way �T x x x x� � � �( ) { }� � � � � � , � �x [ , )0 1 . For the n-th iteration of the 2-interval exchange map T� we obtain T x T x n xn n� � � ( )( ) ( ) { }� � � . Since � is irrational, T� does not have any fixed point. It is not difficult to check that � �( ) ( ) [ , ( )n x n x T xn� � � � � � �1 0 1� � ��� which implies that s n T T n n� � � � � �� � � � , ( ) ( )( ) ( ) [ , , ( ) [ , . � � � � � � � 0 0 1 1 1 1 if if� Let us show the most famous example of Sturmian words, the Fibonacci word. Example 2.1: Let be the map given by : ,0 01 1 0� � with the property ( ) ( ) ( )uv u v� for any finite words u, v over the alphabet {0, 1}. Define the n-th finite Fibonacci word fn in the following way: f0 0� and for all n � 0, f fn n� �1 ( ). Since f0 0� and (0) starts with 0, then fn is the prefix of f n �1 for each n � 0. The Fibonacci word is defined as the limit of the sequence of words fn and thus lim n nf �� � 010010100100101001010010010� Note that the further applications of the map fn do not change the Fibonacci word. Observe that the length f n is the n-th element of the Fibonacci sequence Fn, (F F Fn n n� �� �1 2; F0 1� , F1 2� ), for all n � 0. It can be shown that the complexity of the Fibonacci word equals to n � 1, thus the word is Sturmian. The Fibonacci word also coincides with the mechanical word with slope 1 2 and zero intercept, where � �1 2 1 5( ) is the golden mean. We finalize this part with a theorem by Hedlund and Morse [4] which states that Sturmian, balanced and mechani- cal words are indeed equivalent. Theorem 2.1: (Hedlund, Morse). Let w be an infinite word over the alphabet A � { , }0 1 . The following conditions are equivalent: 1. w is Sturmian; 2. w is balanced and aperiodic; 3. there exist an irrational �, � �( , )0 1 and a real � �[ , )0 1 such that w s� � �, or w s� � �, , for all n � 0. There exist several proofs of the theorem. The origi- nal proof [4] is of combinatorial nature, while the other by Lunnon and Pleasants [14] is based on geometrical considerations. 2.1 Other characteristics of Sturmian words We have mentioned several equivalent definitions of Sturmian words as those with minimal complexity, balanced aperiodic sequences and mechanical words. In the past few years, there have been successful attempts to find a new characterization of Sturmian words. The first one, which we will describe uses return words, while the second uses palindromes. Let w be a one-sided infinite word and u a factor of w. We say that a finite word v is the return word over u if vu is a factor of w, u is a prefix of vu and there are exactly 2 occurrences of u 20 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 45 No. 5/2005 Czech Technical University in Prague in vu. In other words, the return word v over u starts with the occurrence of u and ends just before the next occurrence of u. Example 2.2: Let 0100101001001010010100100101… be the Fibonacci word. The set of return words over 0101 con- tains words 01010010 and 01010. For clarity, here is the Fibonacci word with indicated return words over 0101 : 0100101001001010010100100101… Vuillon [15] observed that the number of return words in- dicates whether a word is Sturmian or not. He showed the following theorem. Theorem 2.2: A binary infinite word w is Sturmian if and only if the set of return words over u has exactly two elements for every non empty word u. Note that the proof of the necessary condition includes a nice application of Rauzy graphs, which are often used for in- vestigation of growth of the complexity in infinite words [8]. Let us focus on palindromes. A palindrome is a finite word that reads the same backwards as forwards. For instance, these are the first palindromes of the Fibonacci word: �, 0, 1, 00, 010, 101, 1001, 00100, 01010,… In [16], Droubay and Pirillo showed the characterization of Sturmian words by observing the number of palindromes of even and odd length. Theorem 2.3: An infinite word is Sturmian if and only if, for each nonnegative integer n, there is exactly one palindrome of length n, if n is even, and there are exactly two palindromes of length n, if n is odd. The mapping that assigns to an integer n the number of palindromes of length n in a word is called the palindromic complexity. In the context of palindromes and Sturmian words, let us draw attention to paper [17]. The authors proved that the number of palindromes in a word n of length n is less or is equal to n � 1. Note that this holds for any kind of words (not necessary Sturmian) over arbitrary alphabets. However in the case of Sturmian words it was shown in [17] that the number of all palindromes in a factor of length n is equal to n � 1. The reader may like to try finding words of length n over a 2-letter alphabet with the number of palindromes less than n � 1; this is not as trivial as it may appear to be. 2.2 Bidirectional Sturmian words In the previous sections we have outlined several charac- teristics of Sturmian words. However we have limited our- selves, from the very first definitions, to one-sided infinite words. This restriction is typical for a large number of papers, in spite the fact that the definitions of notions like balanced words, mechanical words etc. can be extended, very naturally, to both sides. The question is, whether the above listed theo- rems still hold for bidirectional infinite words. Let us show a way of generating bidirectional infinite words from which it will be clear that such a generalization is possible. Consider �, � fixed positive irrational numbers, � �� � , � �[ , )0 1 and the set � � � � � � � � �, ( , ] { | , , }đ� � � � � � � �1 1m n m n m n Z . It follows that m has to satisfy � � � �� � � � �n m n , hence �m n� �� � , i.e. any element of � � � � �, ( , ]� 1 has the form �� � �� �n n , for some n Z� . Using this fact we can write �� � � � � � � ��, ( , ] { : }� � � � � �1 x n n n Zn , thus the elements of � � � � �, ( , ]� 1 form an increasing se- quence ( )xn n Z� . We can compute the lengths between two consecutive points of ( )xn n Z� as � �x x n nn n� � � � � � � �1 1( )� � � � �. The term � �( )n n� � � �1 � � � � takes only two values 0 and 1 for each n Z� . Thus there are only two distances be- tween neighbors in � � � � �, ( , ]� 1 , namely 1 � � and �. Let us define a sequence ( )wn n Z� of 0’s and 1’s by w x x x xn n n n n � � � � � � � � � � � 0 1 1 1 1 if if � � , . The sequence ( )wn n Z� is a pointed bidirectional infinite word ( ) | ,w w w w w wn n Z� � ��� �2 1 0 1 2 where | denotes a delimiter. Since the distances between the consecutive points in � � � � �, ( , ]� 1 are ordered as the me- chanical word s � �, then w (i.e. the infinite word to the right from the delimiter) is the Sturmian word. From the construc- tion it is clear that the language of w w w0 1 2 � is the same as the language of � w w� �2 1. The complexity function Cw has been defined for the right sided infinite words, however the definition can be naturally extended to left sided infi- nite words, say � � � �w w w� 2 1 as : C n L ww n� � �( ) # ( ). Since C n L w L w C nw n n w� � � � �( ) # ( ) # ( ) ( ) the word � w w� �2 1 is also Sturmian. Since an arbitrary shift of the whole interval ( , ]� �� 1 (i.e. we are keeping the unit length of the interval) does not change the set � � � � �, ( , ]� 1 , it just shifts the position of the delimiter, we can conclude that the word ( )wn n Z� is the pointed bidirectional infinite Sturmian word. From now on we will consider only bidirectional infinite words. Note that the set � � � � �, ( , ]� 1 is called the cut-and-project set and the interval ( , ]� �� 1 is an acceptance window. There are a couple of papers dealing with cut-and-project sets. In [18] it is shown that a cut-and-project set has either two or three distances between adjacent points; two distances correspond to the case of the unit length of the acceptance window and the distances form a Sturmian word. On the other hand, the words corresponding to the cut-and-project sets with three distances are exactly those which arise from the coding of the 3-interval exchange map, and vice versa. In [19], [20] the authors study substitution properties and the substitutivity of cut-and-project sets. 3 Sturmian words and substitutions Let us take a look at Sturmian words from a different point of view. One can see in Example 2.1 that there exist Sturmian words which are generated by certain maps (here we will call them substitutions). In fact, the mentioned Fibonacci word is a fixed point of the map . The question is whether this is a general property of all Sturmian words, or whether there ex- ists a class of Sturmian words invariant under substitutions. Let us now state basic definitions and then we give an over- view of the most interesting results. A morphism is a map of A* into itself satisfying ( ) ( ) ( )uv u v� for each u v A, *� . The morphism is called non-erasing if ( )ai is not an empty word for any a Ai � . A non-erasing morphism is called a substitution. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 21 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 5/2005 The action of can be extended to bidirectional infinite words ( ) |w w w w w wn n Z� � ��� �2 1 0 1 2 by � � ( ) ( )| ( ) ( ) ( )w w w w w� �2 1 0 1 2 We say that the word ( )wn n Z� is invariant under the substitu- tion (or is a fixed point of ) if � � � � ( ) ( )| ( ) ( ) ( ) |w w w w w w w w w w� � � ��2 1 0 1 2 2 1 0 1 2 Suppose that we have a substitution and there exist let- ters a a Ai j, � , such that ( )a uai i� and ( )a a vj j� for some non-empty words u v A, *� . Then by repeated application of on the pair a ai j| of letters separated by the delimiter | we obtain words ( ) ( )( )| ( )n i n ja a , n N� of increasing length. Clearly ( ) ( ) ( ) ( )( )| ( ) ( )| ( )n i n j n n i n j na a u a a v� � �1 1 , for certain words u v An n, *� . The limit of ( ) ( )( )| ( )n i n ja a for n � � is an infinite bidirectional word ( )wn n Z� and we say that generates the word ( )wn n Z� . Let us define a weaker notion of a substitutive word. We say that ( ) |w w w w w wn n Z� � ��� �2 1 0 1 2 is a substi- tutive word, if there exists a substitution on an alphabet B with a fixed point ( ) |v v v v v vn n Z� � ��� �2 1 0 1 2 and a map � : B A� such that w vn n� �( ), for each n Z� . Note that all fixed points of a substitution are substitutive. The opposite is not true. Let A a ak� { , , }1 � be an alphabet. To a substitution one may assign a substitution matrix A � �N k k in the following way: A ij j ia a: ( )� number of letters in the word . The problem of invariance under a substitution (or the weaker notion of substitutivity) has motivated many papers. There are some partial results, where authors consider only one sided Sturmian words or characterize substitution invari- ant bidirectional Sturmian words depending on the slope � if the intercept � � 0. Crisp et al. [10] carried on the work of Brown [21] and studied substitution invariant cutting sequences. They proved that the cutting sequence S� (resp. the mechanical sequence c� is substitution invariant if and only if the continuous frac- tion expansion of � (resp. �) has a certain form. The author in [22] used some of their results and simplified their condition on the invariance of the characteristic sequence c� under a substitution. He showed that c�, � �( , )0 1 , is invariant under a substitution if and only if � is a quadratic irrational with conjugate � � ( , )0 1 . Such � is called a Sturm number. This result was shown independently by Allauzen, [23]. Parvaix [24] proved that bidirectional non-pointed Sturmian words with � � 0 are invariant under � substitution if and only if � is a Sturm number and the intercept � belongs to the quadratic field Q a a b a,b Q( ) { | }� � �� . A complete characterization of infinite one-sided substitu- tion invariant Sturmian words was done by Yasutomi [25]. Berthé et al. [26] studied infinite words which arise from the coding of the 2-interval exchange map and gave an alterna- tive proof of Yasutomi’s result using Rauzy fractals associated with invertible primitive substitutions. The authors also de- fined for every fixed Sturm number � a matrix M� � �Q 2 2 that is called the generating matrix of � and is closely related to the smallest solution of a Pell equation. They showed that a Sturmian sequence s � �, (� Sturm number, � �[ , )0 1 ) is a fixed point of a substitution with substitution matrix A if and only if A has the form M� l , for some l � 1. We complete this overview by giving a few notes on paper [27]. The authors have completely solved the question of the substitution invariance of pointed bidirectional Sturmian words. The main theorem shown in the paper is the following. Theorem 3.1: Let � be an irrational number, � �( , )0 1 , � �[ , )0 1 . The pointed bidirectional Sturmian word with slope � and intercept � is invariant under a non-trivial substitution if and only if the follow- ing three conditions are satisfied: 1. � is a Sturm number, 2. � ��Q( ), 3. � � � � � �� � �1 or 1 � � � � � �� � � , where �� is the image of � under the Galois automorphism of the quadratic field Q( )� . Note that this result is analogous to those derived in [25] and [26] for the one-sided case. The proof presented in [27] is constructive based on the cut-and-project scheme that was sketched in the para- graph devoted to bidirectional words. This approach has not been used yet in the study of substitution invariant Sturmian words. It turns out to be a good choice because the proof is simple. One of the advantages of the cut-and-project scheme is that the more difficult parts of the proof can be illus- trated on vivid examples, which makes the whole paper more comprehensible. We believe that methods similar to those in [27] can solve the question of the substitution invariance of words over a 3 letter alphabet, which arise from the coding of the 3-interval exchange map. 4 Open problems We have summarized several interesting properties of Sturmian words and here we would like to highlight how the results about Sturmian words can help in further advances in the field of aperiodic words. As Sturmian words are the sim- plest aperiodic structures, the question of generalisation of results obtained for Sturmian words is particularly interest- ing. The direct generalization of Sturmian words are infinite words which arise from the coding of a 3-interval (resp. r-in- terval) exchange map. We believe that results and techniques used in the study of Sturmian words can be applied with success to open problems connected with words coding a 3-in- terval exchange map. Below you may find a list of the most interesting issues. 1. A necessary and sufficient condition on the substitution invariance of the words coding a 3-interval exchange map is still not known. The problem of finding a similar condition to that of Theorem 3.1 is still open, but the tech- niques used in [27] may bring some answers. 2. Giving a description of substitution matrices of substi- tutions which generate the words coding a 3-interval ex- change map is a problem closely related to the previous one. The question of finding generating matrices of such 22 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 45 No. 5/2005 Czech Technical University in Prague substitutions seems to be very challenging. This issue was solved in [26] for Sturmian words. 3. Although a description of palindromes in the words cod- ing a 3-interval exchange map is already known [17], we believe that the use of the cut-and-project scheme can give an alternative proof of this result. Nevertheless the palindromic complexity is described only for a 2-interval exchange map (see theorem 2.3) and a 3-interval ex- change map [28], but we believe that a general description can be obtained by considerations based on the cut-and- -project scheme. 5 Acknowledgment The author acknowledges partial funding from the Czech Science Foundation GA, ČR 201/05/0169. The author is also very obliged to Edita Pelantová and Zuzana Masáková for their help and discussions on the paper. References [1] Shechtman, D. et al.: “Metallic Phase with Long-Range Orientational Order and No Translational Symmetry.” Phys. Rev. Lett. Vol. 53 (1984), p. 1951–1953. [2] Bombieri, E., Taylor, J. E.: “Which Distributions of Mat- ter Diffract? An Initial Investigation.” J. Phys. Colloque C3, Vol. 14 (1986), p. 19–28. [3] Guimond, L. S., Patera, J.: “Proving the Deterministic Period Breaking of Linear Congruential Generators Us- ing Two Tile Quasicrystals.” Math. of Comput., Vol. 71 (2002), p. 319–332. [4] Hedlund, G., Morse, M.: “Symbolic Dynamics II: Sturm- ian Sequences.” Amer. J. Math., Vol. 61 (1940), p. 1–42. [5] Venkov, B. A.: Elementary Number Theory, Groningen: Wolters-Noordhoff, 1970. [6] Bernoulli, J.: “Sur une nouvelle espece de calcul.” Receuil pour les astronomes, Vols. 1, 2, Berlin, 1772. [7] Markoff, A. A.: “Sur une question de Jean Bernoulli.” Math. Ann., Vol. 19 (1882), p. 27–36. [8] Arnoux, P., Rauzy, G.: “Représentation géométrique de suites de complexité 2n+1.” Bull. Soc. Mat. France, Vol. 119 (1991), p. 199–215. [9] Coven, E. M.: “Sequences with Minimal Block Growth II.” Math. Sys. Theory, Vol. 8 (1973), p. 376–382. [10] Crips, D. et al.: “Substitution Invariant Cutting Se- quences.” J. de Th. des Nom. de Bordeaux, Vol. 5 (1993), p. 123–137. [11] Adamczewski, B.: “Codages de rotations et phénomPnes d’autosimilarité.” J. de Th. des Nom. de Bordeaux, Vol. 14 (2002), p. 351–386. [12] Alessandri, B., Berthé, V.: “Three Distance Theorems and Combinatorics on Words.” L’Enseignement Mat., Vol. 44 (1998), p. 103–132. [13] Ferenczi, S. et al.: “Structure of Three Interval Exchange Transformations I: an Arithmetic Study Ann. Inst. Fou- rier, Vol. 51 (2001), p. 861–901. [14] Lunnon, W. F., Pleasants, P. A. B.: “Characterization of Two-Distance Sequences.” J. Austral. Math. Soc., Vol. 53 (1992), p. 198–218. [15] Vuillon, L.: “A Characterization of Sturmian Words by Return Words.” European J. Combin., Vol. 22 (2001), p. 263–275. [16] Droubay, X., Pirillo, G.: “Palindromes and Sturmian Words.” Theoret. Comput. Sci., Vol. 223 (1999), p. 73–85. [17] Droubay, X. et al.: “Episturmian Words and some Con- structions of de Luca and Rauzy.” Theoret. Comput. Sci., Vol. 225 (2001), p. 539–553. [18] Guimond, L. S. et al.: “Combinatorial Properties of Infi- nite Words Associated with Cut-and-Project Sequences.” J. de Th. des Nom. de Bordeaux, Vol. 15 (2003), p. 697–725. [19] Baláži, P.: “Infinite Words Coding 3-Interval Ex- change.” Diploma work, 2003. [20] Masáková, Z. et al.: “Substitution Rules for Aperiodic Se- quences of Cut and Project Type.” J. of Phys. A: Math. Gen., Vol. 33 (2000), p. 8867–8886. [21] Brown, T. C.: “A Characterization of the Quadratic Irra- tionals.” Canad. Math. Bull., Vol. 34 (1991), p. 36–41. [22] Baláži, P.: “Jednoduchá charakteristika Sturmových čí- siel.” Proc. of 9th Math. Conf. of Tech. Uni., 2001, p. 5–15. [23] Allauzen, C.: “Une charactérisation simple des nombres de Sturm.” J. de Th. des Nom. de Bordeaux, Vol. 10 (1998), p. 237–241. [24] Parvaix, B.: “Substitution Invariant Sturmian Bise- quences.” J. de Th. des Nom. de Bordeaux, Vol. 11 (1999), p. 201–210. [25] Yasutomi, S.: “On Sturmian Sequences which are Invari- ant under some Substitutions.” Number Theory and its Ap- plications, Vol. 2 (1999), p. 347–373. [26] Berthé, V. et al.: Invertible Substitutions and Sturmian Words: An Application Of Rauzy Fractals, preprint 2003. [27] Baláži, P. et al.: “Complete Characterization of Sub- stitution Invariant Sturmian Sequences.” To appear in Integers, 2005. [28] Damanik D., Zamboni L. Q: Arnoux-Rauzy Subshifts: Lin- ear Recurrences, Powers, and Palindromes, arXiv: math. CO/0208137v1. [29] Berstel, J.: “Recent Results on Extensions of Sturmian Words.” Internat. J. Algebra Comput., Vol. 12 (2002), p. 371–385. Ing. Peter Baláži e-mail: balazi@km1.fjfi.cvut.cz Department of Mathematics Czech Technical University in Prague Faculty of Nuclear Sciences and Physical Engineering Trojanova 13 120 00 Prague 2, Czech Republic © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 23 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 5/2005