JAUNT: A Constraint Solver for Disjunctive Feature Structures

Some of the modern linguistic theories, such as LFG and unification-based grammars with disjunctions, require an NP-complete process for their analysis. Solving such hard problems efficiently is crucial to the realization of a practical system based on these theories. We have developed a constraint solver named JAUNT for solving various NP-complete problems encountered in the natural language processing field. This paper describes the design and the implementation of JAUNT. JAUNT is not only a constraint solver but a general-purpose programming language whose principal data structure is feature structures. The constraint-satisfaction algorithms employed in JAUNT, namely generalized constraint propagation and forward checking, are also described.