On synchronized sequences and their separators
Carpi, Arturo ; Maggi, Cristiano
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 513-524 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2001-01-01
Classification:  68Q45,  68R15 
@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},
     volume = {35},
     year = {2001},
     pages = {513-524},
     mrnumber = {1922292},
     zbl = {1003.68064},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 513-524. http://gdmltest.u-ga.fr/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