The Setting
A shortest common superstring instance is a finite list of finite words over a symbol alphabet . The count construction assigns a natural number to each substring, subject to requirements from input words, their extensions and periodic texts. Word lengths count symbols.
Write for contiguous substring containment, including the empty word . An occurrence of a word in a word is a starting position satisfying (1); overlapping occurrences have distinct starting positions. (1)✦ For a word , write for its substring in positions . The substring set of a word and the irreducible input set are the finite sets in (2) and (3). (2)✦ (3)✦ The substring vertex set of is the set of words in (4), and the input alphabet of is the symbol set in (5). (4)✦ (5)✦ A finite count instance consists of finite sets of words and , and a finite set of symbols .✦ The preprocessed instance associated with is the finite count instance in (6). (6)✦
Blocking Occurrences
A template is an integer-indexed text . A word matches , written , when it satisfies (7). (7)✦ A blocking occurrence of a word in a word relative to a template is a starting position satisfying (8). (8)✦ The blocking coefficient counts the blocking positions, as in (9). For a count function , its blocking sum over is defined by (10). (9)✦ (10)✦
The Count Recursion
Fix a finite count instance . The maximum vertex length of a finite count instance is the natural number given by .✦ For a natural number count function on words and a word , the left and right extension sums and are the sums in (11). (11) For a word over , a chosen default symbol in and a nonnegative integer , the generated template takes at the symbol of indexed by the nonnegative part of the remainder of modulo , using the default symbol if that position is absent. When , it repeats the first symbols of in both integer directions, as in (12). (12) For words and natural numbers , the periodic rule is the bound in (13); parameters outside its stated conditions contribute zero. In the nonzero case, . (13)✦ The maximum periodic rule bound is the finite maximum in (14). The recursion operator is defined by (15), where is the indicator of the required set . (14)✦ (15)✦ The count iteration starts at zero. For a word , the forced occurrence count of the finite count instance is the value at of the count iteration after stages, as specified in (16). (16) The total letter count is the sum of the one-letter forced counts in (17), where denotes the one-letter word with symbol . (17)✦
The Claim
Theorem 1. For every finite input list and every word , the irreducible input set satisfies (18). (18)✦ For every finite count instance , its forced counts satisfy the exact recursion (19) at every word . (19)✦ Let be an integer-indexed text with positive period , let , and let match . Suppose , , and . Then the periodic lower bound is (20). (20)✦
What Is Checked
The preprocessing statement ranges over finite input lists and candidate superstrings. The recursion statements range over arbitrary finite count instances, and the periodic lower bound allows any positive period of an integer-indexed text.