The Setting
Two occurrences in a common text determine window words that may overlap or be separated by a gap. A connection between these words is a walk that appends symbols on the right and deletes symbols on the left.
Let be an alphabet. An integer-indexed text over is a function . For an integer-indexed text over and integers , the finite text window of is the word on the half-open interval , with reversed endpoints giving the empty word, as defined in (1): (1)✦
A substring-closed vertex set is a set of words containing every contiguous substring, including the empty word, of each of its words.✦
A hierarchical walk in is a finite directed walk with all vertices in , whose up steps append one symbol on the right and whose down steps delete the first symbol.✦ Stationary walks at vertices of are allowed. Two walks can be concatenated when the last vertex of the first is the first vertex of the second.
The cost of a hierarchical walk is its number of up steps.✦ A stationary walk and a down step have cost zero, and costs add under concatenation. The visited set of a hierarchical walk is the set of its actual vertices, including both endpoints.✦
The Claim
Theorem 1. Let be substring-closed, and let be a text such that the one-letter word belongs to for every .
Let be integers with , , and , and suppose and belong to . There are a hierarchical walk from to and a word satisfying (2): (2)✦
Let , indexed by , be two nondecreasing sequences, and let . Suppose and for every . There is a hierarchical walk from to satisfying (3): (3)✦
What Is Checked
The statements concern hierarchical walks in a substring-closed vertex set and windows of an integer-indexed text whose one-letter words belong to that set, with the window starts and ends ordered in the direction of the walk.