Roche E., Schabes Y. (eds.) Finite-State Language Processing

MIT Press, 1997. — 472 pp.The theory of finite-state automata is rich, and finite-state automata techniques are used in a wide range of domains, including switching theory, pattern matching, pattern recognition, speech processing, handwriting recognition, optical character recognition, encryption algorithm, data compression, indexing, and operating system analysis (e.g., Petri-net).
Finite-state devices, such as finite-state automata, graphs, and finite-state transducers, have been present since the emergence of computer science and are extensively used in areas as various as program compilation, hardware modeling, and database management. Although finite-state devices have been known for some time in computational linguistics, more powerful formalisms such as context-free grammars or unification grammars have typically been preferred. However, recent mathematical and algorithmic results in the field of finite-state technology have had a great impact on the representation of electronic dictionaries and on natural language processing. As a result, a new technology for language is emerging out of both industrial and academic research. This book, a discussion of fundamental finite-state algorithms, constitutes an approach from the perspective of natural language processing.Finite-State Morphology: Inflections and Derivations in a Single Framework Using Dictionaries and Rules
Representations and Finite-State Components in Natural Language
The Replace Operator
Finite-State Approximation of Phrase-Structure Grammars
The Lexical Analysis of Natural Languages
Deterministic Part-of-Speech Tagging with Finite-State Transducers
Parsing with Finite-State Transducers
Designing a (Finite-State) Parsing Grammar
Applying a Finite-State Intersection Grammar
The Construction of Local Grammars
On the Use of Sequential Transducers in Natural Language Processing
FASTUS: A Cascaded Finite-State Transducer for Extracting Information from Natural-Language Text
Rational Transductions for Phonetic Conversion and Phonology
Speech Recognition by Composition of Weighted Finite Automata