Enumeration and Automatic Sequences

Shallit, Jeffrey

doi:10.1515/puma-2015-0008

Abstract

A sequence (a_n)n≥0 is k-automatic if there is a finite automaton that, on input n expressed in base k, reaches a state with output a_n. In this paper I will survey some recent advances concerning enumeration of various aspects of these sequences, such as the recurrence function, and the subword complexity (which counts the number of distinct blocks of length n).

References

[1] J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoret. Comput. Sci., 98 (19292) 163-197.10.1016/0304-3975(92)90001-V
Search in Google Scholar
[2] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.10.1017/CBO9780511546563
Search in Google Scholar
[3] J.-P. Allouche and J. Shallit The ring of k-regular sequences, II, Theoret. Comput. Sci., 307 (2003) 3-29.
Search in Google Scholar
[4] S. V. Avgustinovich, The number of different subwords of given length in the Morse-Hedlund sequence, Sibirsk. Zh. Issled. Oper., 1 (1994) 3-7. In Russian. English translation in A. D. Korshunov, ed., Discrete Analysis and Operations Research, Kluwer, 1996, pp. 1-5.
Search in Google Scholar
[5] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Appl. Math., 24 (1989) 83-96.
Search in Google Scholar
[6] V. Bruyère, G. Hansel, C. Michaux and R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. Simon Stevin, 1 (1994) 191-238. Corrigendum, Bull. Belg. Math. Soc. Simon Stevin, 1 (1994) 577.
Search in Google Scholar
[7] J. R. Büchi, Weak second-order arithmetic and _nite automata, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 6 (1960) 66-92. Reprinted in S. Mac Lane and D. Siefkes, eds., The Collected Works of J. Richard Büchi, Springer-Verlag, 1990, pp. 398-424
Search in Google Scholar
[8] A. Carpi and C. Maggi, On synchronized sequences and their separators, RAIRO Theor. Inform. Appl., 35 (2001) 513-524.
Search in Google Scholar
[9] J. Cassaigne, Sequences with grouped factors, in Developments in Language Theory III, Aristotle University of Thessaloniki, 1998, 211-222.
Search in Google Scholar
[10] E. Charlier, N. Rampersad and J. Shallit, Enumeration and decidable properties of automatic sequences, Internat. J. Found. Comp. Sci., 23 (2012) 1035-1066.
Search in Google Scholar
[11] A. Cobham, On the base-dependence of sets of numbers recognizable by _nite automata, Mathematical Systems Theory, 3 (1969) 186-192.10.1007/BF01746527
Search in Google Scholar
[12] A. Cobham, Uniform tag sequences, Mathematical Systems Theory, 6 (1972) 164-192.10.1007/BF01706087
Search in Google Scholar
[13] V. D'Alonzo, On the repetitivity index of infinite words, PhD thesis, Facoltà di Scienze Matematiche, Fisiche e Naturali, Università degli Studi di Napoli Federico II, 2009, available at http://www.fedoa.unina.it/3457/.
Search in Google Scholar
[14] A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci., 63 (1989) 333-348.10.1016/0304-3975(89)90013-3
Search in Google Scholar
[15] C. F. Du, H. Mousavi, L. Schaeffer and J. Shallit, Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance, preprint, 2014, available at http://arxiv.org/abs/1406.0670.
Search in Google Scholar
[16] D. Goč, D. Henshall and J. Shallit, Automatic theorem-proving in combinatorics on words, Internat. J. Found. Comp. Sci., 24 (2013) 781-798.
Search in Google Scholar
[17] D. Goč, H. Mousavi and J. Shallit, On the number of unbordered factors, Lecture Notes in Comput. Sci., 7810 (2013) 299-310.
Search in Google Scholar
[18] D. Goč, L. Schaeffer and J. Shallit, Subword complexity and k-synchronization, Lecture Notes in Comput. Sci., 7907 (2013) 252-263.
Search in Google Scholar
[19] S. Homer and A. L. Selman, Computability and Complexity Theory, Springer-Verlag, 2nd edition, 2011.10.1007/978-1-4614-0682-2
Search in Google Scholar
[20] B. Madill and N. Rampersad, The abelian complexity of the paperfolding word, Discrete Math., 313 (2013) 831-838.
Search in Google Scholar
[21] M. Morse and G. A. Hedlund, Symbolic dynamics, Amer. J. Math., 60 (1938) 815-866.
Search in Google Scholar
[22] L. Schaeffer, Deciding properties of automatic sequences, Master's Thesis, University ofWaterloo, 2013, https://uwspace.uwaterloo.ca/handle/10012/7899.
Search in Google Scholar
[23] A. Tarski, Undecidable Theories, North-Holland, 2013.
Search in Google Scholar

Enumeration and Automatic Sequences

Abstract

Paradigm

My account