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
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},
     zbl = {1003.68064},
     mrnumber = {1922292},
     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
DA  - 2001///
SP  - 513
EP  - 524
VL  - 35
IS  - 6
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2001__35_6_513_0/
UR  - https://zbmath.org/?q=an%3A1003.68064
UR  - https://www.ams.org/mathscinet-getitem?mr=1922292
LA  - en
ID  - ITA_2001__35_6_513_0
ER  - 
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/

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

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

[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 614317 | Zbl 0472.10035

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

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

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

[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 1203822 | Zbl 0783.68065

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

[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 1453865 | Zbl 0959.11015