Finite-state devices, which include finite-state automata, graphs, and finite-state transducers, are in wide use in many areas of computer science. Recently, there has been a resurgence of the use of finite-state devices in all aspects of computational linguistics, including dictionary encoding, text processing, and speech processing. This book describes the fundamental properties of finite-state devices and illustrates their uses. Many of the contributors pioneered the use of finite-automata for different aspects of natural language processing. The topics, which range from the theoretical to the applied, include finite-state morphology, approximation of phrase-structure grammars, deterministic part-of-speech tagging, application of a finite-state intersection grammar, a finite-state transducer for extracting information from text, and speech recognition using weighted finite automata. The introduction presents the basic theoretical results in finite-state automata and transducers. These results and algorithms are described and illustrated with simple formal language examples as well as natural language examples.
Douglas Appelt, John Bear, David Clemenceau, Maurice Gross, Jerry R. Hobbs, David Israel, Megumi Kameyama, Lauri Karttunen, Kimmo Koskenniemi, Mehryar Mohri, Eric Laporte, Fernando C. N. Pereira, Michael D. Riley, Emmanuel Roche, Yves Schabes, Max D. Silberztein, Mark Stickel, Pasi Tapanainen, Mabry Tyson, Atro Voutilainen, Rebecca N. Wright
“The papers in this collection are highly original, written in most cases by the authors who have pioneered the use of finite automata in natural language processing. This compendium will be one of the most important contributions to computational linguistics of the last ten years. It will occupy a central place in the ongoing debate about the use of analytic vs. statistic techniques as well as being a reference work that can also be used for advanced computational linguistics courses. Researchers in theoretical linguistics and computer science will also benefit from it.”
—Frank Guenthner, Centrum für Informations und Sprachverarbeitung (CIS), Ludwig-Maximilians Universität Munchen
“Emmanuel Roche and Yves Schabes have put together a picture of the state of the art in using finite-state techniques in computational linguistics. The contributing authors comprise an impressive collection—essentially the originating sources for much of the important recent work in this area.”
—Philip Resnik, Assistant Professor, Department of Linguistics and Institute for Advanced Computer Studies, University of Maryland at College Park