logo ANNALES DE L'INSTITUT FOURIER

With cedram.org
Table of contents for this issue | Previous article | Next article
Marion Le Gonidec
Sur la complexité de mots infinis engendrés par des $q$-automates dénombrables
(Complexity of infinite words generated by countable $q$-automata)
Annales de l'institut Fourier, 56 no. 7 (2006), p. 2463-2491, doi: 10.5802/aif.2246
Article PDF | Reviews MR 2290787 | Zbl 1121.68090 | 3 citations in Cedram
Class. Math.: 68R15, 11B85
Keywords: Infinite words, complexity, substitutions, automata

Résumé - Abstract

This article deals with combinatorial properties of infinite words generated by countable and deterministic $q$-automata of bounded degree. Those words can also be viewed as projections of fixed point of some substitutions of constant length on countable alphabet. We show that complexity function of such words is at most polynomial and, on some examples, the order of growth of this function is at most $n (\log n)^p$.

Bibliography

[1] J.-P. Allouche, “Sur la complexité des suites infinies”, Bull. Belg. Math. Soc. Simon Stevin 1 (1994) no. 2, p. 133-143 Article |  MR 1318964 |  Zbl 0803.68094
[2] J.-P. Allouche & J. Shallit, Automatic sequences. Theory, applications, generalizations, Cambridge University Press, Cambridge, 2003  MR 1997038 |  Zbl 01993704
[3] J. Berstel & D. Perrin, Theory of codes, Academic Press, 1985  MR 797069 |  Zbl 0587.68066
[4] S. Brlek, “Enumeration of factors in the Thue-Morse word”, Discrete Applied Math. 24 (1989), p. 83-96 Article |  MR 1011264 |  Zbl 0683.20045
[5] A. Cobham, “Uniform-tag sequences”, Math. Syst. Th. 6 (1972), p. 164-192 Article |  MR 457011 |  Zbl 0253.02029
[6] 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), p.  59-75  MR 388861 |  Zbl 0316.68043
[7] S. Eilenberg, Automata, languages and machines A, Academic Press, 1974  Zbl 0317.94045
[8] S. Ferenczi, “Substitution dynamical systems on infinite alphabets”, to appear in Ann. Inst. Fourier, 2006 Cedram
[9] M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and Its applications 17, Cambridge University Press, 1983  MR 675953 |  Zbl 0874.20040
[10] M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and Its applications 90, Cambridge University Press, 2002  MR 1905123 |  Zbl 1001.68093
[11] C. Mauduit, “Propriétés arithmétiques des substitutions et automates infinis”, to appear in Ann. Inst. Fourier, 2006 Cedram |  MR 1476736
[12] C. Mauduit & A. Sárközy, “On the arithmetic structure of the integers whose sum of digits is fixed”, Acta Arithmetica LXXXI (1997) no. 2, p.  145-173 Article |  MR 1456239 |  Zbl 0887.11008
[13] B. Mossé, “Reconnaissabilité des substitutions et complexité des suites automatiques”, Bull. Soc. Math. France 124 (1996) no. 2, p.  329-346 Numdam |  MR 1414542 |  Zbl 0855.68072
[14] J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming (Antwerp, 1984), Lecture Notes in Comput. Sci. 172, Springer, 1984, p.  380–389  MR 784265 |  Zbl 0554.68053
[15] D. Perrin & J.-E. Pin, Mots infinis. Technical report 93.40, Laboratoire Informatique Théorique et Programmation. Institut Blaise Pascal, 1997
[16] D. Perrin & J.-E. Pin, Infinite words, Automata, Semigroups, Logic and Games, Pure and Applied Mathematics 141, Elsevier, 2004  Zbl 02206109
[17] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics 1794, Springer-Verlag, Berlin, 2002, Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel  MR 1970385 |  Zbl 1014.11015
[18] M. Queffélec, Substitution dynamical systems-spectral analysis, Lecture Notes in Mathematics 1294, Springer-Verlag, Berlin, 1987  MR 924156 |  Zbl 0642.28013
[19] G. Rozenberg & A. Salomaa (Eds), Handbook of formal language, Springer-Verlag, 1997  Zbl 0866.68057
top