On uniformly recurrent words generated by shifting segments, including with a change in orientation

A. Ya. Belov ; A. L. Chernyatiev

Čebyševskij sbornik, Tome 20 (2019) no. 4, pp. 69-85.

Résumé

The work is devoted to the review of some problems of symbolic dynamics. The description of uniformly recurrent words associated with the shifting of segments is given. Let $W$ be an infinite word over finite alphabet $A$. We get combinatorial criteria of existence of interval exchange transformations that generate the word $W$. In this paper we study words generated by general piecewise-continuous transformation of the interval. Further we prove equivalence set words generated by piecewise-continuous transformation and words generated by interval exchange transformation. This method get capability of descriptions of the words generated by arbitrary interval exchange transformation. This work is targeted to the following Inverse problem: Which conditions should be imposed on a uniformly recurrent word $W$ in order that it be generated by a dynamical system of the form $(I,T,U_1,\ldots,U_k)$, where $I$ is the unit interval and $T$ is the interval exchange transformation? The answer to this question is given in terms of the evolution of the labeled Rauzy graphs of the word $W$. The Rauzy graph of order $k$ (the $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 there exists an arc from vertex $A$ to vertex $B$ if and only if $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 follower of the directed $k$-graph $G$ we call the directed graph $\mathrm{Fol}(G)$ constructed as follows: the vertices of graph $\mathrm{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 special factors (see Section 2); vertices which are heads and tails of more than one arc correspond to bispecial factors. The sequence of the Rauzy $k$-graphs constitutes the evolution of the Rauzy graphs of the word $W$. The Rauzy graph is said to be labeled if its arcs are assigned letters $l$ and $r$ and some of its vertices (perhaps, none of them) are assigned symbol “–”. The follower of the labeled Rauzy graph is the directed graph which is the follower of the latter (considered a Rauzy graph with the labeling neglected) and whose arcs are labeled according to the following rule: Arcs that enter a branching vertex should be labeled by the same symbols as the arcs that enter any left successor of this vertex; Arcs that go out of a branching vertex should be labeled by the same symbols as the arcs that go out of any right successor of this vertex; If a vertex is labeled by symbol “–”, then all its right successors should also be labeled by symbol “–”. In terms of Rauzy labeled graphs we define the asymptotically correct evolution of Rauzy graphs, i.e., we introduce rules of passing from $k$-graphs to $(k+1)$-graphs. Namely, the evolution is said to be correct if, for all $k\geq 1$, the following conditions hold when passing from the $k$-graph $G_k$ to the $(k+1)$-graph $G_{k+1}$ : The degree of any vertex is at most $2$, i.e., it is incident to at most two incoming and outgoing arcs; If the graph contains no vertices corresponding to bispecial factors, then $G_{n+1}$ coincides with the follower $D(G_n)$; If the vertex that corresponds to a bispecial factor is not labeled by symbol “–”, then the arcs that correspond to forbidden words are chosen among the pairs $lr$ and $rl$; If the vertex is labeled by symbol “–”, then the arcs to be deleted should be chosen among the pairs $ll$ or $rr$. The evolution is said to be asymptotically correct if this condition is valid for all $k$ beginning with a certain $k=K$. The oriented evolution of the graphs means that there are no vertices labeled by symbol “–”. The main result of this work consists in the description of infinite words generated by interval exchange transformations (and answers a Rouzy question [21]): Main theorem. A uniformly recurrent word $W$ is generated by an interval exchange transformation if and only if the word is provided with the asymptotically correct evolution of the labeled Rauzy graphs; is generated by an orientation–preserving interval exchange transformation if and only if the word is provided with the asymptotically correct oriented evolution of the labeled Rauzy graphs.

Détail

Keywords: combinatorics of words, Sturmian sequence, interval exchange transformation, morphic sequence, symbolical dynamics, Rauzy graph.

Bibliographie

[1] A.Ya. Belov, V.V. Borisenko, V.N. Latyshev, “Monomialnye algebry”, Itogi nauki i tekhniki. Sovr. Mat. Pril. Tem. Obzory, 26, M., 2002, 35–214

[2] A.Ya. Belov, G. Kondakov, “Obratnye zadachi simvolicheskoi dinamiki”, Fundamentalnaya i prikladnaya matematika, 1 (1995) | MR

[3] A.Ya. Belov, A.L. Chernyatev, “Opisanie slov Shturma nad n-bukvennym alfavitom”, Mat. metod. i pril. IV, MGSU, 1999, 122–128

[4] Ya.G. Sinai, Vvedenie v ergodicheskuyu teoriyu, FAZIS, M., 1996, 144 pp. | MR

[5] A.L. Chernyatev, “Sbalansirovannye slova i dinamicheskie sistemy”, Fund. i Prikl. Mat. (to appear)

[6] A.L. Chernyatev, “Slova s minimalnoi funktsiei rosta”, Vestnik MGU, 2007 (to appear)

[7] A. Aberkane, “Words whose complexity satisfies $\lim p(n)/n = 1$”, Theor. Comp. Sci., 307 (2003), 31–46 | DOI | MR | Zbl

[8] P. Arnoux, G. Rauzy, “Representation geometrique des suites the complexite $2n + 1$”, Bull. Soc. Math. France, 119 (1991), 199–215 | DOI | MR | Zbl

[9] V. Berthé, S. Ferenczi, Luca Q. Zamboni, Interactions between Dynamics, Arithmetics and Combinatorics: the Good, the Bad, and the Ugly, 2007 | MR

[10] J. Berstel, P. Séébold, “Sturmian words”, Algebraic Combinatorics on Words, Chap. 2, Encyclopedia of Mathematics and Its Applications, 90, ed. M. Lothaire, Cambridge University Press, Cambridge, 2002 | MR

[11] J. Berstel, “Resent results on Sturmian words”, Developments in language theory II, World Scientific, 1996, 13–24 | MR | Zbl

[12] X. Droubay, J. Justin, G. Pirillo, “Episturmian words and some construction of de Luca and Rauzy”, Theoret. Comp. Sci., 2000 (to appear) | MR

[13] H. Furstenberg, “Poincaré reccurence and number theory”, Bull. Amer. Math. Soc., 5 (1981), 211–234 | DOI | MR | Zbl

[14] S. Ferenczi, Luca Q. Zamboni, Combinatorial structure of symmetric k-interval exchange transformations, in preparation

[15] S. Ferenczi, C. Holton, Luca Q. Zamboni, “Structure of three-interval exchange transformations II: a combinatorial description of the trajectories”, J. Analyse Math., 89 (2003), 239–276 | DOI | MR | Zbl

[16] R. L. Graham, “Covering the Positive Integers by disjoints sets of the form $\{[n\alpha + \beta]:$ $n=1, 2, \ldots\}$”, J. Combin. Theory Ser. A, 15 (1973), 354–358 | DOI | MR | Zbl

[17] P. Hubert, “Well balanced sequences”, Theoret. Comput. Sci., 242 (2000), 91–108 | DOI | MR | Zbl

[18] A. de Luca, “Sturmian words: structure, combinatorics and their arithmetics”, Theoret. Comp. Sci., 183 (1997), 45–82 | DOI | MR | Zbl

[19] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, 17, Addison-Wesley, Reading, MA, 1983 | MR | Zbl

[20] M. Morse, G. A. Hedlund, “Symbolic dynamics II. Sturmian trajectories”, Amer. J. Math., 62 (1940), 1–42 | DOI | MR

[21] G. Rauzy, “Mots infnis en arithmetique”, Automata on Infnite Words, Ecole de Printemps d'Informatique Thfeorique (Le Mont Dore, May 1984), Lecture Notes in Computer Science, 192, eds. M. Nivat, D. Perrin, Springer-Verlag, Berlin etc., 1985, 165–171 | MR

[22] G. Rote, “Sequences with subword complexity $2n$”, J. Number Theory, 46 (1994), 196–213 | DOI | MR | Zbl

[23] L. Vuillon, “Balanced words”, Bull. Belg. Math. Soc. Simon Stevin, 10:5 (2003), 787–805 | DOI | MR