Enumeration and decidable properties of automatic sequences

[en] We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems.

Disciplines :

Mathematics

Author, co-author :

Charlier, Emilie ; University of Waterloo > School of Computer Science

Rampersad, Narad

Shallit, Jeffrey

Language :

English

Title :

Enumeration and decidable properties of automatic sequences

Publication date :

2011

Event name :

15th International Conference on Developments in Language Theory

Event place :

Milan, Italy

Event date :

du 19 juillet 2011 au 22 juillet 2011

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Heidelberg, Germany

Special issue title :

Developments in language theory

Volume :

6795

Pages :

165-179

Peer reviewed :

Peer reviewed

Available on ORBi :

since 19 June 2012

Statistics

Number of views

61 (6 by ULiège)

Number of downloads

1 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Allouche, J.-P., Baake, M., Cassaigne, J., Damanik, D.: Palindrome complexity. Theoret. Comput. Sci. 292, 9-31 (2003)
Allouche, J.-P., Rampersad, N., Shallit, J.: Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410, 2795-2803 (2009)
Allouche, J.-P., Shallit, J.O.: The ring of k-regular sequences. Theoret. Comput. Sci. 98, 163-197 (1992)
Allouche, J.-P., Shallit, J.O.: The ring of k-regular sequences, II. Theoret. Comput. Sci. 307, 3-29 (2003)
Allouche, J.-P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)
Berstel, J.: An exercise on Fibonacci representations. RAIRO Inform. Théor. App. 35, 491-498 (2001)
Berstel, J., Reutenauer, C.: Noncommutative Rational Series With Applications. Encyclopedia of Mathematics and Its Applications, vol. 137. Cambridge University Press, Cambridge (2011)
Brown, S., Rampersad, N., Shallit, J., Vasiga, T.: Squares and overlaps in the Thue-Morse sequence and some variants. RAIRO Inform. Théor. App. 40, 473-484 (2006)
Bruyère, V., Hansel, G.: Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181, 17-43 (1997)
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and p-recognizable sets of integers. Bull. Belgian Math. Soc. 1, 191-238 (1994); Corrigendum, Bull. Belg. Math. Soc. 1, 577 (1994)
Carpi, A., D'Alonzo, V.: On the repetitivity index of infinite words. Internat. J. Algebra Comput. 19, 145-158 (2009)
Carpi, A., D'Alonzo, V.: On factors of synchronized sequences. Theor. Comput. Sci. (to appear 011)
Carpi, A., Maggi, C.: On synchronized sequences and their separators. RAIRO Inform. Théor. App. 35, 513-524 (2001)
Cobham, A.: Uniform tag sequences. Math. Systems Theory 6, 164-192 (1972)
Currie, J.D.: Lexicographically least words in the orbit closure of the Rudin-Shapiro word (2010), http://arxiv.org/pdf/0905.4923
Currie, J.D., Saari, K.: Least periods of factors of infinite words. RAIRO Inform. Théor. App. 43, 165-178 (2009)
Fagnot, I.: Sur les facteurs des mots automatiques. Theoret. Comput. Sci. 172, 67-89 (1997)
Frougny, C., Solomyak, B.: On representation of integers in linear numeration systems. In: Pollicott, M., Schmidt, K. (eds.) Ergodic Theory of ℤd Actions (Warwick, 1993-1994), London Mathematical Society Lecture Note Series, vol. 228, pp. 345-368. Cambridge University Press, Cambridge (1996)
Garel, E.: Séparateurs dans les mots infinis engendrés par morphismes. Theoret. Comput. Sci. 180, 81-113 (1997)
Halava, V., Harju, T., Kärki, T., Rigo, M.: On the periodicity of morphic words. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol. 6224, pp. 209-217. Springer, Heidelberg (2010)
Honkala, J.: A decision method for the recognizability of sets defined by number systems. RAIRO Inform. Théor. App. 20, 395-403 (1986)
Krieger, D., Shallit, J.: Every real number greater than 1 is a critical exponent. Theoret. Comput. Sci. 381, 177-182 (2007)
Leroux, J.: A polynomial time Presburger criterion and synthesis for number decision diagrams. In: 20th IEEE Symposium on Logic in Computer Science (LICS 2005), pp. 147-156. IEEE Press, Los Alamitos (2005)
Mossé, B.: Reconnaissabilité des substitutions et complexité des suites automatiques. Bull. Soc. Math. France 124, 329-346 (1996)
Nicolas, F., Pritykin, Y.: On uniformly recurrent morphic sequences. Internat. J. Found. Comp. Sci. 20, 919-940 (2009)
Saari, K.: On the Frequency and Periodicity of Infinite Words. PhD thesis, University of Turku, Finland (2008)
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009)