Unification Grammars

by Francez, Nissim; Wintner, Shuly

• ISBN13: 9781107014176
• ISBN10: 1107014174
• Format: Hardcover
• Copyright: 2011-09-30
• Publisher: Cambridge Univ Pr

Summary

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.

Author Biography

Nissim Francez is professor emeritus of computer science at the Technion-Israel Institute of Technology. His research for the last twenty years has focused on computational linguistics in general, and on the formal semantics of natural language in particular, mainly within the framework of type-logical grammar. His most recent research topic is proof-theoretic semantics for natural language. He is the author of several books and approximately 150 scientific articles. He regularly serves on editorial boards and program committees of several major conferences, including the committee of the FoLLI (Association for Logic, Language, and Information) Beth Dissertation Award. Shuly Wintner is associate professor of computer science at the University of Haifa, Israel. His areas of interest include computational linguistics and natural language processing, with a focus on formal grammars, morphology, syntax, and Semitic languages. He is the author or editor of nearly 100 publications. He has served on the program committees of numerous conferences, as a member of the standing committee overseeing the yearly Formal Grammar conference, and as the editor-in-chief of the journal Research in Language and Computation.

Table of Contents

Preface	p. ix
Acknowledgments	p. xii
Introduction	p. 1
Syntax: the structure of natural languages	p. 3
Linguistic formalisms	p. 4
A gradual description of language fragments	p. 6
Formal languages	p. 12
Context-free grammars	p. 14
CFGs and natural languages	p. 22
Mildly context-sensitive languages	p. 29
Motivating an extended formalism	p. 30
Feature structures	p. 34
Motivation	p. 35
Feature graphs	p. 37
Feature structures	p. 52
Abstract feature structures	p. 54
Attribute-value matrices	p. 64
The correspondence between feature graphs and AVMs	p. 74
Feature structures in a broader context	p. 83
Unification	p. 85
Feature structure unification	p. 85
Feature-graph unification	p. 86
Feature structure unification revisited	p. 93
Unification as a computational process	p. 94
AFS unification	p. 99
Generalization	p. 108
Unification grammars	p. 115
Motivation	p. 116
Multirooted feature graphs	p. 118
Abstract multirooted structures	p. 125
Multi-AVMs	p. 130
Unification revisited	p. 137
Rules and grammars	p. 146
Derivations	p. 151
Derivation trees	p. 157
Linguistic applications	p. 165
A basic grammar	p. 166
Imposing agreement	p. 167
Imposing case control	p. 172
Imposing subcategorization constraints	p. 174
Subcategorization lists	p. 178
Long-distance dependencies	p. 185
Relative clauses	p. 191
Subject and object control	p. 197
Constituent coordination	p. 201
Unification grammars and linguistic generalizations	p. 208
Unification-based linguistic formalisms	p. 209
Computational aspects of unification grammars	p. 213
Expressiveness of unification grammars	p. 214
Unification grammars and Turing machines	p. 226
Off-line parsability	p. 233
Branching unification grammars	p. 239
Polynomially parsable unification grammars	p. 244
Unification grammars for natural languages	p. 251
Parsing with unification grammars	p. 253
Conclusion	p. 275
List of symbols	p. 277
Preliminary mathematical notions	p. 280
Solutions to selected exercises	p. 284
Bibliography	p. 299
Index	p. 307
Table of Contents provided by Ingram. All Rights Reserved.