On synchronized sequences and their separators

Carpi, Arturo ; Maggi, Cristiano

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 6, pp. 513-524

Résumé

We introduce the notion of a $k$-synchronized sequence, where $k$ is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be $k$-synchronized if its graph is represented, in base $k$, by a right synchronized rational relation. This is an intermediate notion between $k$-automatic and $k$-regular sequences. Indeed, we show that the class of $k$-automatic sequences is equal to the class of bounded $k$-synchronized sequences and that the class of $k$-synchronized sequences is strictly contained in that of $k$-regular sequences. Moreover, we show that equality of factors in a $k$-synchronized sequence is represented, in base $k$, by a right synchronized rational relation. This result allows us to prove that the separator sequence of a $k$-synchronized sequence is a $k$-synchronized sequence, too. This generalizes a previous result of Garel, concerning $k$-regularity of the separator sequences of sequences generated by iterating a uniform circular morphism.

Détail

Classification : 68Q45, 68R15
Keywords: regular sequence, automatic sequence, separator