# On synchronized sequences and their separators

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 35, Issue: 6, page 513-524
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCarpi, Arturo, and Maggi, Cristiano. "On synchronized sequences and their separators." RAIRO - Theoretical Informatics and Applications 35.6 (2010): 513-524. <http://eudml.org/doc/221953>.

@article{Carpi2010,

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},

keywords = {Regular sequence; automatic sequence; separator; -synchronized sequence},

language = {eng},

month = {3},

number = {6},

pages = {513-524},

publisher = {EDP Sciences},

title = {On synchronized sequences and their separators},

url = {http://eudml.org/doc/221953},

volume = {35},

year = {2010},

}

TY - JOUR

AU - Carpi, Arturo

AU - Maggi, Cristiano

TI - On synchronized sequences and their separators

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

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/221953

ER -

## References

top- J.-P. Allouche and J. Shallit, The ring of k-regular sequences. Theoret. Comput. Sci.98 (1992) 163-197. Zbl0774.68072
- G. Christol, Ensembles presque périodiques k-reconnaissables Theoret. Comput. Sci.9 (1979) 141-145.
- G. Christol, T. Kamae, M. Mendès France and G. Rauzy, Suites algébriques, automates et substitutions. Bull. Soc. Math. France108 (1980) 401-419. Zbl0472.10035
- A. Cobham, Uniform tag sequences. Math. Systems Theory6 (1972) 164-192. Zbl0253.02029
- S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1974). Zbl0317.94045
- C.C. Elgot and J.E. Mezei, On relations defined by generalized finite automata. IBM J. Res. Develop.9 (1965) 47-68. Zbl0135.00704
- C. Frougny, Numeration Systems, in Algebraic Combinatorics on Words. CambridgeUniversity Press (to appear). Zbl0787.68057
- C. Frougny and J. Sakarovitch, Synchronized rational relations of finite and infinite words. Theoret. Comput. Sci.108 (1993) 45-82. Zbl0783.68065
- E. Garel, Séparateurs dans les mots infinis engendrés par morphismes. Theoret. Comput. Sci.180 (1997) 81-113.
- C. Pomerance, J.M. Robson and J. Shallit, Automaticity II: Descriptional complexity in the unary case. Theoret. Comput. Sci.180 (1997) 181-201. Zbl0959.11015

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.