2021/12/06 by Ľubomíra Dvořáková, Daniela Opočenská, Dvořáková, Lubomíra +5 · 2 citations
Computer Science · #semigroups and automata theory #Coding theory and cryptography #Cellular Automata and Applications
paper · pdf · doi:10.48550/arxiv.2112.02854
We study the threshold between avoidable and unavoidable repetitions in infinite balanced sequences over finite alphabets. The conjecture stated by Rampersad, Shallit and Vandomme says that the minimal critical exponent of balanced sequences over the alphabet of size d ≥ 5 equals (d-2)/(d-3). This conjecture is known to hold for d∈ \5, 6, 7,8,9,10\. We refute this conjecture by showing that the picture is different for bigger alphabets. We prove that critical exponents of balanced sequences over an alphabet of size d≥ 11 are lower bounded by (d-1)/(d-2) and this bound is attained for all even numbers d≥ 12. According to this result, we conjecture that the least critical exponent of a balanced sequence over d letters is (d-1)/(d-2) for all d≥ 11.