On synchronized sequences and their separators
Dipartimento di Matematica e
Informatica, Università di Perugia, via Vanvitelli 1, 06123 Perugia,
2 Dipartimento di Matematica, Università “La Sapienza”, Roma, Italy.
Revised: 21 February 2002
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.
Mathematics Subject Classification: 68Q45 / 68R15
Key words: Regular sequence / automatic sequence / separator
© EDP Sciences, 2001