RAIRO-Theor. Inf. Appl.
Volume 35, Number 6, November/December 2001A tribute to Aldo de Luca
|Page(s)||513 - 524|
|Published online||15 July 2002|
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.