Skip to main content
SpringerLink
Log in

Automata and automatic sequences

  • Conference paper
Beyond Quasicrystals

Part of the book series: Centre de Physique des Houches ((LHWINTER,volume 3))

Abstract

In the following pages we discuss infinite sequences defined on a finite alphabet, and more specially those which are generated by finite automata. We have divided our paper into seven parts which are more or less self-contained. Needless to say, we feel that the order we propose is the most natural one. References appear at the end of each one of the parts which implies some redundancy.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Allouche J.-P., Note on the cyclic towers of Hanoi, Theoret. Comput. Sci. 123 (1994) 3–7.

    Article  MathSciNet  MATH  Google Scholar 

  2. Allouche J.-P., Arnold A., Berstel J., Brlek S., Jockusch W., Plouffe S., Sagan B. E., A relative of the Thue-Morse sequence, Discrete Math. (1994) to appear.

    Google Scholar 

  3. Allouche J.-P., Astoorian D., Randall J., Shallit J., Morphisms, square-free strings and the tower of Hanoi puzzle, Amer. Math. Monthly 101 (1994) 651–658.

    Article  MathSciNet  Google Scholar 

  4. Allouche J.-P., Bétréma J., Shallit J., Sur des points fixes de morphismes d’un monoïde libre, RAIRO, Informatique Théorique et Applications 23 (1989) 235–249.

    Google Scholar 

  5. Allouche J.-P., Cosnard M., Itération de fonctions unimodales et suites engendrées par automates, C. R. Acad. Sci., Paris, Série A 296 (1983) 159–162.

    MathSciNet  MATH  Google Scholar 

  6. Allouche J.-P., Dress F., Tours de Han oï et automates, KAIRO, Informatique Théorique et Applications 24 (1990) 1-15.

    Google Scholar 

  7. Allouche J.-P., Johnson T., Finite automata and morphisms in assisted musical composition, J. New Music Research 24 (1995) to appear.

    Google Scholar 

  8. Berstel J., Sur la construction de mots sans carré, Séminaire de Théorie des Nombres de Bordeaux, Exposé 18 (1978–1979) 1801–1815.

    Google Scholar 

  9. Berthé V., this volume.

    Google Scholar 

  10. Blanchard A., Mendès France M., Symétrie et transcendance, Bull. Sci. Math. 106 (1982) 325–335.

    MATH  Google Scholar 

  11. Bruyère V., Hansel G., Michaux C., Villemaire R., Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. 1 (1994) 191–238.

    MATH  Google Scholar 

  12. Carpi A., Repetitions in the Kolakoski sequence, Bull. EATCS 50 (1993) 194–196.

    Google Scholar 

  13. Cobham A., On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969) 186–192.

    Article  MathSciNet  MATH  Google Scholar 

  14. Cobham A., Uniform tag sequences, Math. Systems Theory 6 (1972) 164–192.

    Article  MathSciNet  MATH  Google Scholar 

  15. Collet P., Eckmann J.-P., Iterated maps on the interval as dynamical systems ( Progress in Physics, Birkhäuser, 1980 ).

    MATH  Google Scholar 

  16. Culik H. K., Karhumäki J., Lepisö A., Alternating iteration of morphisms and the Kolakoski sequence, in: Lindenmayer systems: impacts in theoretical computer science, computer graphics and developmental biology, G. Rozenberg and A. Salomaa Eds (Springer Verlag, 1992 ) p. 93–103.

    Google Scholar 

  17. Culik II K., Karhumäki J., Iterative devices generating infinite words, in: STACS 1992: 9th Annual Symposium on Theoretical Aspects of Computer Science, A. Finkel and M. Jantzen Eds (Lecture Notes in Computer Science, 577, 1992 ) p. 531–543.

    Google Scholar 

  18. Davis C., Knuth D. E., Number representations and dragon curves, J. Recr. Math. 3 (1970) 161–181; 133–149.

    Google Scholar 

  19. Dekking F. M., Regularity and irregularity of sequences generated by automata, Séminaire de Théorie des Nombres de Bordeaux, Exposé 9 (1979–1980) 901–910.

    Google Scholar 

  20. Dekking F. M., On the structure of self–generating sequences, Séminaire de Théorie des Nombres de Bordeaux, Exposé 31 (1980–1981) 31–01–3106.

    Google Scholar 

  21. Dekking F. M., Mendès France M., van der Poorten A., FOLDS!, Math. Intel]. 4 (1982) 130–138, 173–181 and 190–195.

    Google Scholar 

  22. Hansel G., private communication.

    Google Scholar 

  23. Hinz A. M., The tower of Hanoi, Enseign. Math. 35 (1989) 289–321.

    MathSciNet  MATH  Google Scholar 

  24. Jonker L., Periodic orbits and kneading invariants, Proc. London Math. Soc. 39 (1979) 428–450.

    Article  MathSciNet  MATH  Google Scholar 

  25. Kolakoski W., Self-generating runs, Prob. 5304, sol. in Amer. Math. Monthly 73 (1966) 681–682.

    Article  MathSciNet  Google Scholar 

  26. Meyer Y., this volume.

    Google Scholar 

  27. Morse M., Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc. 2 (1921) 84–100.

    Article  MathSciNet  Google Scholar 

  28. Nun G., How much Thue is Kolakoski?, Bull. EATCS 49 (1993) 183185.

    Google Scholar 

  29. Prouhet E., C. R. Acad. Sci., Paris 33 (1851) 225.

    Google Scholar 

  30. Queffélec M., this volume.

    Google Scholar 

  31. Rudin W., Some theorems on Fourier coefficients, Proc. Amer. Math. Soc. 10 (1959) 855–859.

    Article  MathSciNet  MATH  Google Scholar 

  32. Shallit J., A generalization of automatic sequences, Theoret. Comput. Sci. 61 (1988) 1–16.

    Article  MathSciNet  MATH  Google Scholar 

  33. Shapiro H. S., Extremal problems for polynomial and power series (Thesis, M.I.T., 1951 ).

    Google Scholar 

  34. Shechtman D., Blech I. A., Gratias D., Cahn J. W., Metallic phase with long-range orientational order and no translational symmetry, Phys. Rev. Letter 53 (1984) 1951–1953.

    Article  ADS  Google Scholar 

  35. Tamura J., Some problems having their origin in the power series z[CY21, in: Reports of the meeting on analytic theory of numbers and related topics, ( Gakushuin University, 1992 ), p. 190–212.

    Google Scholar 

  36. Thue A., Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. I. Mat. Kl. Christiana 7 (1906) 1–22.

    Google Scholar 

  37. Thue A., Lage gleicher Teile gewisse Zeichenreihen, Norske vid. Selsk. Skr. I. Mat. KI. Christiana 1 (1912) 1–67.

    Google Scholar 

  38. Weakley W. D., On the number of C°°-words of each length, J. Combin. Theory Ser. A 51 (1989) 55–62.

    Article  MathSciNet  MATH  Google Scholar 

  39. Wen Z.-X., Wen Z.-Y., Remarques sur la suite engendrée par des substitutions composées, Ann. Fac. Sci. Toulouse Math. 9 (1988) 55–63.

    Article  MathSciNet  MATH  Google Scholar 

  40. Berthé V., this volume.

    Google Scholar 

  41. Blanchard A., Mendès France M., Symétrie et transcendance, Bull. Sci. Math. 106 (1982) 325–335.

    MathSciNet  MATH  Google Scholar 

  42. Davis C., Knuth D. E., Number representations and dragon curves, J. Recr. Math. 3 (1970) 161–181; 133–149.

    Google Scholar 

  43. Dekking F. M., Mendès France M., Uniform distribution modulo one: a geometrical viewpoint, J. reine angew. Math. 129 (1981) 143–153.

    Google Scholar 

  44. Dekking F. M., Mendès France M., van der Poorten A., FOLDS!, Math. Intel]. 4 (1982) 130–138, 173–181 and 190–195.

    Google Scholar 

  45. Kmosek M., Report by A. Schinzel, Oberwolfach 28 may - 2 june 1979.

    Google Scholar 

  46. Mahler K., Ein Analog zu einem Schneiderschen Satz, Proc. Akad. Wetensch. Amsterdam 39 (1936) 633–640 and 729–737.

    Google Scholar 

  47. Mandelbrot B., Les objets fractals (Nouvelle Bibliothèque Scient. Flammarion, Paris, 1975 ).

    Google Scholar 

  48. Mendès France M., Sur les fractions continues limitées, Acta Arith. 2 (1973) 207–215.

    Google Scholar 

  49. Mendès France M., Paper folding, space-filling curves and Rudin-Shapiro sequences, Contempory Mathematics 9 (1982) 85–95.

    Article  MATH  Google Scholar 

  50. Mendès France M., The Planck constant of a curve, in: Fractal Geometry and Analysis J. Belair and S. Dubuc Eds ( Kluwer Acad. Publ., 1991 ) p. 325–366

    Google Scholar 

  51. Mendès France M., Tenenbaum G., Dimension des courbes planes, papiers pliés et suites de Rudin-Shapiro, Bull. Soc. math. France 109 (1981) 207–215.

    MathSciNet  MATH  Google Scholar 

  52. Shallit J., Simple continued fractions for some irrational numbers J. Number Theory 11 (1979) 209–217.

    Article  MathSciNet  MATH  Google Scholar 

  53. Allouche J.-P., Suites infinies à répétitions bornées, Séminaire de Théorie des Nombres de Bordeaux, Exposé 20 (1983–1984) 2001–2011.

    Google Scholar 

  54. Allouche J.-P., Bousquet-Mélou M., Facteurs des suites de Rudin-Shapiro généralisées, Bull. Belg. Math. Soc. 1 (1994) 145–164.

    MATH  Google Scholar 

  55. Allouche J.-P., von Haeseler F., Peitgen H.-O., Skordev G., Linear cellular automata, finite automata and Pascal’s triangle, Discrete App/. Math. (1995) to appear.

    Google Scholar 

  56. Allouche J.-P., Reder C., Oscillations spatio-temporelles engendrées par un automate cellulaire, Discrete Appl. Math. 8 (1984) 215–254.

    Article  MathSciNet  MATH  Google Scholar 

  57. Allouche J.-P., Salon O., Robinson tilings and 2-dimensional automata, in: Quasicrystals, Networks and Molecules of Fivefold Symmetry, I. Hargittai Ed (VCH Publishers Inc., 1990 ) p. 97–105.

    Google Scholar 

  58. Axel F., Allouche J.-P., Kléman M., Mendès France M., Peyrière J., Vibrational modes in a one dimensional “quasi-alloy”, the Morse case, J. Phys. Colloques, 1986, Workshop on aperiodic crystals, Les Houches (1986) 11–20.

    Google Scholar 

  59. Axel F., Peyrière J., Spectrum and extended states in a harmonic chain with controlled disorder: effects of the Thue-Morse symmetry, J. Stat. Phys. 57 (1989) 1013–1047.

    MATH  Google Scholar 

  60. Berstel J., Sur la construction de mots sans carré, Séminaire de Théorie des Nombres de Bordeaux, Exposé 18 (1978–1979) 1801–1815.

    Google Scholar 

  61. Bovier A., Ghez J.-M., Spectral properties of one-dimensional Schrödinger operators with potentials generated by substitutions, Comm. Math. Phys. 158 (1993) 45–66.

    Article  MathSciNet  ADS  MATH  Google Scholar 

  62. Burks A. W., Essays on cellular automata (University of Illinois Press, 1970 ).

    Google Scholar 

  63. Cassaigne J., Motifs évitables et régularités dans les mots (Thèse, Université Paris 6 /7, 1994 ).

    Google Scholar 

  64. Goles E., Martínez S., Neural and automata networks (Mathematics and its applications, 58, 1991 ).

    Google Scholar 

  65. Mignosi F., Pirillo G., Repetitions in the Fibonacci infinite word, RAIRO, Informatique Théorique et Applications 26 (1992) 199–204.

    MathSciNet  MATH  Google Scholar 

  66. Salon O., Suites automatiques à multi–indices, Séminaire de Théorie des Nombres de Bordeaux, Exposé. (1986–1987) 4–01–4–27; followed by an appendix by Shallit J., 4–29A–4–36A.

    Google Scholar 

  67. Salon O., Suites automatiques à multi-indices et algébricité, C. R. Acad. Sci. Paris, Série 1305 (1987) 501–504.

    MathSciNet  Google Scholar 

  68. Shallit J., Stolfi J., Two methods for generating fractals, Comp. and Graphics 13 (1989) 185–191.

    Article  Google Scholar 

  69. Süt6 A., this volume.

    Google Scholar 

  70. Thue A., Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. I. Mat. KI. Christiana 7 (1906) 1–22.

    Google Scholar 

  71. Thue A., Lage gleicher Teile gewisse Zeichenreihen, Norske vid. Selsk. Skr. I. Mat. KI. Christiana 1 (1912) 1–67.

    Google Scholar 

  72. Bass J., Suites uniformément denses, moyennes trigonométriques, fonctions pseudo-aléatoires, Bull. Soc. math. France 87 (1959) 1–69.

    MathSciNet  MATH  Google Scholar 

  73. Bertrandias J.-P., Espaces de fonctions bornées et continues en moyenne asymptotique d’ordre p, (Thèse), Bull. Soc. math. France, Mémoire 5 (1966) 3–106.

    Google Scholar 

  74. Coquet J., Kamae T., Mendès France M., Sur la mesure spectrale de certaines suites arithmétiques, Bull. Soc. math. France 105 (1977) 369384.

    Google Scholar 

  75. Kakutani S., Strictly ergodic symbolic dynamical systems, in: Proceedings of the 6th Berkeley symposium on mathematical statistics and probability [1970 Berkeley] vol. 2 ( Berkeley, University of California Press, 1972 ) p. 319–326.

    Google Scholar 

  76. Mahler K., On the translation properties of a simple class of arithmetical functions, Jour. Math. and Phys. 6 (1927) 158–163.

    MATH  Google Scholar 

  77. Mendès France M., van der Poorten A. J., Arithmetic and analytic properties of paperfolding sequences (dedicated to Kurt Mahler), Bull. Austr. Math. Soc. 24 (1981) 123–131.

    MATH  Google Scholar 

  78. Meyer Y., Le spectre de Wiener, Studia Mathematica 27 (1966) 189–201.

    MATH  Google Scholar 

  79. Queffélec M., this volume.

    Google Scholar 

  80. Wiener N., Generalized harmonic analysis, Acta Math. 55 (1930) 117–258.

    Article  MathSciNet  MATH  Google Scholar 

  81. Alessandri P., Codage des rotations, Mémoire de D. E. A. (Université Claude Bernard, Lyon I, 1993 ).

    Google Scholar 

  82. Allouche J.-P., The number of factors in a paperfolding sequence, Bull. Austr. Math. Soc. 46 (1992) 23–32.

    Article  MathSciNet  MATH  Google Scholar 

  83. Allouche J.-P., Bacher R., Toeplitz sequences, paperfolding, Hanoi towers and progression-free sequences of integers, Enseign. Math. 38 (1992) 315–327.

    MathSciNet  MATH  Google Scholar 

  84. Allouche J.-P., Bousquet-Mélou M., Facteurs des suites de Rudin-Shapiro généralisées, Bull. Belg. Math. Soc. 1 (1994) 145–164.

    MATH  Google Scholar 

  85. Allouche J.-P., Bousquet-Mélou M., Canonical positions for the factors in the paperfolding sequences, Theoret. Comput. Sci. 129 (1994) 263–278.

    MATH  Google Scholar 

  86. Allouche J.-P., Shallit J., Complexité des suites de Rudin-Shapiro généralisées, Journal de Théorie des Nombres de Bordeaux 5 (1993) 283–302.

    Article  MathSciNet  MATH  Google Scholar 

  87. Arnoux P., Mauduit C., Meigniez G., Sur la complexité de certaines suites arithmétiques, in preparation.

    Google Scholar 

  88. Arnoux P., Mauduit C., Shiokawa I., Tamura J. I., Complexity of sequences defined by billiards in the cube, Bull. Soc. math. France 122 (1994) 1–12.

    MathSciNet  MATH  Google Scholar 

  89. Arnoux P., Mauduit C., Shiokawa I., Tamura J. I., Rauzy’s conjecture on the cubic billiards, Tokyo J. Math. 17 (1994) 211–218.

    Article  MathSciNet  MATH  Google Scholar 

  90. Arnoux P., Rauzy G., Représentation géométrique de suites de complexité 2n + 1, Bull. Soc. math. France 119 (1991) 199–215.

    MathSciNet  MATH  Google Scholar 

  91. Berstel J., Séébold P., Mots de Sturm - un survol, Preprint (1994).

    Google Scholar 

  92. Berthé V., this volume.

    Google Scholar 

  93. Brlek S., Enumeration of factors in the Thue-Morse word, Discrete Appl. Math. 24 (1989) 83–96.

    Article  MathSciNet  MATH  Google Scholar 

  94. Cobham A., Uniform tag sequences, Math. Systems Theory 6 (1972) 164–192.

    Article  MathSciNet  MATH  Google Scholar 

  95. Coven E. M., Hedlund G. A., Sequences with minimal block growth, Math. Systems Theory 7 (1973) 138–153.

    Article  MathSciNet  MATH  Google Scholar 

  96. Crisp D., Moran W., Pollington A., Shiue P., Substitution invariant cutting sequences, Journal de Théorie des Nombres de Bordeaux 5 (1993) 123–137.

    Article  MathSciNet  MATH  Google Scholar 

  97. Dekking F. M., On the structure of self–generating sequences, Séminaire de Théorie des Nombres de Bordeaux, Exposé 31 (1980–1981) 31–01–3106.

    Google Scholar 

  98. Ferenczi S., Les transformations de Chacon: combinatoire, structure géométrique, lien avec les systèmes de complexité 2n + 1, Bull. Soc. math. France (1995) to appear.

    Google Scholar 

  99. Hubert P., Complexité des suites définies par des billards rationnels, Bull. Soc. math. France (1995) to appear.

    Google Scholar 

  100. Koskas M., Complexity functions for some Toeplitz sequences, Theoret. Comput. Sci. (1995) to appear.

    Google Scholar 

  101. Li M., Vitânyi P., Kolmogorov complexity and its applications, in: Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, J. van Leeuwen Ed (MIT Press, 1990 ) p. 187–254.

    Google Scholar 

  102. de Luca A., Varricchio S., On the factors of the Thue-Morse word on three symbols, Information Processing Letters 27 (1988) 281–285.

    Article  MathSciNet  MATH  Google Scholar 

  103. de Luca A., Varricchio S., Some combinatorial properties of the ThueMorse sequence, Theoret. Comput. Sci. 63 (1989) 333–348.

    Article  MathSciNet  MATH  Google Scholar 

  104. Morse M., Hedlund G. A., Symbolic Dynamics, Amer. J. Math. 60 (1938) 815–866.

    Article  MathSciNet  Google Scholar 

  105. Morse M., Hedlund G. A., Symbolic Dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940) 1–42.

    Article  MathSciNet  Google Scholar 

  106. Mossé M., Notions de reconnaissabilité pour les substitutions et complexité des suites automatiques, Prépublication du LMD 93–21 (1993).

    Google Scholar 

  107. Pansiot J.-J., Bornes inférieures sur la complexité des facteurs des mots infinis engendrés par morphismes itérés, Lecture Notes in Computer Science 166 (1984) 230–240.

    Article  MathSciNet  Google Scholar 

  108. Pansiot J.-J., Complexité des facteurs des mots infinis engendrés par morphismes itérés, Lecture Notes in Computer Science 172 (1984) 380389.

    Google Scholar 

  109. Rauzy G., Suites à, termes dans un alphabet fini, Séminaire de Théorie des Nombres de Bordeaux, Exposé 25 (1982–1983) 2501–2516.

    Google Scholar 

  110. Rote G., Sequences with subword complexity 2n, J. Number Theory 46 (1994) 196–213.

    Article  MathSciNet  MATH  Google Scholar 

  111. Santini M.-L., Échanges de trois intervalles (Thèse, Université Aix-Marseille I I, 1994 ).

    Google Scholar 

  112. Loraud N., Contribution à l’étude de l’opacité d’un automate, Work in progress.

    Google Scholar 

  113. Mendes France M., Opacity of an automaton. Application to the inhomogeneous Ising chin, Comm. Math. Phys. 139 (1991) 341–352.

    Article  MathSciNet  ADS  MATH  Google Scholar 

  114. Allouche J.-P., Mendès France M., Quasicrystal Ising chain and automata theory, J. Stat. Phys. 42 (1986) 809–821.

    Article  ADS  MATH  Google Scholar 

  115. Baxter R. J., Exactly solved models in statistical mechanics (Academic Press, 1982 ).

    Google Scholar 

  116. Biggs N. L., Interaction models, London Mathematical Society (Lecture Note Series, 30, Cambridge University Press, 1977 ).

    Google Scholar 

  117. Cipra B. A., An introduction to the Ising model, Amer. Math. Monthly 94 (1987) 937–959.

    Article  MathSciNet  Google Scholar 

  118. Dekking F. M., Iteration of a map by an automaton, Discrete Math. 126 (1994) 81–86.

    MathSciNet  MATH  Google Scholar 

  119. Derrida B., Products of random matrices and one dimensional disordered systems in: Nonlinear Equations in Field Theory (Lectures Notes in Physics, 226, Springer-Verlag, 1985 ).

    Google Scholar 

  120. Ising E., Beitrag zur Theorie der Ferromagnetismus, Z. Physik 31 (1925) 253–258.

    Article  ADS  Google Scholar 

  121. Kamae T., Mendès France M., A continuous family of automata: the Ising automata, Submitted (1994).

    Google Scholar 

  122. Mendès France M., Opacity of an automaton. Application to the inhomogeneous Ising chain, Comm. Math. Phys. 139 (1991) 341–352.

    Article  ADS  MATH  Google Scholar 

  123. Thompson C. J., Mathematical statistical mechanics (Princeton University Press, 1972 ).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CNRS, LMD, Luminy Case 930, F-13288, Marseille Cedex 9, France

    J.-P. Allouche

  2. Mathématiques, Université Bordeaux I, 351 cours de la Libération, F-33405, Talence Cedex, France

    M. Mendès France

Authors
  1. J.-P. Allouche
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Mendès France
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Université Paris VII-Denis Diderot, France

    Françoise Axel

  2. CECN-CNRS, Vitry, France

    Denis Gratias

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Allouche, JP., France, M.M. (1995). Automata and automatic sequences. In: Axel, F., Gratias, D. (eds) Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-03130-8_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-03130-8_11

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-59251-8

  • Online ISBN: 978-3-662-03130-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation