×

The asymptotic distribution of elements in automatic sequences. (English) Zbl 1028.68081

Summary: In an automatic sequence an element need not have an asymptotic density. In this paper a necessary and sufficient criterion is proved for the existence of the asymptotic density of a given element. If it does not exist the asymptotic distribution of the element can be described in terms of a function \(H\) whose graph is self-similar. An algorithm is given to decide whether \(H\) is piecewise continuously differentiable, and in this case it can be computed effectively. Finally, it is shown that the \(H^{\infty}\)-density of an element in an automatic sequence always exists and equals its logarithmic density.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J.-P., Automates finis en théorie des nombres, Expo. Math., 5, 239-266 (1987) · Zbl 0641.10041
[2] Allouche, J.-P.; Mendès France, M., Automata and automatic sequences, (Axel, F.; Gratias, D., Beyond Quasicrystals, Les Éditions de Physique (1995), Springer: Springer Berlin), 293-367 · Zbl 0881.11026
[3] Allouche, J.-P.; Mendès France, M.; Peyrière, J., Automatic Dirichlet series, J. Number Theory, 81, 359-373 (2000) · Zbl 0971.11006
[4] Christol, G.; Kamae, T.; Mendès France, M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. Math. France, 108, 401-419 (1980) · Zbl 0472.10035
[5] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[6] M. Dekking, M. Mendès France, A. van der Poorten, Folds!, Math. Intelligencer 4 (1982) 130-138, 173-181, 190-195.; M. Dekking, M. Mendès France, A. van der Poorten, Folds!, Math. Intelligencer 4 (1982) 130-138, 173-181, 190-195. · Zbl 0493.10001
[7] Dumont, J.-M.; Thomas, A., Systèmes de numération et fonctions fractales relatifs aux substitutions, Theoret. Comput. Sci., 65, 153-169 (1989) · Zbl 0679.10010
[8] Dumont, J.-M.; Thomas, A., Digital sum problems and substitutions on a finite alphabet, J. Number Theory, 39, 351-366 (1991) · Zbl 0736.11007
[9] R.E. Edwards, Fourier Series, vols. I, II, Holt, Rinehart and Winston, New York, 1967.; R.E. Edwards, Fourier Series, vols. I, II, Holt, Rinehart and Winston, New York, 1967.
[10] Flehinger, J., On the probability that a random integer has initial digit \(A\), Am. Math. Monthly, 73, 1056-1061 (1966) · Zbl 0147.17502
[11] F.R. Gantmacher, Theory of Matrices, 2 vols. Chelsea, New York, 1960.; F.R. Gantmacher, Theory of Matrices, 2 vols. Chelsea, New York, 1960.
[12] Schatte, P., Some estimates of the \(H_∞\)-uniform distribution, Mh. Math., 103, 233-240 (1987) · Zbl 0624.10040
[13] Schatte, P., On Benford’s law to variable base, Statist. Probab. Lett., 37, 391-397 (1998) · Zbl 0908.60018
[14] Schatte, P., Brief an den Herausgeber, DMV-Mitteilungen, 2, 6-7 (2001)
[15] Seneta, E., Non-negative Matrices and Markov Chains, Springer Series in Statistics (1981), Springer: Springer New York · Zbl 0471.60001
[16] Shallit, J., Number theory and formal languages, (Hejhal, D. A.; Friedman, J.; Gutzwiller, M. C.; Odlyzko, A. M., Emerging Applications of Number Theory. Emerging Applications of Number Theory, The IMA Volumes in Mathematics and its Applications, Vol. 109 (1999), Springer: Springer New York), 547-570 · Zbl 0973.11032
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.