The Setting
A host layer and its child layers describe windows from different periodic texts. The connection problem asks for a closed hierarchical walk that visits a window of each layer.
Let be an alphabet and let be a set of finite words over . A substring-closed vertex set over is a set of finite words over that contains every contiguous substring of each of its words, including the empty word .✦ For an integer-indexed text , write for the finite word read on the half-open interval ; this word is empty when .✦ A positive period of is an integer such that for every integer ; it need not be the least positive period.
A hierarchical walk in is a finite walk whose up steps append one symbol and whose down steps delete the first symbol, with the source and target of every step in .✦ A stationary walk at any word of is allowed, and walks with a common endpoint may be concatenated. A walk visits a word when that word is an actual vertex of the walk, including either endpoint.✦ The cost of a hierarchical walk in is the number of up steps in : stationary walks and down steps cost zero, and concatenation adds costs.✦
A periodic layer for , a text and a nonnegative integer period parameter is a nondecreasing function satisfying (1)✦ The first exit position and last exit position of a periodic layer at an integer are the integers defined by (2) A walk touches when it visits some word with between the two exit positions in (2), inclusively.✦
Recorded Windows and Requests
Two integer-indexed texts and have interval agreement on when for every integer with .✦ A recorded host window of a layer on consists of a text with positive period , distinct from , and integer endpoints satisfying (3): (3)✦
A child layer request of consists of a periodic layer for , text and period parameter , with an integer endpoint satisfying the interior conditions in (4): (4)✦
For a family of recorded host windows indexed by a set , distinctness of the hosted texts modulo shifts means (5)
A family of requests is indexed by a set , with a map assigning each request to its recorded host window .
The Claim
Theorem 1. Let be substring-closed, let have positive period , and let be a periodic layer for , and . Let be recorded host windows of whose texts satisfy (5), and let be requests assigned by . Suppose that every one-letter word and belongs to . For every finite nonempty set , there is a hierarchical walk from to such that (6)✦
What Is Checked
The claim (6) is stated over substring-closed word sets, periodic layers and their actual visited windows, recorded host windows with texts distinct modulo shifts, and finite nonempty families of interior child layer requests, with all one-letter words of the participating texts present.