Sturmian and episturmian words (a survey of some recent results). (English) Zbl 1149.68065

Bozapalidis, Symeon (ed.) et al., Algebraic informatics. Second international conference, CAI 2007, Thessaloniki, Greece, May 21–25, 2007. Revised selected and invited papers. Berlin: Springer (ISBN 978-3-540-75413-8/pbk). Lecture Notes in Computer Science 4728, 23-47 (2007).
Summary: This survey paper contains a description of some recent results concerning Sturmian and episturmian words, with particular emphasis on central words. We list fourteen characterizations of central words. We give the characterizations of Sturmian and episturmian words by lexicographic ordering, we show how the Burrows-Wheeler transform behaves on Sturmian words. We mention results on balanced episturmian words. We give a description of the compact suffix automaton of central Sturmian words.
For the entire collection see [Zbl 1143.68003].


68R15 Combinatorics on words
68Q45 Formal languages and automata
Full Text: DOI