The Setting
A point in a dyadic routing construction queries one cell in each selector table. At a decision node, the first successful selector chooses a child; if all selectors vanish, the route takes the default child. The local success test below concerns one nondefault subtree and the terminal table reached inside it.
Let . The child alphabet is , with default child and nondefault children .✦ Thus the paper’s parameter for the total number of children is in this notation. A decision node is a word over of length less than ✦, and a terminal path is a word of length .✦ Their sets and are defined in (1); denotes concatenation with the child , and is the empty word. (1)
The periodic mesh key , for , and the finite dyadic key , for , are the indices in (2), where . At level , the periodic grid cells are the half-open intervals modulo one. (2)
Fix selector resolutions for and , and terminal resolutions for . The selector address set and terminal address set are the sets of pairs of table labels and grid indices given in (3). A selector table and a terminal table are Boolean functions on these respective address sets. (3)
The queried selector and terminal addresses at are and in (4). (4) The extended selector value is the Boolean function on all words in (5). For a Boolean vector , the first-success rule chooses the least nondefault child with , or if there is none.✦ For a center , the pointwise selector choice and the center choice are also defined there. (5)
For a child-choice map , the iterated route is the word obtained by the recursion in (6). The local routed leaf associated to a child-choice map , a starting word , and a parameter is the word when .✦ Write ; the local leaf starts at the nondefault child of a decision node . (6)
Fix a center and a Boolean assignment . The zero-filled exposure completion is the selector table in (7). (7)✦
Window Endpoints
An admissible edge path over is a nonempty word with .✦ Separated window data , with natural parameters , consist of a natural-valued function on and natural-valued assignments on words satisfying the window conditions in (8) and the separation conditions in (9). Put . (8) For admissible paths , write for the prefix relation and for a proper prefix. The descendant bounds and prefix separation are the first two conditions of (9). Its last condition is the sibling separation, for words and children whenever and are admissible. (9) For a decision node and a nondefault child , the nondefault child edge is the path obtained by concatenating and . The selector window endpoints and terminal window endpoints of supply the resolutions in (10). (10)
The Claim
Theorem 1 (Center exposure and local tests). For arbitrary selector and terminal resolutions, the full center exposure is the Boolean assignment in (11). The center exposure fiber of a Boolean assignment at the center is the set of selector and terminal table pairs in (12). (11)✦ (12)✦ A good exposure at the center is a Boolean assignment on whose completed center route uses a default child, as specified by (13). (13)✦ For a child-choice map , starting word and parameter , an index is a first default stage when it satisfies (14); write for this condition. (14)✦ If is good, there are an index and a decision node with such that (15) holds for every selector table with . (15)✦ For separated window data , tables at the endpoint resolutions (10), a decision node , a nondefault child , and , the local selector-terminal test is the Boolean value in (16). (16)✦
In the paper, the result reads: writing for the selector table with label and resolution , and for the terminal table with label and resolution , at a fixed center , expose in every selector table, including unvisited subtrees, so that the finite exposure atoms determine the center’s path and, when it exists, its first default node ; for a nondefault child of , let be the route starting from and let .
What Is Checked
The center exposure fiber and good-exposure condition are stated over arbitrary natural , real centers and Boolean selector assignments; the first default assertion uses a good assignment, while the local test uses separated window data with total children and both selector and terminal tables.
For a decision node and a nondefault child , the local routing depth identity is (17). (17)✦