Finite-State Techniques: Automata, Transducers and Bimachines

ISBN-13: 9781108485418 / Angielski / Twarda / 2019 / 314 str.

Stoyan Mihov; Klaus U. Schulz

Opis

This text for graduate students and researchers gives a complete coverage of the field with mathematical rigour, from basics to advanced topics. It closes the gap between theory and real practice by providing full proofs and executable code for all algorithms, showcasing the efficient and elegant solutions that finite-state methods offer.

Recenzje

'… this volume is well written and very detailed. It is thus a nice reference for those results for the interested graduate or researcher …' Andreas Maletti, ZB Math Reviews

Spis treści

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.