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 条
  • [31] Automatic sequences and the Glaisher-Kinkelin constant
    Campbell, John M.
    ADVANCES IN APPLIED MATHEMATICS, 2024, 158
  • [32] About frequencies of letters in generalized automatic sequences
    Nicolay, S.
    Rigo, M.
    THEORETICAL COMPUTER SCIENCE, 2007, 374 (1-3) : 25 - 40
  • [33] Automatic sequences and curves over finite fields
    Bridy, Andrew
    ALGEBRA & NUMBER THEORY, 2017, 11 (03) : 685 - 712
  • [34] AUTOMATIC SEQUENCES ARE ORTHOGONAL TO APERIODIC MULTIPLICATIVE FUNCTIONS
    Lemanczyk, Mariusz
    Muellner, Clemens
    DISCRETE AND CONTINUOUS DYNAMICAL SYSTEMS, 2020, 40 (12) : 6877 - 6918
  • [35] Combinatorics on words and generating Dirichlet series of automatic sequences
    Allouche, Jean-Paul
    Shallit, Jeffrey
    Stipulanti, Manon
    DISCRETE MATHEMATICS, 2025, 348 (08)
  • [36] (LOGARITHMIC) DENSITIES FOR AUTOMATIC SEQUENCES ALONG PRIMES AND SQUARES
    Adamczewski, Boris
    Drmota, Michael
    Muellner, Clemens
    TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2022, 375 (01) : 455 - 499
  • [37] Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev
    Shallit, Jeffrey
    Shan, Sonja Linghui
    Yang, Kai Hsiang
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2023, 57
  • [38] Automatic sequences generated by synchronizing automata fulfill the Sarnak conjecture
    Deshouillers, Jean-Marc
    Drmota, Michael
    Muellner, Clemens
    STUDIA MATHEMATICA, 2015, 231 (01) : 83 - 95
  • [39] Subsequences of automatic sequences indexed by left perpendicularncright perpendicular and correlations
    Deshouillers, Jean-Marc
    Drmota, Michael
    Morgenbesser, Johannes F.
    JOURNAL OF NUMBER THEORY, 2012, 132 (09) : 1837 - 1866
  • [40] Self-similar groups, automatic sequences, and unitriangular representations
    Grigorchuk, R.
    Leonov, Y.
    Nekrashevych, V.
    Sushchansky, V.
    BULLETIN OF MATHEMATICAL SCIENCES, 2016, 6 (02) : 231 - 285
12345