Cambridge Tracts in Theoretical Computer Science
Finite-state methods are
the most efficient mechanisms for analysing textual and symbolic data, providing elegant solutions for an immense number of
practical problems in computational linguistics and computer science. This book for graduate students and researchers gives
a complete coverage of the field, starting from a conceptual introduction and building to advanced topics and applications.
The central finite-state technologies are introduced with mathematical rigour, ranging from simple finite-state automata to
transducers and bimachines as 'input-output' devices. Special attention is given to the rich possibilities of simplifying,
transforming and combining finite-state devices. All algorithms presented are accompanied by full correctness proofs and executable
source code in a new programming language, C(M), which focuses on transparency of steps and simplicity of code. Thus, by enabling
readers to obtain a deep formal understanding of the subject and to put finite-state methods to real use, this book closes
the gap between theory and practice.
Part I. Formal Background: 1. Formal preliminaries; 2. Monoidal finite-state automata;
3. Classical finite-state automata and regular languages; 4. Monoidal multi-tape automata and finite-state transducers; 5.
Deterministic transducers; 6. Bimachines; Part II. From Theory to Practice: 7. The C(M) language; 8. C(M) implementation of
finite-state devices; 9. The Aho-Corasick algorithm; 10. The minimal deterministic finite-state automaton for a finite language;
11. Constructing finite-state devices for text rewriting; Bibliography; Index.
Covers the whole spectrum of finite-state
methods, from theory to practical applications.