On synchronized sequences and their separators

Carpi, Arturo; Maggi, Cristiano

Carpi, Arturo ; Maggi, Cristiano

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 6, pp. 513-524.

Résumé

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.

MR Zbl

Classification : 68Q45, 68R15
Mots clés : regular sequence, automatic sequence, separator

@article{ITA_2001__35_6_513_0,
     author = {Carpi, Arturo and Maggi, Cristiano},
     title = {On synchronized sequences and their separators},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {513--524},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {6},
     year = {2001},
     mrnumber = {1922292},
     zbl = {1003.68064},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2001__35_6_513_0/}
}

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
SP  - 513
EP  - 524
VL  - 35
IS  - 6
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2001__35_6_513_0/
LA  - en
ID  - ITA_2001__35_6_513_0
ER  -

%0 Journal Article
%A Carpi, Arturo
%A Maggi, Cristiano
%T On synchronized sequences and their separators
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 513-524
%V 35
%N 6
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_2001__35_6_513_0/
%G en
%F ITA_2001__35_6_513_0

Carpi, Arturo; Maggi, Cristiano. On synchronized sequences and their separators. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 6, pp. 513-524. http://www.numdam.org/item/ITA_2001__35_6_513_0/

Bibliographie
Cité par

[1] J.-P. Allouche and J. Shallit, The ring of $k$ -regular sequences. Theoret. Comput. Sci. 98 (1992) 163-197. | MR | Zbl

[2] G. Christol, Ensembles presque périodiques $k$ -reconnaissables Theoret. Comput. Sci. 9 (1979) 141-145. | MR | Zbl

[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. | Numdam | MR | Zbl

[4] A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972) 164-192. | MR | Zbl

[5] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1974). | MR | Zbl

[6] C.C. Elgot and J.E. Mezei, On relations defined by generalized finite automata. IBM J. Res. Develop. 9 (1965) 47-68. | MR | Zbl

[7] C. Frougny, Numeration Systems, in Algebraic Combinatorics on Words. Cambridge University Press (to appear).

[8] C. Frougny and J. Sakarovitch, Synchronized rational relations of finite and infinite words. Theoret. Comput. Sci. 108 (1993) 45-82. | MR | Zbl

[9] E. Garel, Séparateurs dans les mots infinis engendrés par morphismes. Theoret. Comput. Sci. 180 (1997) 81-113. | MR | Zbl

[10] C. Pomerance, J.M. Robson and J. Shallit, Automaticity II: Descriptional complexity in the unary case. Theoret. Comput. Sci. 180 (1997) 181-201. | MR | Zbl