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

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.

Classification : 68Q45, 68R15
Keywords: 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},
     year = {2001},
     publisher = {EDP Sciences},
     volume = {35},
     number = {6},
     mrnumber = {1922292},
     zbl = {1003.68064},
     language = {en},
     url = {https://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  - https://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 https://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. https://www.numdam.org/item/ITA_2001__35_6_513_0/

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

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

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

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

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

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

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

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

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