2015/06/25 by Jeremy Nicholson, Narad Rampersad, Nicholson, Jeremy +1
Computer Science · #68R15 #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1506.07847
openalex publication_date 2015/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In combinatorics on words, a word w of length n over an alphabet of size q is said to be privileged if n <= 1 or if n >= 2 and w has a privileged border that occurs exactly twice in w. Forsyth, Jayakumar and Shallit proved that there exist at least 2n-5/n2 privileged binary words of length n. Using the work of Guibas and Odlyzko, we prove that there are constants c and n0 such that for n >= n0, there are at least (cqn)/(n(logq n)2) privileged words of length n over an alphabet of size q. Thus, for n sufficiently large, we improve the earlier bound set by Forsyth, Jayakumar and Shallit and generalize for all q.