2020/10/27 by Daniel Gabrić, Gabric, Daniel · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2010.14663
openalex publication_date 2020/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A word is said to be bordered if it contains a non-empty proper prefix that is also a suffix. We can naturally extend this definition to pairs of non-empty words. A pair of words (u,v) is said to be mutually bordered if there exists a word that is a non-empty proper prefix of u and suffix of v, and there exists a word that is a non-empty proper suffix of u and prefix of v. In other words, (u,v) is mutually bordered if u overlaps v and v overlaps u. We give a recurrence for the number of mutually bordered pairs of words. Furthermore, we show that, asymptotically, there are c⋅ k2n mutually bordered words of length-n over a k-letter alphabet, where c is a constant. Finally, we show that the expected shortest overlap between pairs of words is bounded above by a constant.