# On synchronized sequences and their separators

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

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

## References

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

## NotesEmbed ?

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