On the pseudorandomness of Parry-Bertrand automatic sequences

Popoli, Pierre; Stipulanti, Manon

Download

Paper published in a journal (Scientific congresses and symposiums)

On the pseudorandomness of Parry-Bertrand automatic sequences

Popoli, Pierre; Stipulanti, Manon

2024 • In CEUR Workshop Proceedings

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/321464

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

main.pdf

Author preprint (369.51 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Combinatorics on words; Correlation measures; Abstract numeration systems; Morphic sequences; Automatic sequences; Periodic sequences

Abstract :

[en] The correlation measure is a testimony of the pseudorandomness of a sequence $\infw{s}$ and provides information about the independence of some parts of $\infw{s}$ and their shifts. Combined with the well-distribution measure, a sequence possesses good pseudorandomness properties if both measures are relatively small. In combinatorics on words, the famous $b$-automatic sequences are quite far from being pseudorandom, as they have small factor complexity on the one hand and large well-distribution and correlation measures on the other. This paper investigates the pseudorandomness of a specific family of morphic sequences, including classical $b$-automatic sequences. In particular, we show that such sequences have large even-order correlation measures; hence, they are not pseudorandom. We also show that even- and odd-order correlation measures behave differently when considering some simple morphic sequences.

Disciplines :

Mathematics

Author, co-author :

Popoli, Pierre ; Université de Liège - ULiège > Mathematics

Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

On the pseudorandomness of Parry-Bertrand automatic sequences

Publication date :

2024

Event name :

25th Italian Conference on Theoretical Computer Science

Event organizer :

Università degli Studi di Torino

Event place :

Torino, Italy

Event date :

September 11-13, Torino

Audience :

International

Journal title :

CEUR Workshop Proceedings

eISSN :

1613-0073

Publisher :

RWTH Aachen University, Aachen, Germany

Peer reviewed :

Peer Reviewed verified by ORBi

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique
ULiège FSR - Université de Liège. Fonds spéciaux pour la recherche

Funding text :

Pierre Popoli’s research is supported by ULiège’s Special Funds for Research, IPD-STEMA Program. Manon Stipulanti is an FNRS Research Associate supported by the Research grant 1.C.104.24F.

Available on ORBi :

since 26 August 2024

Statistics

Number of views

11 (4 by ULiège)

Number of downloads

29 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

A. N. Kolmogorov, Three approaches to the quantitative definition of information, Internat. J. Comput. Math. 2 (1968) 157–168. doi:10.1080/00207166808803030.
G. J. Chaitin, On the length of programs for computing finite binary sequences, J. Assoc. Comput. Mach. 13 (1966) 547–569. doi:10.1145/321356.321363.
R. J. Solomonoff, A formal theory of inductive inference. I, Information and Control 7 (1964) 1–22.
P. M. Vitányi, How incomputable is kolmogorov complexity?, Entropy 22 (2020). doi:10. 3390/e22040408.
C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997) 365–377. doi:10.4064/ aa-82-4-365-377.
C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences. II. The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction, J. Number Theory 73 (1998) 256–276. doi:10.1006/jnth.1998.2286.
N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, V. Rödl, Measures of pseudorandomness for finite sequences: typical values, Proc. Lond. Math. Soc. (3) 95 (2007) 778–812. doi:10.1112/plms/pdm027.
J. Cassaigne, C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences. VII. The measures of pseudorandomness, Acta Arith. 103 (2002) 97–118. doi:10.4064/aa103-2-1.
K. Gyarmati, On a pseudorandom property of binary sequences, The Ramanujan Journal 8 (2004) 289–302. doi:10.1007/s11139-004-0139-z.
K. Gyarmati, C. Mauduit, On the correlation of binary sequences, ii, Discrete Mathematics 312 (2012) 811–818. doi:https://doi.org/10.1016/j.disc.2011.09.013.
J.-P. Allouche, J. Shallit, Automatic sequences: Theory, applications, generalizations, Cambridge University Press, Cambridge, 2003.
L. Mérai, A. Winterhof, On the pseudorandomness of automatic sequences, Cryptogr. Commun. 10 (2018) 1013–1022. doi:10.1007/s12095-017-0260-7.
K. Mahler, The spectrum of an array and its application to the study of the translation properties of a simple class of arithmetical functions: Part two on the translation properties of a simple class of arithmetical functions, Journal of Mathematics and Physics 6 (1927) 158–163. doi:https://doi.org/10.1002/sapm192761158.
C. Mauduit, Multiplicative properties of the Thue-Morse sequence, Period. Math. Hungar. 43 (2001) 137–153. doi:10.1023/A:1015241900975.
M. Baake, M. Coons, Correlations of the Thue—Morse sequence, Indagationes Mathematicae (2023). doi:https://doi.org/10.1016/j.indag.2023.02.001.
J. Mazáč, Correlation functions of the Rudin–Shapiro sequence, Indagationes Mathematicae (2023). doi:https://doi.org/10.1016/j.indag.2023.03.003.
E. Grant, J. Shallit, T. Stoll, Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin-Shapiro sequences, Acta Arith. 140 (2009) 345–368. doi:10.4064/aa140-4-5.
E. Charlier, C. Cisternino, M. Stipulanti, Robustness of Pisot-regular sequences, Adv. in Appl. Math. 125 (2021) Paper No. 102151, 22. doi:10.1016/j.aam.2020.102151.
E. Charlier, C. Cisternino, M. Stipulanti, A full characterization of Bertrand numeration systems, in: Developments in language theory, volume 13257 of Lecture Notes in Comput. Sci., Springer, Cham, 2022, pp. 102–114. doi:10.1007/978-3-031-05578-2\_8.
A. Massuir, J. Peltomäki, M. Rigo, Automatic sequences based on Parry or Bertrand numeration systems, Adv. in Appl. Math. 108 (2019) 11–30. doi:10.1016/j.aam.2019. 03.003.
F. Point, On decidable extensions of Presburger arithmetic: from A. Bertrand numeration systems to Pisot numbers, J. Symbolic Logic 65 (2000) 1347–1374. doi:10.2307/2586704.
M. Stipulanti, Convergence of Pascal-like triangles in Parry-Bertrand numeration systems, Theoret. Comput. Sci. 758 (2019) 42–60. doi:10.1016/j.tcs.2018.08.003.
M. Lothaire, Combinatorics on words, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1997. doi:10.1017/CBO9780511566097.
P. B. A. Lecomte, M. Rigo, Numeration systems on a regular language, Theory Comput. Syst. 34 (2001) 27–44. doi:10.1007/s002240010014.
V. Berthé, M. Rigo (Eds.), Combinatorics, Automata, and Number Theory, volume 135 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2010. doi:10.1017/CBO9780511777653.
M. Rigo, A. Maes, More on generalized automatic sequences, Journal of Automata, Languages, and Combinatorics 7 (2002) 351–376. doi:10.25596/jalc-2002-351.
J. Shallit, A generalization of automatic sequences, Theoret. Comput. Sci. 61 (1988) 1–16. doi:10.1016/0304-3975(88)90103-X.
M. Rigo, Formal languages, automata and numeration systems. 2, Networks and Telecommunications Series, ISTE, London; John Wiley & Sons, Inc., Hoboken, NJ, 2014. Applications to recognizability and decidability.
W. Parry, On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar. 11 (1960) 401–416. doi:10.1007/BF02020954.
E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41 (1972) 179–182.
A. Bertrand-Mathis, Comment écrire les nombres entiers dans une base qui n’est pas entière, Acta Math. Hungar. 54 (1989) 237–241. doi:10.1007/BF01952053.
N. J. A. Sloane, et al., The On-Line Encyclopedia of Integer Sequences, 2024. URL: https://oeis.org.
J.-P. Allouche, J. Cassaigne, J. Shallit, L. Q. Zamboni, A taxonomy of morphic sequences, 2019. Preprint available at https://arxiv.org/pdf/1711.10807.
J. Shallit, The logical approach to automatic sequences—exploring combinatorics on words with Walnut, volume 482 of London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 2023.
A. Cobham, Uniform tag seqences, Mathematical Systems Theory 6 (1972) 164–192. doi:10.1007/BF01706087.
M. Morse, G. A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938) 815–866.
M. I. Hollander, Greedy numeration systems and regularity, Theory Comput. Syst. 31 (1998) 111–133. doi:10.1007/s002240000082.