The Setting
The graph formulation of forced occurrence counts uses words as vertices. Its walks track changes to a current word, and its base edge multiplicities depend on counts of one-symbol extensions.
Let be a set of symbols, and let be the set of finite words over . Write for the symbol length of a word , and when is a contiguous substring of , including the empty word. For , the words and prepend and append , respectively.
A finite count instance consists of a finite set of substring vertices, a finite set of required input words, and a finite alphabet .
The count iteration of is the sequence of functions from words to nonnegative integers specified by (1), where denotes the count recursion operator of . (1)✦ The maximum vertex length of is the nonnegative integer specified by (2); it is zero when is empty. The forced occurrence count of is the function from words to nonnegative integers specified by (2). (2)
The Definition
Definition 1 (Hierarchical graph and base multiplicities). A vertex set is substring-closed when it satisfies (3). (3)✦ An up step goes from to , and a down step goes from to , for a symbol , with both endpoints in . A hierarchical walk from to in is a finite vertex sequence in the set of (4). (4)✦ Write for the walk with no steps at , and for the concatenation of walks and with matching endpoints. The cost of a hierarchical walk is the nonnegative integer defined by (5). (5)✦ For a finite count instance and a word , the base upward edge multiplicity is the nonnegative integer in (6). (6)✦ The base downward edge multiplicity of a word is the nonnegative integer in (7). (7)✦
What Is Checked
The definitions are stated over arbitrary sets of word vertices and finite count instances over a common symbol set.