A note on Sturmian words

Authors: Perrin, D; Restivo, A
Publication year: 2012
Type: Articolo in rivista (Articolo in rivista)
OA Link: http://hdl.handle.net/10447/73700

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.