LANGUAGES OF k-INTERVAL EXCHANGE TRANSFORMATIONS

Abstract. This paper gives a complete characterization of those sequences of subword complexity (k − 1)n+1 which are natural codings of orbits of k-interval exchange transfor-mations, thereby answering an old question of Rauzy. Interval exchange transformations were originally introduced by Oseledec [17], following an idea of Arnold [1], see also [9]; an exchange of k intervals, denoted throughout this paper by I, is given by a probability vector of k lengths (α1,..., αk) together with two permutations (pi0, pi1) on k letters. The unit interval is partitioned into k subintervals of lengths α1,..., αk which are ordered according to pi−10 and then rearranged by I according to pi −1 1. It was Rauzy [18] who first saw interval exchange transformations as a possible framework for generalizing the well-known interaction between circle rotations on one hand, and Sturmian sequences [16] on the other; thus he asked the question “how to describe the symbolic sequences which are natural codings of k-interval exchange transformations”, a natural coding meaning a sequence (xn) taking the value 1, 2,... k when the n-th iterate of some point x lies in th