<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
Morse and Hedlund's Skew Sturmian Words Revisited
Giuseppe Pirillo1,2
1IASI, CNR, Viale Morgagni 67/A, 50134 Firenze, Italy
2Université de Marne-la-Vallée 5, boulevard Descartes Champs sur Marne, 77454 Marne-la- Vallée, Cedex 2, France
Annals of Combinatorics 12 (1) p.115-121 March, 2008
AMS Subject Classification:94A45
For any infinite word r over A={a, b} we associate two infinite words min(r), max(r) such that any prefix of min(r) (max(r), respectively) is the lexicographically smallest (greatest, respectively) among the factors of r of the same length. We prove that (min(r); max(r)) = (as; bs) for some infinite word s if and only if r is a proper Sturmian word or an ultimately periodic word of a particular form. This result is based on a lemma concerning sequences of infinite words.
Keywords: words, lexicographic order, Sturmian words, episturmian words


1. J.-P. Borel and F. Laubie, Quelques mots sur la droite projective réelle, J. Théor. Nombres Bordeaux 5 (1) (1993) 23-51.

2. A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci. 183 (1) (1997) 45-82.

3. X. Droubay, J. Justin, and G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci. 255 (1-2) (2001) 539-553.

4. S. Gan, Sturmian sequences and the lexicographic world, Proc. Amer. Math. Soc. 129 (5) (2001) 1445-1451.

5. A. Glen, A characterization of fine words over a finite alphabet, Theoret. Comput. Sci., to appear.

6. A. Glen, J. Justin, and G. Pirillo, Characterizations of finite and infinite episturmian words via lexicographic orderings, Europ. J. Combin. 29 (1) (2008) 45-58.

7. O. Jenkinson and L. Zamboni, Characterisations of balanced words via orderings, Theoret. Comput. Sci. 310 (1-3) (2004) 247-271.

8. J. Justin and G. Pirillo, On a characteristic property of Arnoux-Rauzy sequences, Theor. Inform. Appl. 36 (4) (2002) 385-388.

9. M. Lothaire, Combinatorics on Words, Encyclopedia Math. Appl. Vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983.

10. M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia Math. Appl. Vol. 90, Cambridge University Press, Cambridge, 2002.

11. M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940) 1-42.

12. G. Pirillo, Inequalities characterizing standard Sturmian words, Pure Math. Appl. 14 (1-2) (2003) 141-144.

13. G. Pirillo, Inequalities characterizing standard Sturmian and episturmian words, Theoret. Comput. Sci. 341 (1-3) (2005) 276-292.

14. G. Pirillo, Characterization of (proper) standard Sturmian words, unpublished manuscript.