Chebyshevskii Sbornik
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Chebyshevskii Sb.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Chebyshevskii Sb., 2019, Volume 20, Issue 4, Pages 69–85 (Mi cheb837)  

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

A. Ya. Belovab, A. L. Chernyatievcd

a Bar-Ilan University (Ramat Gan, Israel)
b College of Mathematics and Statistics, Shenzhen University, (Shenzhen, China)
c HSE (Moscow)
d Moscow Institute of Physics and Technology

Abstract: 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.


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

DOI: https://doi.org/10.22405/2226-8383-2018-20-4-69-85

Full text: PDF file (682 kB)
References: PDF file   HTML file

UDC: 519.101
Received: 07.08.2019
Accepted:20.12.2019

Citation: A. Ya. Belov, A. L. Chernyatiev, “On uniformly recurrent words generated by shifting segments, including with a change in orientation”, Chebyshevskii Sb., 20:4 (2019), 69–85

Citation in format AMSBIB
\Bibitem{KanChe19}
\by A.~Ya.~Belov, A.~L.~Chernyatiev
\paper On uniformly recurrent words generated by shifting segments, including with a change in orientation
\jour Chebyshevskii Sb.
\yr 2019
\vol 20
\issue 4
\pages 69--85
\mathnet{http://mi.mathnet.ru/cheb837}
\crossref{https://doi.org/10.22405/2226-8383-2018-20-4-69-85}


Linking options:
  • http://mi.mathnet.ru/eng/cheb837
  • http://mi.mathnet.ru/eng/cheb/v20/i4/p69

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:23
    Full text:10

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021