We have presented a new control environment for processing computational semantics. By combining and extending the AI techniques known as constraint satisfaction, solution synthesis and branch-and-bound, we have reduced the search space from billions or more to thousands or less. We have argued that the search problems encountered in computational semantics fit nicely into the class of problems that this control paradigm handle well.
In the past, the utility of knowledge-based semantics has been limited, subject to arguments that it only works in ``toy'' environments. Recent efforts at increasing the size of knowledge bases, however, have created an imbalance with existing control techniques which are unable to handle the explosion of information. We believe that this methodology will enable such work. Furthermore, we believe that it is applicable to a wide variety of real-life problems. Our work in graph coloring is a beginning step towards using this research in other areas.