On synchronized sequences and their separators

¹ Dipartimento di Matematica e Informatica, Università di Perugia, via Vanvitelli 1, 06123 Perugia, Italy; (carpi@dipmat.unipg.it)
² Dipartimento di Matematica, Università “La Sapienza”, Roma, Italy.

Received: 13 April 2001
Revised: 21 February 2002

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.