On synchronized sequences and their separators

Carpi, Arturo, and Maggi, Cristiano. "On synchronized sequences and their separators." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.6 (2001): 513-524. <http://eudml.org/doc/92681>.

@article{Carpi2001,
abstract = {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.},
author = {Carpi, Arturo, Maggi, Cristiano},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {regular sequence; automatic sequence; separator; -synchronized sequence},
language = {eng},
number = {6},
pages = {513-524},
publisher = {EDP-Sciences},
title = {On synchronized sequences and their separators},
url = {http://eudml.org/doc/92681},
volume = {35},
year = {2001},
}

TY - JOUR
AU - Carpi, Arturo
AU - Maggi, Cristiano
TI - On synchronized sequences and their separators
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2001
PB - EDP-Sciences
VL - 35
IS - 6
SP - 513
EP - 524
AB - 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.
LA - eng
KW - regular sequence; automatic sequence; separator; -synchronized sequence
UR - http://eudml.org/doc/92681
ER -