Some Characterizations of Sturmian Words in Terms of the Lexicographic Order

Issue title: Words, Graphs, Automata, and Languages; Special Issue Honoring the 60th Birthday of Professor Tero Harju

Article type: Research Article

Authors: Bucci, Michelangelo | De Luca, Alessandro^; | Zamboni, Luca Q.^;

Affiliations: Department of Mathematics, University of Turku, FI-20014 Turku, Finland, michelangelo.bucci@utu.fi | Dipartimento di Scienze Fisiche, Università degli Studi di Napoli Federico II, via Cintia, Monte S. Angelo, I-80126 Napoli, Italy | Department of Mathematics, University of Turku, FI-20014 Turku, Finland, alessandro.deluca@utu.fi | Université de Lyon, Université Lyon 1, CNRS UMR 5208 Institut Camille Jordan, Bâtiment du Doyen Jean Braconnier, 43, blvd du 11 novembre 1918, F-69622 Villeurbanne Cedex, France | Department of Mathematics, University of Turku, FI-20014 Turku, Finland, luca.zamboni@utu.fi

Note: [] Partially supported by the FiDiPro grant “Words, Numbers, Tilings and Applications” from the Academy of Finland Address for correspondence: Department of Mathematics, University of Turku, FI-20014 Turku, Finland

Note: [] Partially supported by the FiDiPro grant “Words, Numbers, Tilings and Applications” from the Academy of Finland

Note: [] Partially supported by the FiDiPro grant “Words, Numbers, Tilings and Applications” from the Academy of Finland Partially supported by ANR grant SUBTILE

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

Keywords: Sturmian words, lexicographic order

DOI: 10.3233/FI-2012-665

Journal: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 25-33, 2012