2022/06/28 by Daniel Gabrić, Gabric, Daniel
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2206.14273
openalex publication_date 2022/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A word~w has a border u if u is a non-empty proper prefix and suffix of u. A word~w is said to be closed if w is of length at most 1 or if w has a border that occurs exactly twice in w. A word~w is said to be privileged if w is of length at most 1 or if w has a privileged border that occurs exactly twice in w. Let Ck(n) (resp.~Pk(n)) be the number of length-n closed (resp. privileged) words over a k-letter alphabet. In this paper, we improve existing upper and lower bounds on Ck(n) and Pk(n). We completely resolve the asymptotic behaviour of Ck(n). We also nearly completely resolve the asymptotic behaviour of Pk(n) by giving a family of upper and lower bounds that are separated by a factor that grows arbitrarily slowly.