Some Characterizations of Sturmian Words in Terms of the Lexicographic Order

• Autorzy: Bucci, M. , De Luca, A. , Zamboni, L. Q.
• Języki publikacji: EN

Abstrakty

EN

In this paper we present three new characterizations of Sturmian words based on the lexicographic ordering of their factors.

Słowa kluczowe

EN

Sturmian words; lexicographic order

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 25-33
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Bucci, M.

autor

De Luca, A.

autor

Zamboni, L. Q.

• Department of Mathematics, University of Turku, FI-20014 Turku, Finland,

Bibliografia

• [1] Arnoux, P., Rauzy, G.: Représentation géométrique de suites de complexité 2n+1, Bull. Soc. Math. France, 119, 1991, 199-215.
• [2] Berstel, J., Lauve, A., Reutenauer, C., Saliola, F.: Combinatorics on Words: Christoffel Words and Repetition in Words, vol. 27 of CRM monograph series, American Mathematical Society, 2008.
• [3] Berstel, J., Séébold, P.: Sturmian Words, in: Algebraic Combinatorics on Words (M. Lothaire, Ed.), Cambridge University Press, Cambridge UK, 2002, Chapter 2.
• [4] Cao, W.-T., Wen, Z.-Y.: Some properties of the factors of Sturmian sequences, Theor. Comput. Sci., 304, 2003, 365-385.
• [5] Jenkinson, O., Zamboni, L. Q.: Characterisations of balanced words via orderings, Theor. Comput. Sci., 310, 2004, 247-271.
• [6] Lothaire, M.: Combinatorics on Words, Addison-Wesley, Reading MA, 1983, Reprinted by Cambridge University Press, Cambridge UK, 1997.
• [7] Mignosi, F., Zamboni, L. Q.: A note on a conjecture of Duval and Sturmian words, Theoret. Inform. Appl., 36, 2002, 1-3.
• [8] Morse, M., Hedlund, G. A.: Symbolic Dynamics, Amer. J. Math., 60, 1938, 815-866.
• [9] Morse, M., Hedlund, G. A.: Symbolic Dynamics II. Sturmian Trajectories, Amer. J. Math., 62, 1940, 1-42.
• [10] Perrin, D., Restivo, A.: A note on Sturmian words, Theor. Comput. Sci., (in press), 2012.
• [11] Rauzy, G.: Une généralisation du développement en fraction continue, in: Séminaire Delange-Pisot-Poitou, 18e année: 1976/77, Théorie des nombres, Fasc. 1, Secrétariat Math., Paris, 1977, Exp. No. 15, 16.
• [12] Rauzy, G.: échanges d'intervalles et transformations induites, Acta Arith., 34, 1979, 315-328.