On the pseudorandomness of automatic sequences

被引：3
|
作者：
Merai, Laszlo [1 ]
Winterhof, Arne [1 ]
机构：
[1] Austrian Acad Sci, Johann Radon Inst Computat & Appl Math, Altenbergerstr 69, A-4040 Linz, Austria
来源：
CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES | 2018年 / 10卷 / 06期
基金：
奥地利科学基金会;
关键词：
Finite automaton; Automatic sequences; Correlation measure; Pseudorandom sequences; Thue-Morse sequence; State complexity;
D O I：
10.1007/s12095-017-0260-7
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页码：1013 / 1022
页数：10
相关论文
共 50 条
  • [11] Multiplicative automatic sequences
    Konieczny, Jakub
    Lemanczyk, Mariusz
    Mullner, Clemens
    MATHEMATISCHE ZEITSCHRIFT, 2022, 300 (02) : 1297 - 1318
  • [12] On asymptotically automatic sequences
    Konieczny, Jakub
    ACTA ARITHMETICA, 2024, 215 (03) : 249 - 287
  • [13] Averages of automatic sequences
    Barbe, A.
    von Haeseler, F.
    THEORETICAL COMPUTER SCIENCE, 2006, 359 (1-3) : 255 - 281
  • [14] Cayley graphs and automatic sequences
    Guillot, Pierre
    JOURNAL OF ALGEBRAIC COMBINATORICS, 2017, 45 (01) : 245 - 270
  • [15] Exponential sums with automatic sequences
    Drappeau, Sary
    Muellner, Clemens
    ACTA ARITHMETICA, 2018, 185 (01) : 81 - 99
  • [16] Cayley graphs and automatic sequences
    Pierre Guillot
    Journal of Algebraic Combinatorics, 2017, 45 : 245 - 270
  • [17] On a family of automatic apwenian sequences
    Guo, Ying-Jun
    Han, Guo-Niu
    DISCRETE MATHEMATICS, 2025, 348 (05)
  • [18] Limit sets of automatic sequences
    Barbé, A
    von Haeseler, F
    ADVANCES IN MATHEMATICS, 2003, 175 (02) : 169 - 196
  • [19] The Measures of Pseudorandomness and the NIST Tests
    Merai, Laszlo
    Rivat, Joel
    Sarkozy, Andras
    NUMBER-THEORETIC METHODS IN CRYPTOLOGY, 2018, 10737 : 197 - 216
  • [20] Linear cellular automata and automatic sequences
    Allouche, JP
    Von Haeseler, F
    Lange, E
    Petersen, A
    Skordev, G
    PARALLEL COMPUTING, 1997, 23 (11) : 1577 - 1592
12345