Skip to Main content Skip to Navigation
Journal articles

A note on Sturmian words

Abstract : We describe an algorithm which, given a factor of a Sturmian word, computes the next factor of the same length in the lexicographic order in linear time. It is based on a combinatorial property of Sturmian words which is related with the Burrows-Wheeler transformation.
keyword : combinatorics
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Dominique Perrin Connect in order to contact the contributor
Submitted on : Sunday, August 4, 2013 - 8:48:01 PM
Last modification on : Saturday, January 15, 2022 - 3:58:22 AM
Long-term archiving on: : Tuesday, November 5, 2013 - 2:35:10 AM


Files produced by the author(s)



Dominique Perrin, Antonio Restivo. A note on Sturmian words. Theoretical Computer Science, Elsevier, 2012, 429 (1), pp.265-272. ⟨10.1016/j.tcs.2011.12.047⟩. ⟨hal-00828351⟩



Les métriques sont temporairement indisponibles