Complexity of infinite words generated by countable -automata
- [1] IML Campus de Luminy, case 907 13288 Marseille Cedex 09 (France)
Annales de l’institut Fourier (2006)
- Volume: 56, Issue: 7, page 2463-2491
- ISSN: 0373-0956
Access Full Article
topAbstract
topHow to cite
topReferences
top- J.-P. Allouche, Sur la complexité des suites infinies, Bull. Belg. Math. Soc. Simon Stevin 1 (1994), 133-143 Zbl0803.68094MR1318964
- J.-P. Allouche, J. Shallit, Automatic sequences. Theory, applications, generalizations, (2003), Cambridge University Press, Cambridge Zbl1086.11015MR1997038
- J. Berstel, D. Perrin, Theory of codes, (1985), Academic Press Zbl0587.68066MR797069
- S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96 Zbl0683.20045MR1011264
- A. Cobham, Uniform-tag sequences, Math. Syst. Th. 6 (1972), 164-192 Zbl0253.02029MR457011
- A. Ehrenfeucht, K. P. Lee, G Rozenberg, Subword complexities of various classes of deterministic developmeltal languages without interactions, Math. Syst. Theoret. Comput. Science 63 (1975), 59-75 Zbl0316.68043MR388861
- S. Eilenberg, Automata, languages and machines, A (1974), Academic Press Zbl0317.94045
- S. Ferenczi, Substitution dynamical systems on infinite alphabets, (2006) Zbl1147.37007
- M. Lothaire, Combinatorics on words, 17 (1983), Cambridge University Press Zbl0874.20040MR675953
- M. Lothaire, Algebraic combinatorics on words, 90 (2002), Cambridge University Press Zbl1001.68093MR1905123
- C. Mauduit, Propriétés arithmétiques des substitutions et automates infinis, (2006) MR1476736
- C. Mauduit, A. Sárközy, On the arithmetic structure of the integers whose sum of digits is fixed, Acta Arithmetica LXXXI (1997), 145-173 Zbl0887.11008MR1456239
- B. Mossé, Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France 124 (1996), 329-346 Zbl0855.68072MR1414542
- J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming (Antwerp, 1984) 172 (1984), 380-389, Springer, Berlin Zbl0554.68053MR784265
- D. Perrin, J.-E. Pin, Mots infinis. Technical report 93.40, (1997), Laboratoire Informatique Théorique et Programmation. Institut Blaise Pascal
- D. Perrin, J.-E. Pin, Infinite words, Automata, Semigroups, Logic and Games, 141 (2004), Elsevier Zbl1094.68052
- N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, 1794 (2002), Springer-Verlag, Berlin Zbl1014.11015MR1970385
- M. Queffélec, Substitution dynamical systems-spectral analysis, 1294 (1987), Springer-Verlag, Berlin Zbl0642.28013MR924156
- G. Rozenberg, A. Salomaa (Eds), Handbook of formal language, (1997), Springer-Verlag Zbl0866.68057
Citations in EuDML Documents
top- Sébastien Ferenczi, Substitution dynamical systems on infinite alphabets
- Julien Cassaigne, Marion Le Gonidec, Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables
- Christian Mauduit, Propriétés arithmétiques des substitutions et automates infinis
- Marion Le Gonidec, Drunken man infinite words complexity