6533b850fe1ef96bd12a8428
RESEARCH PRODUCT
A note on Sturmian words
Dominique PerrinAntonio Restivosubject
Discrete mathematicsProperty (philosophy)General Computer ScienceSettore INF/01 - Informatica010102 general mathematics[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Sturmian word0102 computer and information sciencesSturmian wordsLexicographical order01 natural sciencesTheoretical Computer ScienceCombinatoricsTransformation (function)010201 computation theory & mathematicsFactor (programming language)combinatorics0101 mathematicscomputerTime complexitycomputer.programming_languageMathematicsdescription
International audience; 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2012-04-01 |