An Interval Exchange Transformations, or IET, is a dynamical system obtained by iterating simple geometric transformations on an interval. Such kind of system can be seen as a generalization of the rotation of the circle. Using an operation called natural coding, one can obtain from a IET a formal language and a shift space, both satisfying interesting and peculiar properties. In this contribution we use IETs to describe the connections between symbolic dynamics and combinatorics on words, using tools ranging from formal language theory to ergodic theory. We also introduce Rauzy induction on a IET, which can be viewed as a generalization of the continued fraction expansion.
A symbolic dynamical system is a pair (X ; s ) formed of a topological space X and a continuous transformation s . A classical example of symbolic dynamical systems is given by Interval Exchange Transformations.
Let us consider the semi-interval [0; 1[ and a partition (Ia)a2A of [0; 1[, with A an ordered alphabet. The interval exchange transformation (or IET) relative to (Ia)a2A is the map T : [0; 1[! [0; 1[ defined by
T (z) = z + aa if z 2 Ia where aa is the length of the semi-interval Ia. Observe that the restriction of T to Ia is just a translation to T (Ia).
A IET can be represented by two copies of the semiinterval [0; 1[, one showing the partition (Ia)a2A and the other the partition given by (T (Ia))a2A .
Example 1. Let R be the interval exchange transformation corresponding to A = fa; bg, with a < b, and let Ia = [0; 1 a[ and Ib = [1 a; 1[. The transformation R is the rotation of angle a defined by
R(z) = z + a mod 1 and it is represented in Figure 1 (here a < 21 )).
The orbit of a point z is the set O(z) = fT n(z) j n 2
Zg. A transformation T is called minimal if the orbit of
every point is dense in [0; 1[. It is regular if the orbits of
the starting points of the semi-intervals Ia, for a 2 A , are
infinite and disjoint. Keane proved in [
The natural coding of a IET T with respect to a point z 2 [0; 1[ is the infinite word ST (z) = a0a1 on the alphabet A defined by an = a
if T n(z) 2 Ia:
Note that a bi-infinite version of such a coding can be easily defined by considering the transformation T 1.
Given a (finite or infinite) word w, we say that u is a factor of w if it is possible to write w = xuy for some words x; y. The set
L (T ) =
[ Fac (ST (z)) z2[0;1[ of all factors of all possible natural codings of a IET T is called the language associated to T . When T is minimal (resp. regular), this language does not depend on the choice of the point, but only of T ; in this case we call L (T ) a minimal (resp. regular) interval exchange set. 3
Given a language (factorial set) L and a word w 2 L , it is possible to define a bipartite graph, called the extension graph of w (with respect to L ), denoted E (w), describing the extensions of the word. Such a graph has on the left (resp. on the right) the left-extensions (resp. the right-extensions) of w, and the edges are given by the biextensions.
Example 3. Let us consider a language L containing as elements of length 3 the words aab; aba; baa; bab (but not aaa nor any word containing bb). The extension graphs of the empty word e is represented in Figure 3 on the left, while the empty graph of the letters a and b are represented respectively on the same figure on the center and on the right. a b
E (e)
E (a) a b a b a b
E (b) a a
A language such that the extension graph of every word in it is a tree (acyclic and connected graph) is called dendric.
Theorem 1 ( [
Let T be a regular IET and z 2 [0; 1[. The closure O(z)
of the orbit of z, together with the shift transformation
s : A Z ! A Z, defined by s (xn)n2Z = (xn+1)n2Z is a
symbolic dynamical system, called a IET subshift. It is known
that its entropy is zero. Moreover it is easy to find an
invariant probability measure m on (X ; s ) by associating to
each word w = a0a1 am 1 a semi-interval Iw as
Iw = Ia0 \ T 1(Ia1 ) \
\ T m+1(Iam 1 )
and defining m([w]) = jIwj, where j j is the classical
Lebesque measure. Keane conjectured in 1975 that every
symbolic dynamical system associated to a regular IET is
uniquely ergodic, that is that m is the only possible
invariant probability measure one can define on it. However,
Keynes and Newton proved in [
Let J [0; 1[ be semi-interval. If a IET T is minimal, for each z 2 [0; 1[ there is a n 0 such that T n(z) 2 J. The transformation induced by T on J is the IET S : J ! J defined for z 2 J by S(z) = T n(z) with n = minfk > 0 j T k(z) 2 Jg.
The Rauzy induction ([
Example 4. The transformation y(T ), where T is the IET defined in Example 1, is given by y(T )(z) =
T 2(z) if z 2 Ib
T (z) otherwise: Note that J is the semi-interval starting with 0 and ending at the starting point of Ib. The transformation is also represented in Figure 5. y(T )