The Setting
The connection problem is to pass through a band of periodic layers while controlling the number of appended symbols. The relevant graph has finite words as vertices and allows a word to grow at its right end or shrink at its left end.
A substring-closed vertex set over an alphabet is a set of finite words containing every contiguous substring of each of its words, including the empty word.✦ A hierarchical walk in is a finite sequence of steps between vertices of , each appending one symbol at the right or deleting the first symbol.✦ Stationary walks are allowed, and walks with a common endpoint can 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 is its number of append steps.✦ Costs add under concatenation.
For an integer-indexed text , the finite window is the word of symbols at positions when , and the empty word when .✦
A periodic layer for , and a parameter is an integer-valued exit function satisfying (1); all variables in these conditions are integers. (1)✦ The first and last exit positions of at a start are the endpoints and defined in (2). (2) A walk touches a layer when it visits a window with endpoints satisfying (3). (3)✦
The Claim
Theorem 1. Let be substring-closed, and let be a text whose one-letter words all belong to . Let , and suppose for every integer .
Let be a family of periodic layers for , and , with designated bottom and top layers and . Suppose every exit function lies pointwise between and . Let satisfy .
There is a closed hierarchical walk based at with the band tour bound (4). (4)✦
What Is Checked
The claim is stated over hierarchical walks in a substring-closed word set and a family of layers of an integer-indexed periodic text, bounded pointwise by two designated layers.