The Setting
The construction assembles Boolean predicates from disjoint blocks of input coordinates. A tournament selects the child inputs used by each row, while a predicate index orders the acceptance sets. Write and . The construction parameters are natural numbers with , , , and ; the recursive definitions also allow arbitrary natural numbers .
A tournament on is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices; write for an edge.✦ A regular tournament with parameter is a tournament on with vertices and outdegree at every vertex.✦ An -labeling on is a map . A good -labeling on is a map such that, for every set of size and every map , there are with and .✦
For a finite coordinate set , a family of predicates on is nested when its acceptance sets satisfy (1). The ordering is on the predicate indices. (1)✦
The Initial Predicates
The block indicator on , for , is the Boolean input specified by (2). (2)✦
For a finite family of centers in and a nonnegative integer , the union of Hamming balls is the predicate defined by (3), where denotes Hamming distance. (3)✦
The initial family on has predicates, with the radii specified by (4). (4)✦
The Claim
Definition 1. Let be a tournament on , let be an -labeling, and let be a finite coordinate set. For an input , its child restriction is defined by (5). (5)✦
For , the reversed gate index is given by (6). (6)✦
Given a family on , the row clause is the Boolean predicate on defined by (7). (7)✦
The recursive family is the family of predicates on specified by (8). (8)✦
For a family on , its extended initial family has length and is defined by (9). (9)✦
The construction base family is the family of Boolean predicates on specified by (10). (10)✦
The tower coordinate sets are the finite sets defined recursively in (11). (11)✦
For base families on of every length , the tower family consists of predicates on and is defined by (12). (12)✦
The construction coordinate set is the finite set specified by (13). (13)✦
For a regular tournament with parameter and a good -labeling , the terminal predicate is defined by (14). (14)✦
In the paper, the result reads: writing for the predicate of index at level , for , partition the parent input into disjoint children of dimension , the preceding input dimension, put for the predicate count and , and let clause at index require for every and for every edge , with the disjunction of the row clauses, distinct children for the targets and gates of each clause, and a resulting family nested in .
What Is Checked
The recursive clauses are stated over finite coordinate sets, an arbitrary tournament and labeling, and Boolean predicate families; the terminal specialization uses a regular tournament and a good labeling.
Theorem 1. Let be a tournament on , let be an -labeling, and let be finite. For a nested child family of length , the recursive acceptance sets satisfy (15). (15)✦
For arbitrary base families , if is nested, the tower acceptance sets satisfy (16). (16)✦
The tower coordinate count is given by (17). (17)✦