In summary, this research provides the machinery for a fast, complete and sound search through many types constraint problems, including natural language semantics. Previously in computational semantics work, researchers needed to make one or more of three simplifications:
Each of these simplifications often leads to non-optimal solutions. In addition, generalized problems such as graph-coloring do not allow, or severely limit, such simplifications. HUNTER-GATHERER removes the need for them by providing a method for organizing and processing search using minimally interacting sub-problems.
This research advances three central theoretical contributions. First is the recognition that solution synthesis methods should not be limited to combining, at the lowest level, pairs of variables, as in Freuder and Tsang, nor need it be content to blindly synthesize combinations of these pairs. HUNTER-GATHERER organizes the search space into maximally independent subgroups of any size, and then guides the synthesis process as it combines results from these subgroups. A related contribution is the process by which HUNTER-GATHERER produces these input subgraphs and synthesis plans in non-exponential time.
The second major theoretical contribution is the use of branch-and-bound optimization techniques to prune the results of synthesis. Previously, only constraint satisfaction techniques were used in this role. The use of branch-and-bound techniques was precipitated by the fact that natural language semantics often does not allow straightforward yes-or-no constraints of the type needed by previous solution synthesis methods. It turns out that, even in more general problems such as graph coloring in which yes-or-no constraints can be used, branch-and-bound pruning significantly outperforms constraint-based pruning. HUNTER-GATHERER, in fact, uses both.
The final major theoretical contribution combines aspects from the first two. Tsang suggests using a ``minimal bandwidth ordering'' (MBO) algorithm to order the input variables in such a way as to maximize the benefits of early constraint pruning. HUNTER-GATHERER extends the concept of MBO to its branch-and-bound optimization. Input subgroups are constructed in such a way as to minimize the interaction outside of the subgraphs, which in turn allow maximal pruning based on branch-and-bound techniques.
A peripheral contribution of this work is the recognition that solution synthesis techniques could be applied to these types of problems. Previously, solution synthesis was used exclusively for constraint satisfaction problems. By substituting branch-and-bound techniques for constraint satisfaction, a whole new set of problems can utilize solution synthesis techniques.