Finite-State Language Processing

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.Contributors: 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.Language, Speech, and Communication series