Skip to main content
Have a personal or library account? Click to login
Enumeration and Automatic Sequences Cover

Enumeration and Automatic Sequences

Pure Mathematics and Applications
Volume 25 (2015): Issue 1 (September 2015)
By:   
Open Access
|Oct 2015
References

References

  1. [1] J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoret. Comput. Sci., 98 (19292) 163-197.
    Open DOISearch in Google Scholar
  2. [2] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.
    Open DOISearch in Google Scholar
  3. [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. [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. [5] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Appl. Math., 24 (1989) 83-96.
    Search in Google Scholar
  6. [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. [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. [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. [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. [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. [11] A. Cobham, On the base-dependence of sets of numbers recognizable by _nite automata, Mathematical Systems Theory, 3 (1969) 186-192.
    Open DOISearch in Google Scholar
  12. [12] A. Cobham, Uniform tag sequences, Mathematical Systems Theory, 6 (1972) 164-192.
    Open DOISearch in Google Scholar
  13. [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. [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.
    Open DOISearch in Google Scholar
  15. [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. [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. [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. [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. [19] S. Homer and A. L. Selman, Computability and Complexity Theory, Springer-Verlag, 2nd edition, 2011.
    Open DOISearch in Google Scholar
  20. [20] B. Madill and N. Rampersad, The abelian complexity of the paperfolding word, Discrete Math., 313 (2013) 831-838.
    Search in Google Scholar
  21. [21] M. Morse and G. A. Hedlund, Symbolic dynamics, Amer. J. Math., 60 (1938) 815-866.
    Search in Google Scholar
  22. [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. [23] A. Tarski, Undecidable Theories, North-Holland, 2013.
    Search in Google Scholar
DOI: https://doi.org/10.1515/puma-2015-0008 | Journal eISSN: 1788-800X
Journal RSS Feed
Language: English
Page range: 96 - 106
Submitted on: Jul 10, 2014
Published on: Oct 7, 2015
Published by: Corvinus University of Budapest
In partnership with: Paradigm Publishing Services
Keywords:
enumeration,
automatic sequence,
recurrence,
regular sequence,
automaton,
bordered word,
synchronized sequence,
predicate,
logic,
Fibonacci representation
Related subjects:
Computer sciences,
Theoretical computer sciences,
Business and economics,
Mathematics and statistics for economists,
Mathematics,
Mathematics,
Analysis,
Differential equations and dynamical systems

© 2015 Jeffrey Shallit, published by Corvinus University of Budapest
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 25 (2015): Issue 1 (September 2015)
Previous article
Next article