A Method for Disjunctive Constraint Satisfaction

摘要: A distinctive property of many current grammatical formalisms is their use feature equality constraints to express a wide variety dependencies. Lexical-Functional Grammar (Kaplan & Bresnan, 1982), Head-Driven Phrase-Structure (Pollard Sag, 1987), PATR (Karttunen, 1986a), FUG (Kay, 1979, 1985), and the various forms categorial unification grammar 1986b; Uszkoreit, 1986; Zeevat, Klein, Calder, 1987) all require an analysis sentence satisfy collection in addition set conditions on arrangement words phrases. Conjunctions can be quickly solved by standard algorithms, so they themselves do not present computational problem. However, derived for typical sentences are merely conjoined together form that algorithms deal with directly. Rather, embedded as primitive elements complex disjunctive formulas. For some formalisms, these disjunctions arise from explicit disjunction operators constraint language provides (e.g., LFG) while others application alternative phrase structure rules PATR). In either case, specifications help simplify statement possibilities. Alternatives expressed locally within individual lexical entries appeal more general processing mechanisms resolve global interactions.