Unification Grammars

"Grammars of natural languages can be expressed as mathematical objects, similar to computer programs. Such a formal presentation of grammars facilitates mathematical reasoning with grammars (and the languages they denote), as well as computational implementation of grammar processors. This book presents one of the most commonly used grammatical formalisms, Unification Grammars, which underlies contemporary linguistic theories such as Lexical-Functional Grammar (LFG) and Head-driven Phrase Structure Grammar (HPSG). The book provides a robust and rigorous exposition of the formalism that is both mathematically well-founded and linguistically motivated. While the material is presented formally, and much of the text is mathematically oriented, a core chapter of the book addresses linguistic applications and the implementation of several linguistic insights in unification grammars. Dozens of examples and numerous exercises (many with solutions) illustrate key points. Graduate students and researchers in both computer science and linguistics will find this book a valuable resource"--Provided by publisher. Contents......Page 3 Preface......Page 5 Introduction......Page 8 1.1 Syntax: the structure of natural languages......Page 10 1.2 Linguistic formalisms......Page 11 1.3 A gradual description of language fragments......Page 13 1.4 Formal languages......Page 19 1.5 Context-free grammars......Page 21 1.6 CFGs and natural languages......Page 29 1.7 Mildly context-sensitive languages......Page 36 1.8 Motivating an extended formalism......Page 37 Reading......Page 39 Feature structures......Page 41 2.1 Motivation......Page 42 2.2 Feature graphs......Page 44 2.3 Feature structures......Page 59 2.4 Abstract feature structures......Page 61 2.5 Attribute-value matrices......Page 71 2.6 The correspondence between feature graphs and AVMs......Page 81 2.7 Feature structures in a broader context......Page 90 Reading......Page 91 3.1 Feature structure unification......Page 92 3.2 Feature-graph unification......Page 93 3.3 Feature structure unification revisited......Page 100 3.4 Unification as a computational process......Page 101 3.5 AFS unification......Page 106 3.6 Generalization......Page 115 Reading......Page 120 Unification grammars......Page 122 4.1 Motivation......Page 123 4.2 Multirooted feature graphs......Page 125 4.3 Abstract multirooted structures......Page 132 4.4 Multi-AVMs......Page 137 4.5 Unification revisited......Page 144 4.6 Rules and grammars......Page 153 4.7 Derivations......Page 158 4.8 Derivation trees......Page 164 Reading......Page 170 Linguistic applications......Page 172 5.1 A basic grammar......Page 173 5.2 Imposing agreement......Page 174 5.3 Imposing case control......Page 179 5.4 Imposing subcategorization constraints......Page 181 5.5 Subcategorization lists......Page 185 5.6 Long-distance dependencies......Page 192 5.7 Relative clauses......Page 198 5.8 Subject and object control......Page 204 5.9 Constituent coordination......Page 208 5.10 Unification grammars and linguistic generalizations......Page 215 5.11 Unification-based linguistic formalisms......Page 216 Reading......Page 218 Computational aspects of unification grammars......Page 220 6.1 Expressiveness of unification grammars......Page 221 6.2 Unification grammars and Turing machines......Page 233 6.3 Off-line parsability......Page 240 6.4 Branching unification grammars......Page 246 6.5 Polynomially parsable unification grammars......Page 251 6.6 Unification grammars for natural languages......Page 258 6.7 Parsing with unification grammars......Page 260 Reading......Page 280 Conclusion......Page 282 Symbols......Page 284 Relations......Page 287 Graphs......Page 288 Computation......Page 289 1.9.......Page 291 2.6.......Page 292 2.20.......Page 293 2.35.......Page 294 3.14.......Page 295 4.3.......Page 296 4.13.......Page 297 4.24.......Page 298 5.1.......Page 299 5.6.......Page 300 5.9.......Page 301 6.1. 6.3.......Page 302 6.11.......Page 303 6.22.......Page 304 Biblio......Page 305 Index......Page 312 Grammars of natural languages can be expressed as mathematical objects, similar to computer programs. Such a formal presentation of grammars facilitates mathematical reasoning with grammars (and the languages they denote) on one hand, and computational implementation of grammar processors on the other hand. This book presents one of the most commonly used grammatical formalisms, Unification Grammars, which underlies contemporary linguistic theories such as Lexical-Functional Grammar (LFG) and Head-driven Phrase Structure Grammar (HPSG). The book provides a robust and rigorous exposition of the formalism which is both mathematically well-founded and linguistically motivated. While the material is presented formally, and much of the text is mathematically oriented, a core chapter of the book addresses linguistic applications and the implementation of several linguistic insights in unification grammars. Dozens of examples and numerous exercises (many with solutions) illustrate key points. Graduate students and researchers in both computer science and linguistics will find this book a valuable resource. Machine generated contents note: 1. Introduction; 2. Feature structures; 3. Unification; 4. Unification grammars; 5. Linguistic applications; 6. Computational aspects of unification grammars; 7. Conclusion.