Clustering, order conditions, and languages of interval exchanges

Abstract

We investigate various connections between the clustering for the Burrows-Wheeler transform, a lossless algorithm used in data compression, and languages of interval exchange transformations. We show that a primitive word $u$ clusters for a pair of orders $({<}_D,{<}_A)$ if and only if $u$ is a return word in the natural coding of a generalised interval exchange transformation with departure and arrival orders $({<}_D,{<}_A)$. This answers a question of M. Lapointe on the perfect clustering of return words for a symmetric standard interval exchange transformation. We show that if $T$ is symmetric, then all natural codings are palindromically rich languages, and the orders of the induced transformation on a cylinder $[w]$ equal the original departure/arrival orders $({<}_D,{<}_A)$ if and only if the shortest bispecial word containing $w$ is a palindrome. We also investigate language related features distinguishing between standard and generalised interval exchange transformations.