[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
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
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)
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
