2022/07/31 by Ľubomíra Dvořáková, Dvořáková, Lubomíra, Daniela Opočenská +3
Computer Science · #68R15 #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2208.00366
openalex publication_date 2022/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The critical exponent E(\mathbf u) of an infinite sequence \mathbf u over a finite alphabet expresses the maximal repetition of a factor in \mathbf u. By the famous Dejean's theorem, E(\mathbf u) ≥ 1+\frac1d-1 for every d-ary sequence \mathbf u. We define the asymptotic critical exponent E^*(\mathbf u) as the upper limit of the maximal repetition of factors of length n. We show that for any d>1 there exists a d-ary sequence \mathbf u having E^*(\mathbf u) arbitrarily close to 1. Then we focus on the class of d-ary balanced sequences. In this class, the values E^*(\mathbf u) are bounded from below by a threshold strictly bigger than 1. We provide a method which enables us to find a d-ary balanced sequence with the least asymptotic critical exponent for 2≤ d≤ 10.