The Setting
Overlapping copies of a word can share symbols in a common superstring. Their occurrences are distinguished by their starting positions, even when those positions lie inside another occurrence.
A symbol is a finite binary string✦, and a word is a finite sequence of symbols.✦ A superstring instance is a finite list of words.✦ Write for the empty word and for contiguous substring containment, including the empty word. The length counts symbols, and the total input symbol length is the sum in (1), with repeated input words counted as often as they occur in . (1)
A common superstring of a superstring instance is a word containing every word in .✦ (2) The optimum superstring length is the infimum of the natural number lengths of common superstrings, as in (3). (3)✦
For words and over an alphabet , the occurrence set is the set of starting positions of in satisfying the length and symbol conditions in (4). The occurrence count of a word in a word is the cardinality of its occurrence set , as in (5). (4)✦ (5)✦
The Counting Data
A finite count instance over consists of finite sets and of words, called its substring vertices and required words, together with a finite alphabet .✦ The maximum vertex length of a finite count instance is the nonnegative integer in (6), taking the value zero when is empty. (6)✦
For a finite count instance , its count recursion operator transforms a function assigning nonnegative integer counts to words into the next such count function; the count iteration starts with zero counts and applies this operator repeatedly, as in (7). The forced occurrence count of is the function obtained after iterations, as specified by (8). (7)✦ (8)✦ The total forced letter count of is the sum of the one-letter counts in (9). (9)✦ where in the argument of denotes the one-letter word consisting of .
For a word , its substring set is the finite set of all contiguous substrings, including .✦ For a superstring instance , the substring vertex set is the set in (10); it contains even when is empty. (10) The irredundant input core is the set of distinct nonempty input words whose only containing input word is themselves, as in (11). (11)✦ The input alphabet is the set of symbols appearing in the input words.✦ The preprocessed count instance of a superstring instance is the finite count instance with substring vertices , required words , and alphabet , as in (12); write and for its forced count and total forced letter count. (12)✦
The Claim
Theorem 1. Let be a finite count instance, with forced count and total forced letter count . Let be a word containing every word of as a contiguous substring. For every word , (13)✦ Moreover, (14)✦ For a superstring instance , the counts of its preprocessed count instance satisfy (15)✦ For every nonempty word , (16)✦
What Is Checked
The statements (13) and (14) range over arbitrary finite count instances and words containing all their required words, while (15) and (16) concern the preprocessed input instance , with symbol lengths throughout and a nonempty word in (16).