Le Gonidec, Marion On the complexity of infinite words generated by countable \(q\)-automata. (Sur la complexité de mots infinis engendrés par des \(q\)-automates dénombrables.) (French. English summary) Zbl 1121.68090 Ann. Inst. Fourier 56, No. 7, 2463-2491 (2006). Summary: 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 }\). Cited in 8 Documents MSC: 68R15 Combinatorics on words 11B85 Automata sequences 68Q45 Formal languages and automata Keywords:infinite words; complexity; substitutions; automata PDFBibTeX XMLCite \textit{M. Le Gonidec}, Ann. Inst. Fourier 56, No. 7, 2463--2491 (2006; Zbl 1121.68090) Full Text: DOI Numdam EuDML References: [1] Allouche, J.-P., Sur la complexité des suites infinies, Bull. Belg. Math. Soc. Simon Stevin, 1, 2, 133-143 (1994) · Zbl 0803.68094 [2] Allouche, J.-P.; Shallit, J., Automatic sequences. Theory, applications, generalizations (2003) · Zbl 1086.11015 [3] Berstel, J.; Perrin, D., Theory of codes (1985) · Zbl 0587.68066 [4] Brlek, S., Enumeration of factors in the Thue-Morse word, Discrete Applied Math., 24, 83-96 (1989) · Zbl 0683.20045 [5] Cobham, A., Uniform-tag sequences, Math. Syst. Th., 6, 164-192 (1972) · Zbl 0253.02029 [6] Ehrenfeucht, A.; Lee, K. P.; Rozenberg, G., Subword complexities of various classes of deterministic developmeltal languages without interactions, Math. Syst. Theoret. Comput. Science, 63, 59-75 (1975) · Zbl 0316.68043 [7] Eilenberg, S., Automata, languages and machines, A (1974) · Zbl 0317.94045 [8] Ferenczi, S., Substitution dynamical systems on infinite alphabets (2006) · Zbl 1147.37007 [9] Lothaire, M., Combinatorics on words, 17 (1983) · Zbl 0874.20040 [10] Lothaire, M., Algebraic combinatorics on words, 90 (2002) · Zbl 1001.68093 [11] Mauduit, C., Propriétés arithmétiques des substitutions et automates infinis (2006) · Zbl 1147.11016 [12] Mauduit, C.; Sárközy, A., On the arithmetic structure of the integers whose sum of digits is fixed, Acta Arithmetica, LXXXI, 2, 145-173 (1997) · Zbl 0887.11008 [13] Mossé, B., Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France, 124, 2, 329-346 (1996) · Zbl 0855.68072 [14] Pansiot, J.-J., Automata, languages and programming (Antwerp, 1984), 172, 380-389 (1984) · Zbl 0554.68053 [15] Perrin, D.; Pin, J.-E., Mots infinis. Technical report 93.40 (1997) [16] Perrin, D.; Pin, J.-E., Infinite words, Automata, Semigroups, Logic and Games, 141 (2004) · Zbl 1094.68052 [17] Pytheas Fogg, N., Substitutions in dynamics, arithmetics and combinatorics, 1794 (2002) · Zbl 1014.11015 [18] Queffélec, M., Substitution dynamical systems-spectral analysis, 1294 (1987) · Zbl 0642.28013 [19] Rozenberg, G.; Salomaa (Eds), A., Handbook of formal language (1997) · Zbl 0866.68057 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.