• Branch-and-Bound and Constraint Satisfaction allow us to ``hunt down'' non-optimal and impossible solutions and prune them from the search space.
• Solution Synthesis methods then ``gather together'' all optimal solutions while avoiding exponential complexity.

Each of these three general AI techniques will be described. We will look at how how they have been used to solve a variety of problems. These general techniques were extended or used in novel ways in this project. We will describe these extensions in detail and give examples of how they were applied to computational semantic processing. A major contribution of this work will also be in showing how and why Natural Language is a prime candidate for applying these methods, and how they can enable near-linear time processing. As part of this discussion, we will demonstrate the important result that by converting Text Planning to a constraint satisfaction problem, Means-End type planning can be replaced by an efficient constraint-based search through a complex tree. We will examine the results in the light of the Mikrokosmos Machine Translation project. This project is a large-scale Spanish-English MT system implemented at New Mexico State University. We will be able to evaluate the control mechanism presented here against a large corpus of sample texts. In particular, we will show that a search space in the billions or more can be reduced to a few thousand or less, with a corresponding decrease in run-time.