×

On the pseudorandomness of automatic sequences. (English) Zbl 1419.11101

Summary: We study the pseudorandomness of automatic sequences in terms of well-distribution and correlation measure of order 2. We detect non-random behavior which can be derived either from the functional equations satisfied by their generating functions or from their generating finite automatons, respectively.

MSC:

11K45 Pseudo-random numbers; Monte Carlo methods
68R15 Combinatorics on words
68Q25 Analysis of algorithms and problem complexity
68Q70 Algebraic theory of languages and automata
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allouche, J.-P.: Finite automata and arithmetic. Séminaire Lotharingien de Combinatoire (Gerolfingen, 1993), 1-18, Prépubl. Inst. Rech. Math. Av., 1993/34, Univ. Louis Pasteur, Strasbourg (1993)
[2] Allouche, J.P., Shallit, J.: Automatic sequences. Theory, applications, generalizations. Cambridge University Press, Cambridge (2003) · Zbl 1086.11015 · doi:10.1017/CBO9780511546563
[3] Alon, N; Kohayakawa, Y; Mauduit, C; Moreira, CG; Rödl, V, Measures of pseudorandomness for finite sequences: typical values, Proc. Lond. Math. Soc., 95, 778-812, (2007) · Zbl 1124.68084 · doi:10.1112/plms/pdm027
[4] Christol, G, Ensembles presque periodiques \(k\)-reconnaissables, Theoret. Comput. Sci., 9, 141-145, (1979) · Zbl 0402.68044 · doi:10.1016/0304-3975(79)90011-2
[5] 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 · doi:10.24033/bsmf.1926
[6] Dorfer, G; Meidl, W; Winterhof, A, Counting functions and expected values for the lattice profile at \(n\), Finite Fields Appl., 10, 636-652, (2004) · Zbl 1077.11056 · doi:10.1016/j.ffa.2004.01.004
[7] Drmota, M.: Subsequences of automatic sequences and uniform distribution. In: Kritzer, P. (ed.) Uniform distribution and quasi-Monte Carlo methods, 87-104, Radon Ser. Comput. Appl Math., vol. 15. De Gruyter, Berlin (2014) · Zbl 1360.11056
[8] Everest, G., van der Poorten, A., Shparlinski, I., Ward, T.: Recurrence Sequences Mathematical Surveys and Monographs, vol. 104. American Mathematical Society, Providence (2003) · Zbl 1033.11006
[9] Gyarmati, K.: Measures of pseudorandomness. In: Charpin, P., Pott, A., Winterhof, A. (eds.) Finite fields and their applications Radon Series in Computational and Applied Mathematics, de Gruyter, pp 43-64 (2013) · Zbl 1304.11077
[10] Hofer, R., Winterhof, A.: Linear complexity and expansion complexity of some number theoretic sequences. In: Arithmetics in Finite Fields (WAIFI 2016). Lecture Notes in Computer Science, vol. 10064, pp 67-74. Springer, Cham (2017) · Zbl 1409.11138
[11] Mauduit, C; Sárközy, A, On finite pseudorandom binary sequences. I. measure of pseudorandomness, the Legendre symbol, Acta Arith., 82, 365-377, (1997) · Zbl 0886.11048 · doi:10.4064/aa-82-4-365-377
[12] Mauduit, C; Sárközy, A, On finite pseudorandom binary sequences. II. the champernowne, rudin-Shapiro, and thue-Morse sequences, a further construction, J. Number Theory, 73, 256-276, (1998) · Zbl 0916.11047 · doi:10.1006/jnth.1998.2286
[13] Mérai, L., Winterhof, A.: On the \(N\) th linear complexity of \(p\)-automatic sequences over 𝔽_{\(p\)}. Preprint (2016) · Zbl 0472.10035
[14] Niederreiter, H.: The Probabilistic Theory of Linear Complexity. Advances in Cryptology-EUROCRYPT ’88 (Davos, 1988), 191-209, Lecture Notes in Comput. Sci, vol. 330. Springer, Berlin (1988) · Zbl 0657.94009
[15] Niederreiter, H.: Sequences with almost perfect linear complexity profile. Advances in cryptology-EUROCRYPT ’87. In: Chaum, D., Price, W.L. (eds.) Lecture Notes in Computer Science, vol. 304, pp 37-51. Springer, Berlin (1988) · Zbl 1124.68084
[16] Sárközy, A, On finite pseudorandom binary sequences and their applications in cryptography, Tatra. Mt. Math. Publ., 37, 123-136, (2007) · Zbl 1240.11085
[17] Topuzoglu, A., Winterhof, A.: Pseudorandom Sequences. Topics in Geometry, Coding Theory and Cryptography, 135-166, Algebr Appl, vol. 6. Springer, Dordrecht (2007) · Zbl 1134.11030
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.