The Handbook provides a comprehensive overview of the concepts, methodologies, and applications being undertaken today in computational linguistics and natural language processing. The Handbook provides a comprehensive overview of the concepts, methodologies, and applications being undertaken today in computational linguistics and natural language processing. List of Figures ix List of Tables xiv Notes on Contributors xv Preface xxiii Introduction 1 Part I Formal Foundations 9 1 Formal Language Theory 11 SHULY WINTNER 2 Computational Complexity in Natural Language 43 IAN PRATT-HARTMANN 3 Statistical Language Modeling 74 CIPRIAN CHELBA 4 Theory of Parsing 105 MARK-JAN NEDERHOF AND GIORGIO SATTA Part II Current Methods 131 5 Maximum Entropy Models 133 ROBERT MALOUF 6 Memory-Based Learning 154 WALTER DAELEMANS AND ANTAL VAN DEN BOSCH 7 Decision Trees 180 HELMUT SCHMID 8 Unsupervised Learning and Grammar Induction 197 ALEXANDER CLARK AND SHALOM LAPPIN 9 Artificial Neural Networks 221 JAMES B. HENDERSON 10 Linguistic Annotation 238 MARTHA PALMER AND NIANWEN XUE 11 Evaluation of NLP Systems 271 PHILIP RESNIK AND JIMMY LIN Part III Domains of Application 297 12 Speech Recognition 299 STEVE RENALS AND THOMAS HAIN 13 Statistical Parsing 333 STEPHEN CLARK 14 Segmentation and Morphology 364 JOHN A. GOLDSMITH 15 Computational Semantics 394 CHRIS FOX 16 Computational Models of Dialogue 429 JONATHAN GINZBURG AND RAQUEL FERNÁNDEZ 17 Computational Psycholinguistics 482 MATTHEW W. CROCKER Part IV Applications 515 18 Information Extraction 517 RALPH GRISHMAN 19 Machine Translation 531 ANDY WAY 20 Natural Language Generation 574 EHUD REITER 21 Discourse Processing 599 RUSLAN MITKOV 22 Question Answering 630 BONNIE WEBBER AND NICK WEBB References 655 Author Index 742 Subject Index 763