The Setting
In a hierarchical graph of substring vertices, an up step appends one symbol and costs one; a down step deletes the first symbol and costs zero. Assigning copies to these edges expresses occurrence requirements for the input words. The base multiplicities concern both the flow at a word and the occurrences recorded in periodic layer windows.
A finite count instance consists of finite sets and of words over a symbol set , and a finite alphabet .✦ The words in are required words. A vertex set is substring-closed if every contiguous substring of every word in , including the empty word , belongs to .✦ A valid count instance is a finite count instance such that , is substring-closed, and every symbol occurring in a word of belongs to .✦
The count iteration starts with zero counts and successively computes new occurrence counts.✦ The forced occurrence count of a word is its value after stages, where the maximum vertex length is defined in (1).✦ This maximum is zero when is empty. (1)✦ The total forced letter count is the sum in (2). (2)✦ Here a symbol in the argument of denotes the one-letter word.
The base up and down multiplicities and of a word are the nonnegative integers defined in (3). (3) For a nonempty word , these are the multiplicities of the up edge that appends its last symbol and the down edge that deletes its first symbol.
Threading and Recorded Occurrences
A downward token of a finite count instance is a distinct copy of a downward edge, indexed by the set in (4); its word is . (4) A threading on a vertex set is a set of tokens with nonempty words and a permutation of satisfying the compatibility condition (5).✦ The notation means that is a prefix of , and deletes its first symbol. (5) The base threading of a valid count instance uses , its token words, and a compatible permutation.✦
The text induced by a token is the integer-indexed text defined in (6), where takes the first symbol. (6)✦ Two tokens have translation-equivalent texts when they satisfy (7).✦ A text group of a threading is an equivalence class of tokens whose induced texts are translation-equivalent.✦ (7)✦ The primitive period of an integer-indexed text is the least positive integer that is a period of . For each group , choose a representative text and write for its primitive period, as specified by (8). (8)✦
A token aligned with an integer-indexed text is a token whose full induced text equals . The alignment set of an integer-indexed text is the set of tokens aligned with , as in (9); enumerate its members as , where . (9)✦ The passage exits of an integer-indexed text at position are the integers defined in (10). The sorted exit of a text at position is the th order statistic of its passage exits: index in the nondecreasing list of passage exits, retaining repetitions.✦ (10)
A finite window of an integer-indexed text , for integers and , is the word of symbols at the integer positions in the half-open interval ; it is empty when .✦ A layered phase of a threading is a triple consisting of a text group and integer indices and with and .✦ The phase window of a layered phase is the finite word in (11). (11) A recorded occurrence of a word is a phase whose window begins with .✦ The set of recorded occurrences of a word is the set of layered phases specified in (12). (12)
The Claim
Theorem 1. Let be a finite count instance. Every nonempty required vertex satisfies (13). (13)✦ Suppose further that is valid. At every word , the base multiplicities satisfy the balance equation (14). (14)✦ The total up and down multiplicities are given by (15) and (16), respectively. (15)✦ (16)✦ For every nonempty word , the base threading has the recorded multiplicity (17). (17)✦
What Is Checked
The required-word bound is stated over arbitrary finite count instances; the balance and total identities, and the recorded multiplicity identity, are stated over valid instances and their base threadings. Every downward token has a nonempty word.