The Setting
Given an occurrence recorded by a periodic layer, the question is whether it lies inside an actual visited window that agrees with a prescribed template. A blocking witness specifies a longer recorded word and an occurrence inside it, with mismatches at the two ends of the longer word.
Let be an alphabet. A substring occurrence of a word in a word at position is a contiguous match with and ; distinct starts count separately, including for overlapping matches and the empty word.✦ For an integer-indexed text , write for its finite text window, with the empty word when .✦ A text occurrence of a word in an integer-indexed text at position is a match satisfying for .✦ A word agrees with a template when throughout its positions.✦ Two texts agree on when their symbols agree at every integer in that interval.✦
A periodic layer over a vertex set and a text , with parameter , is a nondecreasing integer-valued exit function satisfying (1).✦ Its first and last exits at are and . (1) An actual window of a periodic layer over a text is a window with . The recording predicate and the set of recorded occurrence residues are defined by (2). An occurrence contained in an actual window need not itself be an actual window. (2) For a finite family , the family occurrence set is the disjoint union ; each occurrence retains its layer index.✦
Bracketing Witnesses
A blocking position of a word in a word , relative to a template , is a position satisfying (3).✦ Write for the set of these positions. (3)✦ For a finite word set and a count function , the blocking coefficient counts blocking positions✦, and the weighted blocking sum is defined by (4) over .✦ (4)
A bracketing witness for a word in a layer , relative to a finite word set and a template , is a triple consisting of a word of , a recorded occurrence of and a blocking position inside , as in (5).✦ Family bracketing witnesses also retain the layer index.✦ (5) When and is -periodic, phase normalization sends an integer recording start to its representative in .✦ The blocked occurrence map sends to the normalized occurrence of induced at .✦ Its family version applies this map in each layer and preserves the layer index.✦
Primitive Layers from Counts
A finite count instance is a triple of finite sets: a set of vertex words, a set of required words and a set of symbols.✦ A valid finite count instance is a finite count instance whose vertex set contains the empty word, is closed under contiguous substrings and uses only symbols of its symbol set .✦ The maximum vertex length of a finite count instance with vertex set is the maximum in (6), equal to zero when is empty. The forced count of a word in a finite count instance is the value at stage of the count iteration of , which starts from zero and repeatedly applies the count recursion of . The downward multiplicity of a word in a finite count instance is the truncated difference in (6).✦ (6) A downward edge token of a finite count instance with vertex set and downward multiplicity is a pair with and ; its token word is .✦
A down-edge threading on a vertex set is a set of tokens with nonempty token words and a successor permutation such that deleting the first symbol of leaves a prefix of for every .✦ Here the token set is finite. For a valid finite count instance , the base edge threading uses its downward edge tokens and a chosen compatible successor permutation.✦ For a threading with successor permutation and token words , the induced periodic text at token is the integer-indexed text defined by (7), using integer iterates of .✦ (7)
Two tokens and of a threading are text translation equivalent when their induced texts and agree after an integer translation.✦ A primitive text group of a threading is an equivalence class of tokens whose induced texts agree after an integer translation.✦ Choose a representative text from the class and let be its least positive period, the smallest positive integer with for all . For a text , its full-text-aligned tokens are , where equality is at every integer position.✦ An aligned token enumeration of is a bijection from the ranks onto the full-text-aligned tokens .
Let and enumerate as . At coordinate , the unsorted passage exits and sorted layer exits are given by (8). The sorted value list arranges the passage exits in nondecreasing order, retaining multiplicities✦; its entry of rank , counted from zero, is the th order statistic.✦ (8) For substring-closed and a period of , the ordered layer at rank is the layer over with exit function and parameter .✦ The indexed primitive layer of a threading is the ordered layer at rank over with parameter , with .✦ Write for this family from the base threading, and put . A primitive layer index is a pair consisting of a primitive text group and a rank with .
The Claim
Theorem 1 (Lemma 3.3). Let be a finite family of layers, with texts and parameters . For a finite word set , a template and a word , the bracketing witness cardinality is (9), with the blocking sum taken over .✦ (9)✦ If every is positive and every is -periodic, the family blocked occurrence map satisfies (10).✦ (10)✦ For a valid finite count instance , its forced count and primitive layer count satisfy (11) for every and , with both blocking sums taken over its vertex set .✦ (11)✦ Finally, let be a layer over with parameter and substring-closed. Suppose is -periodic and agrees with . For a recorded occurrence outside the image of , there is a matching actual window as specified in (12).✦ (12)✦
What Is Checked
The witness statements range over finite families of layers and finite word sets; the blocking sum identity uses valid finite count instances and their base threadings, while the matching window statement uses a substring-closed vertex set and a template agreeing with .
For a count instance, each downward token has a nonempty vertex word, and validity ensures the existence of a compatible token permutation.✦ For an arbitrary threading, the ordered exit functions are nondecreasing✦ and bound each start from the preceding coordinate.✦ They translate by every period of their text.✦ With substring closure, every window between the first and last ordered exits belongs to the vertex set.✦