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 metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00828351
Contributor : Dominique Perrin <>
Submitted on : Sunday, August 4, 2013 - 8:48:01 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, November 5, 2013 - 2:35:10 AM

File

noteSturmianWords.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

263

Files downloads

749