The Setting
The counting problem concerns occurrences of words in periodic layers. Overlapping occurrences are distinguished by their starting positions, and distinct copies of a hierarchical edge remain separate.
A finite count instance over a symbol set consists of a finite set of vertex words, a finite set of required words, and a finite alphabet .✦ Write for the empty word, for symbol length, and when is a prefix of . A substring-closed set contains every contiguous substring of each of its words, including .✦ A finite count instance is valid when , is substring-closed, and every letter of every vertex word belongs to .✦
The maximum vertex length is .✦ The count iteration starts with the identically zero function and obtains by applying ’s count recursion operator to .✦ The forced occurrence count and the base down multiplicity are defined by (1), where denotes appending the letter and . (1) A downward edge token is a pair with and ✦; its token word is .✦ Denote this finite token set by .
Threadings and Their Texts
A finite down edge threading on a vertex set assigns each token in a finite set a nonempty word and a successor permutation of satisfying (2).✦ Here deletes the first symbol. (2) The base edge threading of a valid count instance uses , its token words, and a chosen compatible successor permutation.✦
The induced periodic text based at token is the integer-indexed text , where denotes the first symbol of a nonempty word.✦ Two tokens are text translation equivalent when some integer satisfies for every integer .✦ A primitive text group of a threading is an equivalence class of tokens of under text translation equivalence.✦ Write for the set of groups, choose a representative token in each group , and put .✦ A period of a text is a positive integer such that for every integer ; the least positive period of is a positive period of no larger than any other positive period of .✦ Denote the least positive period of by .✦
The full-text aligned tokens for a text form the set .✦ Put and enumerate these tokens as . The unsorted passage exits and sorted layer exits of the enumerated tokens aligned with a text are the integer positions given by (3). The notation means the entry at index , starting at zero, in the nondecreasing sorted list of the indicated values, with repetitions retained.✦ An aligned token enumeration for is a bijection from the indices to the full-text aligned token set , sending to .✦ (3)
Layers and Recorded Occurrences
For an integer-indexed text , the finite window is the word of symbols at positions , and is empty when .✦ A word occurs in an integer-indexed text at an integer position when for every .✦
A periodic layer on consists of an integer-indexed text , a nonnegative integer parameter , and an integer-valued nondecreasing exit function satisfying the conditions in (4).✦ The visited windows of a periodic layer are the windows specified by the last condition of (4). (4) For a substring-closed vertex set and a period of a text , the ordered layer with index is the periodic layer on with text , period , and exit function .✦ The primitive layer indices of are the pairs with and ✦; the indexed primitive layer uses text , period , and exits .✦ Denote this family by .
A layer records a word at an integer position when occurs in at and .✦ The occurrence set of a word in a layer is the set of its recorded positions .✦ An occurrence of a word in a family of layers is a pair consisting of a layer in that family and an occurrence of in that layer; for this gives (5).✦ (5)
A primitive layered phase is a triple with , , and .✦ The phase window of a primitive layered phase is a finite word, and the recorded occurrence set of a word in a threading is a set of primitive layered phases, as defined in (6). (6)
The Claim
Theorem 1. For a finite down edge threading and any finite word , the recorded count satisfies (7).✦ (7)✦ Let be a valid finite count instance, let be its base edge threading, and let be its primitive layer family. For every nonempty word , the threading and family counts satisfy (8) and (9), respectively. (8)✦ (9)✦
In the paper, the result reads: for every nonempty word , the total number of recorded occurrences of on all the closed walks is , counting starting positions modulo each walk’s turn length.
What Is Checked
The prefix count is stated over arbitrary finite down edge threadings; the forced counts are stated over valid finite count instances and nonempty words.
Every downward edge token has a nonempty vertex word. For a valid count instance, a compatible token permutation exists.✦ For every text , its sorted exits are nondecreasing✦ and satisfy the lower bound in (4)✦; when is a period of , their shift rule holds✦, and when is substring-closed, their visited windows belong to .✦