Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.1

Clustering Words and Interval Exchanges


Sébastien Ferenczi
IMPA
CNRS -- UMI 2924
Estrada Dona Castorina 110
Rio de Janeiro, RJ 22460-32
Brazil

Luca Q. Zamboni
Institut Camille Jordan
Université Claude Bernard Lyon 1
43 boulevard du 11 novembre 1918
F-69622 Villeurbanne Cedex
France
and
Department of Mathematics
and Turku Centre for Computer Science
University of Turku
20014 Turku
Finland

Abstract:

We characterize words which cluster under the Burrows-Wheeler transform as those words w such that ww occurs in a trajectory of an interval exchange transformation, and build examples of clustering words.

Full version:  pdf,    dvi,    ps,    latex    

Received April 6 2012; revised version received August 20 2012. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page