On Rauzy graph sequences of infinite words
Pavel Salimov · Journal of Applied and Industrial Mathematics · 2010
Under study are the sequences of Rauzy graphs (i.e., the graphs of subwords overlapping) of infinite words. The k -stretching of a graph is the graph we obtain by replacing each edge with a chain of length k . Considering a sequence of strongly connected directed graphs of maximal in and out vertex degrees equal to s , we prove that it is, up to stretchings, a subsequence of a Rauzy graphs sequence of some uniformly recurrent infinite word on s -letter alphabet. The language of a word of this kind and stretching for a given sequence of graphs are constructed explicitly.