Paper: On The Satisfiability Of Complex Constraints

ACL ID C92-1020
Title On The Satisfiability Of Complex Constraints
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1992
  • Luis Damas (University of Porto, Porto Portugal)

The main problem arising from the use of com- plex constraints in Computational Linguists is due to the NP-hardness of checking whether a given set of constraints is satisfiable and, in the affirmative case, of generating the set of min- imal models which satisfy the constraints. In this "paper we show how the CLG approach to rewriting constraints while constructing a par- tial model can greatly reduce the size of the original constraints and thus contribute to re- duce the computational problem.