Interval exchange transformations, Rauzy graphs, Universal sequences and factor-Dynamics.

Let $M$ be a compact metric space, $U\subset M$ be its open subspace, $f:M\to M$ be a homeomorphism of the compact into itself, and $x\in M$ be an initial point. It determines sequence of points
$x,f(x),\ldots,f^{(n)}(x),\ldots$ With the sequence of iterations, one can associate an infinite binary word $w_n=a$ for $f^{(n)}(x_0)\in U$, $w_n=b$ for $f^{(n)}(x_0)\notin U$
which is called the {\it evolution} of point $x_0$. If $f$ is invertible then $n\in \mathbb{Z}$, otherwise $n\in \mathbb{N}$. Symbolic dynamics investigates the interrelation between the
properties of the dynamical system $(M,f)$ and the combinatorial properties of the word $W_n$. For words over alphabets which comprise more symbols, several characteristic sets should be
considered: $U_1,\ldots,U_n$.

The famous Sturmian sequences and some of their generalizations

present situation of ``combinatorial paradise''.  It provides patterns for further investigation. Let us remind the classical result.

{\bf Equivalence theorem} {\it Let $W$ be an infinite recurrent word over the binary alphabet
$A=\{a,b\}$. The following conditions are equivalent: 1) The word $W$ is a {\em Sturmian word}, i.e., for any $n\geq 1$,
the number of different subwords of length $n$ that occur in $W$ is equal to $T_n(W)=n+1$. 2) The word is not periodic and is {\em balanced}, i.e., any
two subwords $u,v\subset W$ of the same length satisfy the inequality $||v|_a-|u|_a|\leq 1$, where $|w|_a$ denotes the number
of occurrences of symbol $a$ in the word $w$. 3) The word $W=(w_n)$ is a {\em mechanical} word with irrational
$\alpha$, i.e. there exist an irrational $\alpha$, $x_0 \in [0,1]$, and interval $U\subset \mathbb{S}^1$,
$|U|=\alpha$, such that $w_n=a$ for $T_{\alpha}^n(x_0)\in U$, $w_n=b$ for $T_{\alpha}^n(x_0)\notin U$

4) Word  $W$ can be obtained as a limit of the sequence of finite words $\{w_i\}_{i=1}^\infty$, such that $w_{i+1}$ can be
obtained from $w_{i}$ via substitution of the following type $a^{k_i}b\to b, a^{k_i+1}b\to a$ or $b^{k_i}a\to a, b^{k_i+1}a\to
b$.  Iff sequence of these substitutions is periodic, then $\alpha$ is

a quadratic irrational.}

There are several different ways of generalizing Sturmian words. One of the most important is interval exchange transformation. 

It can be done in terms of {\em Rauzy graphs}.  The {\it Rauzy graph} of order $k$ (the {\it $k$-graph}) of the word $W$ is the directed graph whose

vertices biuniquely correspond to the factors of length $k$ of the word $W$ and the vertex $A$ is connected to vertex $B$ by directed
arc iff $W$ has a factor of length $k+1$ such that its first $k$ letters make the subword that corresponds to $A$ and the last $k$
symbols make the subword that corresponds to $B$. By the {\it follower} of the directed $k$-graph $G$ we call the directed graph
$\Fol(G)$ constructed as follows: the vertices of graph $\Fol(G)$ are in one-to-one correspondence with the arcs of graph $G$ and
there exists an arc from vertex $A$ to vertex $B$ if and only if the head of the arc $A$ in the graph $G$ is at the notch end of
$B$. The $(k+1)$-graph is a subgraph of the follower of the $k$-graph; it results from the latter by removing some arcs.
Vertices which are tails of (or heads of) at least two arcs correspond to {\it special factors}; vertices which are heads and
tails of more than one arc correspond to {\it bispecial factors}. The sequence of the Rauzy $k$-graphs constitutes the {\it
evolution} of the Rauzy graphs of the word $W$.

We discourse factor-dynamics properties,  universal sequences (for example language consisting all words which appear in $k$-interval exchange for some $k$, deformations of universal language 

and the first digit sequence $2^{n^2}$. 

Let $P(n)$ be a polynomial, having an irrational coefficient of the highest degree. A word $W=(w_n)$, (n\in \mathbb{N})$ consists of a sequence of first binary numbers of $\{P(n)\}$ i.e. $w_n=[2\{P(n)\}]$. Denote by $T(k)$ the number of different subwords of $W$ of length $k$.  

{\bf Theorem}. There exists a polynomial $Q(k)$, depending only on the power of the polynomial $P$, such that $T(k)=Q(k)$ for all sufficiently great $k$.

similar is true for the first digit sequence $2^{n^2}$.

(Joint work with , I.Reshetnikov)