Finite-state techniques : automata, transducers and bimachines
Author(s)
Bibliographic Information
Finite-state techniques : automata, transducers and bimachines
(Cambridge tracts in theoretical computer science, 60)
Cambridge University Press, 2019
- : hardback
Available at 3 libraries
  Aomori
  Iwate
  Miyagi
  Akita
  Yamagata
  Fukushima
  Ibaraki
  Tochigi
  Gunma
  Saitama
  Chiba
  Tokyo
  Kanagawa
  Niigata
  Toyama
  Ishikawa
  Fukui
  Yamanashi
  Nagano
  Gifu
  Shizuoka
  Aichi
  Mie
  Shiga
  Kyoto
  Osaka
  Hyogo
  Nara
  Wakayama
  Tottori
  Shimane
  Okayama
  Hiroshima
  Yamaguchi
  Tokushima
  Kagawa
  Ehime
  Kochi
  Fukuoka
  Saga
  Nagasaki
  Kumamoto
  Oita
  Miyazaki
  Kagoshima
  Okinawa
  Korea
  China
  Thailand
  United Kingdom
  Germany
  Switzerland
  France
  Belgium
  Netherlands
  Sweden
  Norway
  United States of America
Note
Includes bibliographical references (p. 298-301) and index
Description and Table of Contents
Description
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.
Table of Contents
- 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.
by "Nielsen BookData"