Paper: The Computational Complexity Of Sentence Derivation In Functional Unification Grammar

ACL ID C86-1137
Title The Computational Complexity Of Sentence Derivation In Functional Unification Grammar
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1986
Authors

Functional unification (FU) grammar is a general linguistic formalism based on the merging of feature-sets. An informal outline is given of how the definition of derivation within FU grammar can be used to represent the satisfiability of an arbitrary logical formula in conjunctive normal form. This suggests that the generation of a structure from an arbitrary FU g~ammar is NP-hard, which is an undesirably high level of computational complexity. I. Functional Unification Grammar There is not space here to give a full definition of FU grammar (see Kay (1979, 1984, 1985), Ritchie(1984)); the aim is rather to outline how the problem of satisfiability of a propositional logic expression in conjunctive normal form (CNF) can be expressed as a derivation in FU grammar, thereby suggesting that the ...