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

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.
Settore INF/01 - Informatica
Perrin, D., & Restivo, A. (2012). A note on Sturmian words. THEORETICAL COMPUTER SCIENCE, 429, 265-272 [10.1016/j.tcs.2011.12.047].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10447/73700
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact