Clustering of return words in languages of interval exchanges

Abstract

A word over an ordered alphabet is said to be clustering if identical letters appear adjacently in its Burrows-Wheeler transform. Such words are strictly related to (discrete) interval exchange transformations. We use an extended version of the well-known Rauzy induction to show that every return word in the language generated by a regular interval exchange transformation is clustering, partially answering a question of Lapointe (2021).

Categories