Paper: Expressing Disjunctive And Negative Feature Constraints With Classical First-Order Logic

ACL ID P90-1022
Title Expressing Disjunctive And Negative Feature Constraints With Classical First-Order Logic
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1990
Authors

In contrast to the "designer logic" approach, this paper shows how the attribute-value feature structures of unification grammar and constraints on them can be axiomatized in classical first-order logic, which can express disjunctive and negative constraints. Because only quantifier-free formulae are used in the axiomatization, the satisfiability problem is NP- complete.