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 条
  • [21] Automatic sequences and parity of partition functions
    Chen, Shi-Chao
    ADVANCES IN APPLIED MATHEMATICS, 2025, 166
  • [22] Hyperquadratic continued fractions and automatic sequences
    Lasjaunias, Alain
    Yao, Jia-Yan
    FINITE FIELDS AND THEIR APPLICATIONS, 2016, 40 : 46 - 60
  • [23] Quasicrystals, model sets, and automatic sequences
    Allouche, Jean-Paul
    Meyer, Yves
    COMPTES RENDUS PHYSIQUE, 2014, 15 (01) : 6 - 11
  • [24] The distribution of elements in automatic double sequences
    Moshe, Y
    DISCRETE MATHEMATICS, 2005, 297 (1-3) : 91 - 103
  • [25] Factors of generalised polynomials and automatic sequences
    Byszewski, Jakub
    Konieczny, Jakub
    INDAGATIONES MATHEMATICAE-NEW SERIES, 2018, 29 (03): : 981 - 985
  • [26] Automatic Sequences and Zip-Specifications
    Grabmayer, Clemens
    Endrullis, Joerg
    Hendriks, Dimitri
    Klop, Jan Willem
    Moss, Lawrence S.
    2012 27TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2012, : 335 - 344
  • [27] On the joint subword complexity of automatic sequences
    Moshe, Yossi
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) : 3573 - 3588
  • [28] Automatic sequences: from rational bases to trees
    Rigo, Michel
    Stipulanti, Manon
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2022, 24 (01)
  • [29] On certain recurrent and automatic sequences in finite fields
    Lasjaunias, Alain
    Yao, Jia-Yan
    JOURNAL OF ALGEBRA, 2017, 478 : 133 - 152
  • [30] Cyclotomic properties of polynomials associated with automatic sequences
    Sobolewski, Bartosz
    ADVANCES IN APPLIED MATHEMATICS, 2020, 120
12345