Mauduit, Christian Arithmetics properties of substitutions and infinite automata. (Propriétés arithmétiques des substitutions et automates infinis.) (French. English summary) Zbl 1147.11016 Ann. Inst. Fourier 56, No. 7, 2525-2549 (2006). The author studies arithmetical and statistical properties of infinite words and sequences of integers generated by a substitution on an infinite denumerable alphabet or by a deterministic automata with an infinite denumerable set of states. In particular, he proves that if \(u\) is a sequence of integers generated by an automaton whose associated graph represents a random walk with zero average on a \(d\)-dimensional lattice, then the sequence \((n\alpha)_{ n\in u }\) is uniformly distributed modulo 1 if and only if \(\alpha \in \mathbb R \setminus \mathbb Q\). Reviewer: Olaf Ninnemann (Berlin) Cited in 14 Documents MSC: 11B85 Automata sequences 68Q45 Formal languages and automata 68R15 Combinatorics on words Keywords:infinite words; substitutions; automata; uniform distribution modulo 1 PDFBibTeX XMLCite \textit{C. Mauduit}, Ann. Inst. Fourier 56, No. 7, 2525--2549 (2006; Zbl 1147.11016) Full Text: DOI Numdam EuDML References: [1] Allouche, Jean-Paul; Shallit, J., Automatic sequences. Theory, applications, generalizations (2003) · Zbl 1086.11015 [2] Banderier, Cyril; Bousquet-Mélou, Mireille; Denise, Alain; Flajolet, Philippe; Gardy, Danièle; Gouyou-Beauchamps, Dominique, Generating functions of generating trees, Discrete Mathematics, 246, 1-3, 29-55 (2002) · Zbl 0997.05007 [3] Banderier, Cyril; Flajolet, Philippe, Basic analytic combinatorics of directed lattice paths, Theoretical Computer Science, 281, 1-2, 37-80 (2002) · Zbl 0996.68126 [4] Banks, W.; Conlitti, A.; Shparlinski, I. E., Character sums over integers with restricted g-ary digits, Illinois J. Math., 46, 819-836 (2002) · Zbl 1026.11068 [5] Banks, W.; Shparlinski, I. E., Arithmetic properties of numbers with restricted digits, Acta Arithmetica, 112, 313-332 (2004) · Zbl 1049.11003 [6] Cassaigne, Julien, Complexité et facteurs spéciaux, Bull. Belg. Math. Soc., 4, 1, 67-88 (1997) · Zbl 0921.68065 [7] Caucal, D., A hierarchy of graph families · Zbl 0704.68072 [8] Cobham, A., On the base-dependence of sets of numbers recognizable by finite automata, Math. Syst. Theory, 3, 186-192 (1969) · Zbl 0179.02501 [9] Cobham, A., Uniform tag sequences, Math. Syst. Theory, 6, 164-192 (1972) · Zbl 0253.02029 [10] Coquet, J., On the uniform distribution modulo one of some subsequences of polynomial sequences, J. Number Theory, 10, 291-296 (1978) · Zbl 0382.10034 [11] Coquet, J., On the uniform distribution modulo one of some subsequences of polynomial sequences II,, J. Number Theory, 12, 244-250 (1980) · Zbl 0432.10026 [12] Coquet, J., Graphes connexes, représentation des entiers et équirépartition, J. Number Theory, 16, 363-375 (1983) · Zbl 0512.10041 [13] Dartyge, C.; Mauduit, C., Nombres presque premiers dont l’écriture en base r ne comporte pas certains chiffres, Journal of Number Theory, 81, 270-291 (2000) · Zbl 0957.11039 [14] Dartyge, C.; Mauduit, C., Ensembles de densité nulle contenant des entiers possédant au plus deux facteurs premiers, Journal of Number Theory, 91, 230-255 (2001) · Zbl 0988.11042 [15] Eilenberg, S., Automata, languages and machines, A (1974) · Zbl 0359.94067 [16] Erdős, P.; Mauduit, C.; Sárközy, A., On arithmetic properties of integers with missing digits, I, J. Number Theory, 70, 99-120 (1998) · Zbl 0923.11024 [17] Erdős, P.; Mauduit, C.; Sárközy, A., On arithmetic properties of integers with missing digits, II, Discrete Math., 200, 149-164 (1999) · Zbl 0945.11006 [18] Ferenczi, S., Substitution on infinite alphabet [19] Filaseta, M.; Konyagin, S. V., Squarefree values of polynomials all of whose coefficients are 0 and 1, Acta Arith., 74, 191-205 (1996) · Zbl 0854.11015 [20] Flajolet, P.; Sedgewick, R., Analytic combinatorics [21] Fouvry, E.; Mauduit, C., Sur les entiers dont la somme des chiffres est moyenne, J. Number Theory, 114, 135-152 (2005) · Zbl 1084.11045 [22] Gambaudo, J.-M.; Hubert, P.; Tisseur, P.; Vaienti (Eds), S., Dynamical systems : from crystal to chaos (2000) · Zbl 0946.00018 [23] Konyagin, S. V., Arithmetic properties of integers with missing digits : distribution in residue classes, Period. Math. Hungar., 42, 145-162 (2001) · Zbl 0980.11006 [24] Konyagin, S. V.; Mauduit, C.; Sárközy, A., On the number of prime factors of integers characterized by digit properties, Period. Math. Hungar., 40, 37-52 (2000) · Zbl 0963.11005 [25] Le Gonidec, M., Sur la complexité des mots infinis engendrés par des q-automates dénombrables · Zbl 1121.68090 [26] Mauduit, C., Automates finis et ensembles normaux, Ann. Inst. Fourier, 36, 1-25 (1986) · Zbl 0576.10026 [27] Mauduit, C., Sur l’ensemble normal des substitutions de longueur quelconque, J. Number Theory, 29, 235-250 (1988) · Zbl 0655.10053 [28] Mauduit, C., Caractérisation des ensembles normaux substitutifs, Invent. Math., 95, 133-147 (1989) · Zbl 0665.10035 [29] Minsky, M. L.; Papert, S., Unrecognizable sets of numbers, J. Assoc. Comput. Mach., 13, 281-286 (1966) · Zbl 0166.00601 [30] Pytheas Fogg, N., Substitutions in dynamicals, arithmetics and combinatorics (2002) · Zbl 1014.11015 [31] Queffelec, M., Substitution dynamical systems - Spectral analysis (1987) · Zbl 0642.28013 [32] Rauzy, G., Propriétés statistiques de suites arithmétiques (1976) · Zbl 0337.10036 [33] Ritchie, R. W., Finite automata and the set of squares, J. Assoc. Comput. Mach., 10, 528-531 (1963) · Zbl 0118.12601 [34] Spitzer, F., Principles of random walks, second edition, 34 (1976) · Zbl 0359.60003 [35] Thomas, W., A short introduction to infinite automata, \(5^{th}\) DLT 01 LNCS, 2295, 134-144 (2001) · Zbl 1073.68671 [36] Thomas, W., Constructing infinite graphs with a decidable monadic theory, \(28^{th}\) MFCS LNCS, 2747, 113-124 (2003) · Zbl 1124.03314 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.