Abstract
In this talk I will report on some recent results concerning decidability and enumeration for properties of automatic sequences. This is work with Jean-Paul Allouche, Émilie Charlier, Narad Rampersad, Dane Henshall, Luke Schaeffer, Eric Rowland, Daniel Goč, and Hamoon Mousavi.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allouche, J.P., Baake, M., Cassaigne, J., Damanik, D.: Palindrome complexity. Theoret. Comput. Sci. 292, 9–31 (2003)
Allouche, J.P., Currie, J., Shallit, J.: Extremal infinite overlap-free binary words. European J. Combinatorics 5, R27 (1998), http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r27
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.: The ubiquitous Prouhet-Thue-Morse sequence. In: Ding, C., Helleseth, T., Niederreiter, H. (eds.) Proceedings of Sequences and Their Applications, SETA 1998, pp. 1–16. Springer (1999)
Allouche, J.P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003)
Berstel, J.: Axel Thue’s work on repetitions in words. In: Leroux, P., Reutenauer, C. (eds.) Séries Formelles et Combinatoire Algébrique, Publications du LaCim, Université du Québec à Montréal, vol. 11, pp. 65–80 (1992)
Blondin Massé, A., Brlek, S., Garon, A., Labbé, S.: Combinatorial properties of f-palindromes in the Thue-Morse sequence. Pure Math. Appl. 19(2-3), 39–52 (2008), http://www.mat.unisi.it/newsito/puma/public_html/19_2_3/4.pdf
Brlek, S.: Enumeration of factors in the Thue-Morse word. Disc. Appl. Math. 24, 83–96 (1989)
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., 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)
Büchi, J.R.: Weak secord-order arithmetic and finite automata. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 6, 66–92 (1960); reprinted in Mac Lane, S., Siefkes, D. (eds.): The Collected Works of J. Richard Büchi, pp. 398–424. Springer (1990)
Büchi, J.R.: On a decision method in restricted second order arithmetic. In: Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.), pp. 1–11. Stanford University Press (1962)
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. Theoret. Comput. Sci. 411, 3932–3937 (2010)
Carpi, A., Maggi, C.: On synchronized sequences and their separators. RAIRO Inform. Théor. App. 35, 513–524 (2001)
Charlier, E., Rampersad, N., Shallit, J.: Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comp. Sci. 23, 1035–1066 (2012)
Cobham, A.: Uniform tag sequences. Math. Systems Theory 6, 164–192 (1972)
Currie, J.: Lexicographically least words in the orbit closure of the Rudin-Shapiro word. Theoret. Comput. Sci. 41, 4742–4746 (2011)
Currie, J.D., Saari, K.: Least periods of factors of infinite words. RAIRO Inform. Théor. App. 43, 165–178 (2009)
Dekking, F.M., Mendès France, M., van der Poorten, A.J.: Folds! Math. Intelligencer 4, 130–138, 173–181, 190–195 (1982); erratum 5, 5 (1983)
Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98, 21–51 (1961)
Euwe, M.: Mengentheoretische Betrachtungen über das Schachspiel. Proc. Konin. Akad. Wetenschappen, Amsterdam 32, 633–642 (1929)
Goč, D., Henshall, D., Shallit, J.: Automatic theorem-proving in combinatorics on words. In: Moreira, N., Reis, R. (eds.) CIAA 2012. LNCS, vol. 7381, pp. 180–191. Springer, Heidelberg (2012)
Goč, D., Mousavi, H., Shallit, J.: On the number of unbordered factors. In: Dediu, A.-H., Martín-Vide, C., Truthe, B. (eds.) LATA 2013. LNCS, vol. 7810, pp. 299–310. Springer, Heidelberg (2013)
Goč, D., Schaeffer, L., Shallit, J.: The subword complexity of k-automatic sequences is k-synchronized (2012) (submitted), preprint available at http://arxiv.org/abs/1206.5352
Goč, D., Schaeffer, L., Shallit, J.: A new approach to the paperfolding sequences (manuscript in preparation, 2013)
Hodgson, B.: Décidabilité par automate fini. Ann. Sci. Math. Québec 7, 39–57 (1983)
Honkala, J.: A decision method for the recognizability of sets defined by number systems. RAIRO Inform. Théor. App. 20, 395–403 (1986)
Klaedtke, F.: Bounds on the automata size for Presburger arithmetic. ACM Trans. Comput. Logic 9(2), article 11 (March 2008), http://doi.acm.org/10.1145/1342991.1342995
Leech, J.: A problem on strings of beads. Math. Gazette 41, 277–278 (1957)
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 (2005)
Luca, A.D., Varricchio, S.: Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theoret. Comput. Sci. 63, 333–348 (1989)
Marsault, V., Sakarovitch, J.: Ultimate periodicity of b-recognisable sets: a quasilinear procedure (2013), preprint available at http://arxiv.org/abs/1301.2691
Morse, M.: Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc. 22, 84–100 (1921)
Morse, M., Hedlund, G.A.: Symbolic dynamics. Amer. J. Math. 60, 815–866 (1938)
Pansiot, J.J.: The Morse sequence and iterated morphisms. Inform. Process. Lett. 12, 68–70 (1981)
Presburger, M.: Über die Volständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Sparawozdanie z I Kongresu Matematyków Krajów Slowianskich, Warsaw, pp. 92–101 (1929)
Presburger, M.: On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation. Hist. Phil. Logic 12, 225–233 (1991)
Prouhet, E.: Mémoire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris 33, 225 (1851)
Rowland, E., Shallit, J.: k-automatic sets of rational numbers. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 490–501. Springer, Heidelberg (2012)
Schaeffer, L.: Abelian powers in automatic sequences are not always automatic. Talk at CanadaDAM 2013 Conference, St. John’s, Newfoundland (June 2013)
Schaeffer, L., Shallit, J.: The critical exponent is computable for automatic sequences. Int. J. Found. Comput. Sci. (2012) (to appear)
Shallit, J.: The critical exponent is computable for automatic sequences. In: Ambroz, P., Holub, S., Másaková, Z. (eds.) Proceedings 8th International Conference Words 2011. Elect. Proc. Theor. Comput. Sci, vol. 63, pp. 231–239 (2011)
Sipser, M.: Introduction to the Theory of Computation. Cengage Learning, 3rd edn. (2013)
Thue, A.: Über unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 7, 1–22 (1906); reprinted in Nagell, T. (ed.): Selected Mathematical Papers of Axel Thue, Universitetsforlaget, Oslo, pp. 139–158 (1977)
Thue, A.: Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl 1, 1–67 (1912); reprinted in Nagell, T. (ed.): Selected Mathematical Papers of Axel Thue, Universitetsforlaget, Oslo, pp. 413–478 (1977)
Wah, A., Picciotto, H.: Algebra: Themes, Tools, Concepts. Creative Publications, Mountain View (1994), http://www.mathedpage.org/attc/attc.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shallit, J. (2013). Decidability and Enumeration for Automatic Sequences: A Survey. In: Bulatov, A.A., Shur, A.M. (eds) Computer Science – Theory and Applications. CSR 2013. Lecture Notes in Computer Science, vol 7913. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38536-0_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-38536-0_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38535-3
Online ISBN: 978-3-642-38536-0
eBook Packages: Computer ScienceComputer Science (R0)