[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 some new characterizations
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 :
2012
Journal title :
International Journal of Foundations of Computer Science
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.
Bibliography
Adamdzewski, B., Bugeaud, Y., Palindromic continued fractions (2007) Ann. Inst. Fourier 57, pp. 1557-1574
Allouche, J.-P., Baake, M., Cassaigne, J., Damanik, D., (2003) Palindrome Complexity. Theoret. Comput. Sci, 292, pp. 9-31
Allouche, J.-P., Rampersad, N., Shallit, J., Periodicity, repetitions, and orbits of an automatic sequence (2009) Theoret. Comput. Sci, 410, pp. 2795-2803
Allouche, J.-P., Shallit, J.O., The ring of k-regular sequences (1992) Theoret. Comput. Sci, 98, pp. 163-197
Allouche, J.-P., Shallit, J.O., The ring of k-regular sequences II (2003) Theoret. Comput. Sci, 307, pp. 3-29
Allouche, J.-P., Shallit, J., (2003) Automatic Sequences: Theory Applications General- Izations, , Cambridge University Press
Berstel, J., An exercise on Fibonacci representations (2001) RAIRO - Theoretical Informatics and Applications, 35 (6), pp. 491-498. , DOI 10.1051/ita:2001127
Berstel, J., Reutenauer, C., (2011) Noncommutative Rational Series with Applications 137 of Encyclopedia of Mathematics and Its Applications, , Cambridge University Press
Brown, S., Rampersad, N., Shallit, J., Vasiga, T., Squares and overlaps in the thue-morse sequence and some variants (2006) RAIRO - Theoretical Informatics and Applications, 40 (3), pp. 473-484. , http://www.edpsciences.org/articles/ita/pdf/2006/03/ita05024.pdf?access= ok, DOI 10.1051/ita:2006030, Word Avoidability, Complexity And Morphisms (WACAM)
Bruyere, V., Hansel, G., Bertrand numeration systems and recognizability (1997) Theoretical Computer Science, 181 (1), pp. 17-43. , PII S0304397596002605
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R., Logic and p-recognizable sets of integers (1994) Bull. Belgian Math. Soc, 1, pp. 191-238. , Corrigendum Bull Belg Math Soc 1 1994 577
Bucci, M., De Luca, A., Zamboni, L.Q., (2011) Reversible Christoffel Factorizations, , http://www.pdmi.ras.ru/EIMI/2011/RuFiDiM/booklet.pdf, Paper presented at the First Russian-Finnish Symposium on Discrete Mathematics St. Petersburg September 21-24 Abstract available at
Carpi, A., D'Alonzo, V., On the repetitivity index of infinite words (2009) Internat. J. Algebra Comput, 19, pp. 145-158
Carpi, A., D'Alonzo, V., On factors of synchronized sequences (2010) Theor. Comput. Sci, 411, pp. 3932-3937
Carpi, A., Maggi, C., On synchronized sequences and their separators (2001) RAIRO - Theoretical Informatics and Applications, 35 (6), pp. 513-524. , DOI 10.1051/ita:2001129
Cobham, A., Uniform tag sequences (1972) Math. Systems Theory, 6, pp. 164-192
Currie, J.D., Lexicographically least words in the orbit closure of the rudin-shapiro word (2011) Theor. Comput. Sci, 412, pp. 4742-4746
Currie, J.D., Saari, K., Least periods of factors of infinite words. RAIRO Inform (2009) Th'Eor. App, 43, pp. 165-178
Droste, M., Kuich, W., Vogler, H., (2009) Handbook of Weighted Automata, , Springer- Verlag
Fagnot, I., Sur les facteurs des mots automatiques (1997) Theoretical Computer Science, 172 (1-2), pp. 67-89
Frid, A., Infinite permutations vs. infinite words (2011) WORDS 2011, 8th International Conference 13-19 Elect Proc Theor Comput Sci, , http://arxiv.org/abs/1108.3616-1, P. Ambrož, S. Holub, and Z. Mas'akov'a, editors Available at
Frid, A., Zamboni, L.Q., On automatic infinite permutations RAIRO Inform. th'Eor. App. to Appear
Frougny, C., Solomyak, B., On representation of integers in linear numeration systems (1996) Ergodic Theory of Zd Actions, , In M. Pollicott and K. Schmidt, editors Warwick 1993-1994 228 of London Mathematical Society Lecture Note Series 345-368 Cambridge University Press
Garel, E., Séparateurs dans les mots infinis engendrés par morphismes (1997) Theoretical Computer Science, 180 (1-2), pp. 81-113. , PII S03043975960001090
Halava, V., Harju, T., K̈arki, T., Rigo, M., On the periodicity of morphic words (2010) Developments in Language Theory 2010 6224 of Lecture Notes in Computer Science, pp. 209-217. , Springer Verlag
Henshall, D., Shallit, J., Automatic theorem-proving in combinatorics on words (2012) Manuscript, , http://arxiv.org/abs/1203.3758, March 15 Available at
Honkala, J., A decision method for the recognizability of sets defined by number systems (1986) RAIRO Inform. th'Eor. App, 20, pp. 395-403
Klavzar, S., Milutinovic, U., Petr, C., Stern polynomials (2007) Advances in Applied Mathematics, 39 (1), pp. 86-95. , DOI 10.1016/j.aam.2006.01.003, PII S0196885806000807
Krieger, D., Shallit, J., Every real number greater than 1 is a critical exponent (2007) Theoretical Computer Science, 381 (1-3), pp. 177-182. , DOI 10.1016/j.tcs.2007.04.037, PII S0304397507003398
Kuich, W., Salomaa, A., (1986) Semirings Automata Languages, , Springer-Verlag
Leroux, J., A polynomial time Presburger criterion and synthesis for number decision diagrams (2005) 20th IEEE Symposium on Logic in Computer Science (LICS, 147-156. , IEEE Press 2005
Mignosi, F., Restivo, A., Characteristic Sturmian words are extremal for the critical factorization theorem Theoret. Comput. Sci., to Appear
Moss'E, B., Reconnaissabilit'e des substitutions et complexit'e des suites automatiques (1996) Bull. Soc. Math. France, 124, pp. 329-346
Nicolas, F., Pritykin, Yu., On uniformly recurrent morphic sequences (2009) Internat. J. Found. Comp. Sci, 20, pp. 919-940
Reznick, B., Some binary partition functions (1990) Analytic Number Theory 85 of Progr. Math, pp. 451-477. , Birkhäuser
Saari, K., (2008) On the Frequency and Periodicity of Infinite Words, , PhD Thesis University of Turku Finland
Sakarovitch, J., (2009) Elements of Automata Theory, , Cambridge University Press
Salomaa, A., Soittola, M., (1978) Automata-Theoretic Aspects of Formal Power Series, , Springer-Verlag
Scḧutzenberger, M.-P., On a theorem of R (1962) Jungen. Proc. Amer. Math. Soc, 13, pp. 885-890
Shallit, J., The critical exponent is computable for automatic sequences WORDS 2011, 8th International Conference, pp. 231-239. , http://arxiv.org/abs/1104.2303-2, Available at In P. Ambrož, S. Holub, and Z. Mas'akov'a, editors Elect Proc Theor Comput Sci 2011. Revised version, with L. Schaeffer, submitted
Widmer, S., Permutation Complexity of the Thue-Morse word (2011) Adv. in Appl Math, 47, pp. 309-329
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.