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.
Perrin, D., Restivo, A. (2012). A note on Sturmian words. THEORETICAL COMPUTER SCIENCE, 429, 265-272 [10.1016/j.tcs.2011.12.047].
A note on Sturmian words
RESTIVO, Antonio
2012-01-01
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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
A note on Sturmian words_TCS2012.pdf
accesso aperto
Dimensione
286.13 kB
Formato
Adobe PDF
|
286.13 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
