The Setting
The vertices are finite words, and the construction seeks a closed walk from the empty word that visits prescribed periodic layers. Connection plans assign budgets to blocks of layers and specify the overlaps at which they can meet.
Let be an alphabet and the empty word. Write when is a contiguous substring of , allowing . A substring-closed vertex set contains every substring of each of its words.✦ A hierarchical walk in consists of stationary walks, steps appending one symbol, steps deleting the first symbol, and concatenations of such walks; all vertices belong to .✦ The cost of a hierarchical walk in is its number of appended symbols, and its visited set is the set of its actual vertices, including the endpoints. Costs add under concatenation, whose visited set is the union of the constituent visited sets. A based closed walk is a hierarchical walk from a chosen base to itself, with the same cost and visitation conventions.✦
Periodic Layers
For an integer-indexed text , its finite window lists its symbols at positions in , and is empty when .✦ A periodic layer for , and a parameter is a nondecreasing exit function with the conditions in (1).✦ Its first and last exit positions are and ; its base layer vertices form : (1)
An ordered layer collection has groups , each with a text , a positive period and a positive number of layers , . The text satisfies , and the exit functions of the layers satisfy whenever . Distinct groups have texts that differ at some position under every integer shift. A grouped layer index is a pair ; write and .
For a linearly ordered alphabet, the forward rotation stream of at phase is , ordered lexicographically.✦ A greatest rotation phase of a group is an integer phase at which the forward rotation stream of is lexicographically greatest.✦ The greatest rotation rank of a group is the forward rotation stream of beginning at a greatest rotation phase .✦
A shifted layer record of a text in a layer with text is a triple satisfying (2).✦ The second condition is interval agreement of with the shifted text on : (2) A shifted layer record of a text in a layer with text is foreign when and disagree at some integer position after shifting by . The recorded window of a shifted layer record of a text is the word .
For an exit family , threshold and , the set of qualifying layer indices is given by (3): (3) For a layer , write and . Foreign record supply for an ordered layer collection is the property that, for every and positive with and , there is a foreign record of in some layer with and .✦
Connection Plans
A block connection plan indexed by assigns to each a content set , nonnegative integer reserve and free allowance , an ordered rank , an optional target , and a recorded word . A specified target requires . For each there is a based closed walk through of cost at most , and a based closed walk through whose cost plus is at most . When and , there is a based closed walk of cost at most through that visits a word of length at most . A self-target requires a word in of length at most .
An outgoing layer plan for over a linearly ordered alphabet chooses a source group , a nonempty finite set of layers in that group, a target layer , and a foreign record of in . Its content, recorded word and reserve are given in (4); the reserve includes base turns and connections: (4) The plan requires a link walk and an internal walk , both based closed walks, satisfying (5). When , it also requires a based closed walk satisfying its final two lines: (5)
Count Data
A finite count instance consists of finite sets of substring vertices, required words and alphabet symbols.✦ A finite count instance is valid when , is substring-closed, and every symbol of every word in lies in .✦ The count iteration of a finite count instance is the sequence of count assignments that starts at zero and repeatedly applies the count recursion operator .✦ The maximum vertex length , forced occurrence count and total forced letter count are defined in (6); lengths count symbols: (6) Here denotes the one-letter word with symbol .
The Claim
Theorem 1. Let be substring-closed. For a block connection plan, let be finite and let be a walk from to . Suppose each either has its target in or has , with the latter condition required when its target is absent. There is a walk from to satisfying (7): (7)✦
For an ordered layer collection over a linearly ordered alphabet, let be a finite set of outgoing layer plans and let be a walk from to . Suppose each layer either has all its vertices in or belongs to a member set for some . There is a walk from to satisfying (8): (8)✦
Suppose has finitely many groups, , and foreign record supply holds. There is a walk from to satisfying (9): (9)✦
Let be a valid finite count instance whose required words are nonempty vertices. There is a word satisfying (10): (10)✦
In the paper, the result reads: the base graph can be connected to by adding closed walks of total up cost at most .
What Is Checked
The claims are stated over substring-closed hierarchical graphs with the specified connection plans or foreign record supply, and over valid finite count instances whose required words are nonempty vertices.