The $ \ell $-Rauzy Graphs on Infinite Words
- 1 December 2024
- journal article
- research article
- Published by Pleiades Publishing Ltd in Journal of Applied and Industrial Mathematics
- Vol. 18 (4) , 824-838
Abstract
Word-representable graphs are vital in the Combinatorics of Words and Graph Theory. We define one such graph, the \( \ell \)-Rauzy graph, and study its structural properties for a few infinite words. The \( \ell \)-Rauzy graph of order \( k \) for an infinite word \( w \) is a directed graph in which each vertex is a subword of length \( k \) of \( w \), where any two vertices \( u,v \) form an arc \( uv \) iff the prefix of \( v \) of length \( \ell \) is the same as the suffix of \( u \) of length \( \ell \) and the concatenated word formed by the arc \( uv \) of length \( 2k-\ell \) is a subword of \( w \). As main results, we show that the \( \ell \)-Rauzy graph of order \( k \) for the infinite Fibonacci word \( f \) is strongly connected, and we explicitly find the graph structure of the \( \ell \)-Rauzy graph of order \( k \) for an infinite periodic word, by knowing the locations of subwords of \( f \) and infinite periodic words. As locating the subwords in an infinite word is not easy, we show that the \( \ell \)-Rauzy graph of order \( k \) for an Arnoux-Rauzy word is strongly connected using a different approach. \( \ell \)
Keywords
This publication has 21 references indexed in Scilit:
- Aperiodic pseudorandom number generators based on infinite wordsTheoretical Computer Science, 2016
- Words and Graphs2015
- A note on symmetries in the Rauzy graph and factor frequenciesTheoretical Computer Science, 2009
- Word Problem of the Perkins Semigroup via Directed Acyclic GraphsOrder, 2008
- Coloring circle graphsElectronic Notes in Discrete Mathematics, 2007
- The structure of subword graphs and suffix trees of Fibonacci wordsTheoretical Computer Science, 2006
- Locating factors of the infinite Fibonacci wordTheoretical Computer Science, 2005
- 3-coloring in timeJournal of Algorithms, 2005
- Subwords of the Golden Sequence and the Fibonacci Words1996
- Sequences With Subword Complexity 2nJournal of Number Theory, 1994