Paper published in a journal (Scientific congresses and symposiums)
On the pseudorandomness of Parry-Bertrand automatic sequences
Popoli, Pierre; Stipulanti, Manon
2024In CEUR Workshop Proceedings
Peer Reviewed verified by ORBi
 

Files


Full Text
main.pdf
Author preprint (369.51 kB)
Download

All documents in ORBi are protected by a user license.

Send to



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
10 (4 by ULiège)
Number of downloads
26 (2 by ULiège)

Bibliography


Similar publications



Contact ORBi