Sets Represented as the Length-n Factors of a Word

2013/04/12 by Jeffrey Shallit, Tan, Shuo, Shallit, Jeffrey
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #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.1304.3666

openalex publication_date 2013/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we consider the following problems: how many different subsets of Sigmaⁿ can occur as set of all length-n factors of a finite word? If a subset is representable, how long a word do we need to represent it? How many such subsets are represented by words of length t? For the first problem, we give upper and lower bounds of the form alpha^(2ⁿ) in the binary case. For the second problem, we give a weak upper bound and some experimental data. For the third problem, we give a closed-form formula in the case where n <= t < 2n. Algorithmic variants of these problems have previously been studied under the name "shortest common superstring".

Related

• The complexity of Shortest Common Supersequence for inputs with no identical consecutive letters
• Two bijections for sets of words with forbidden factors
• Growth rate of binary words avoiding xxx^R
• A proof that a word of length n has less than 1.5n distinct squares
• Longest common subsequences in sets of words