On the Maximum Order Complexity of Thue–Morse and Rudin–Shapiro Sequences along Polynomial Values

[1] ALLOUCHE, J.-P.—SHALLIT, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.10.1017/CBO9780511546563Search in Google Scholar

[2] ALON, N.—KOHAYAKAWA, Y.—MAUDUIT, C.—MOREIRA, C. G.—RÖDL, V.: Measures of pseudorandomness for finite sequences: typical values, Proc. Lond. Math. Soc. (3) 95 (2007), 778–812.10.1112/plms/pdm027Search in Google Scholar

[3] CHRISTOL, G.: Ensembles presque periodiques k-reconnaissables, Theoret. Comput. Sci. 9 (1979), 141–145.10.1016/0304-3975(79)90011-2Search in Google Scholar

[4] DIEM, C.: On the use of expansion series for stream ciphers, LMS J. Comput. Math. 15 (2012), 326–340.10.1112/S146115701200109XSearch in Google Scholar

[5] DRMOTA, M.—MAUDUIT, C.—RIVAT, J.: The sum-of-digits function of polynomial sequences, J.Lond. Math. Soc.(2) 84 (2011), 81–102.10.1112/jlms/jdr003Search in Google Scholar

[6] DRMOTA, M.—MAUDUIT, C.—RIVAT, J.: Normality along squares, J. Eur. Math. Soc. (JEMS) 21 (2019), 507–548.10.4171/JEMS/843Search in Google Scholar

[7] MAUDUIT, C.—RIVAT, J.: Rudin–Shapiro sequences along squares, Transactions of the Amer. Math. Soc. 370 (2018), 7899–7921.10.1090/tran/7210Search in Google Scholar

[8] 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 (1998), 256–276.10.1006/jnth.1998.2286Search in Google Scholar

[9] MAUDUIT, C.—SÁRKÖZY, A.: On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997), 365–377.10.4064/aa-82-4-365-377Search in Google Scholar

[10] MÉRAI, L.—WINTERHOF, A.: On the pseudorandomness of automatic sequences, Cryptogr. Commun. 10 (2018), 1013–1022.10.1007/s12095-017-0260-7Search in Google Scholar

[11] MOSHE, Y.: On the subword complexity of Thue-Morse polynomial extractions, Theoret. Comput. Sci. 389 (2007), 318–329.10.1016/j.tcs.2007.10.015Search in Google Scholar

[12] MÜLLNER, C.: The Rudin-Shapiro sequence and similar sequences are normal along squares, Canad. J. Math. 70 (2018), 1096–1129.10.4153/CJM-2017-053-1Search in Google Scholar

[13] SUN, Z.—WINTERHOF, A.: On the maximum order complexity of subsequences of the Thue-Morse and Rudin-Shapiro sequence, Unif. Distrib. Theory 14 (2019), 33–42.10.2478/udt-2019-0012Search in Google Scholar

[14] SUN, Z.—WINTERHOF, A.: On the maximum order complexity of subsequences of the Thue-Morse and Rudin-Shapiro sequence along squares, Int. J. Comput. Math. Comput. Syst. Theory 4 (2019), 30–36.10.1080/23799927.2019.1566275Search in Google Scholar