Finite-state techniques : automata, transducers and bimachines /
Stoyan Mihov, Klaus U. Schulz.
Bok Engelsk 2019 · Electronic books.
| Annen tittel | |
|---|---|
| Medvirkende | Schulz, K. U. (author.)
|
| Utgitt | Cambridge University Press
|
| Omfang | 1 online resource (x, 304 pages) : : digital, PDF file(s).
|
| Utgave | 1st ed.
|
| Opplysninger | Title from publisher's bibliographic system (viewed on 29 Jul 2019).. - Cover -- Half-title page -- Series page -- Title page -- Copyright page -- Contents -- Preface -- Part I FORMAL BACKGROUND -- 1 Formal Preliminaries -- 1.1 Sets, Functions and Relations -- 1.2 Lifting Functions to Sets and Tuples -- 1.3 Alphabets, Words and Languages -- 1.4 Word Tuples, String Relations and String Functions -- 1.5 The General Monoidal Perspective -- 1.6 Summing Up -- 1.7 Exercises for Chapter 1 -- 2 Monoidal Finite-State Automata -- 2.1 Basic Concept and Examples -- 2.2 Closure Properties of Monoidal Finite-State Automata -- 2.3 Monoidal Regular Languages and Monoidal Regular Expressions -- 2.4 Equivalence Between Monoidal Regular Languages and Monoidal Automaton Languages -- 2.5 Simplifying the Structure of Monoidal Finite-State Automata -- 2.6 Summing Up -- 2.7 Exercises for Chapter 2 -- 3 Classical Finite-State Automata and Regular Languages -- 3.1 Deterministic Finite-State Automata -- 3.2 Determinization of Classical Finite-State Automata -- 3.3 Additional Closure Properties for Classical Finite-State Automata -- 3.4 Minimal Deterministic Finite-State Automata and the Myhill-Nerode Equivalence Relation -- 3.5 Minimization of Deterministic Finite-State Automata -- 3.6 Coloured Deterministic Finite-State Automata -- 3.7 Pseudo-Determinization and Pseudo-Minimization of Monoidal Finite-State Automata -- 3.8 Summing Up -- 3.9 Exercises for Chapter 3 -- 4 Monoidal Multi-Tape Automata and Finite-State Transducers -- 4.1 Monoidal Multi-Tape Automata -- 4.2 Additional Closure Properties of Monoidal Multi-Tape Automata -- 4.3 Classical Multi-Tape Automata and Letter Automata -- 4.4 Monoidal Finite-State Transducers -- 4.5 Classical Finite-State Transducers -- 4.6 Deciding Functionality of Classical Finite-State Transducers -- 4.7 Summing Up -- 4.8 Exercises for Chapter 4 -- 5 Deterministic Transducers.. - 11.2 Using Deterministic Machines for Simple Text Rewriting -- 11.3 Leftmost-Longest Match Text Rewriting -- 11.4 Regular Relations for Leftmost-Longest Match Rewriting -- References -- Index.. - 5.1 Deterministic Transducers and Subsequential Transducers -- 5.2 A Determinization Procedure for Functional Transducers with the Bounded Variation Property -- 5.3 Deciding the Bounded Variation Property -- 5.4 Minimal Subsequential Finite-State Transducers: Myhill-Nerode Relation for Subsequential Transducers -- 5.5 Minimization of Subsequential Transducers -- 5.6 Numerical Subsequential Transducers -- 5.7 Summing Up -- 5.8 Bibliographic Notes -- 5.9 Exercises for Chapter 5 -- 6 Bimachines -- 6.1 Basic Definitions -- 6.2 Equivalence of Regular String Functions and Classical Bimachines -- 6.3 Pseudo-Minimization of Monoidal Bimachines -- 6.4 Direct Composition of Classical Bimachines -- 6.5 Summing Up -- 6.6 Exercises for Chapter 6 -- Part II FROM THEORY TO PRACTICE -- 7 The C(M) language -- 7.1 Basics and Simple Examples -- 7.2 Types, Terms and Statements in C(M) -- 8 C(M) Implementation of Finite-State Devices -- 8.1 C(M) Implementations for Automata Algorithms -- 8.2 C(M) Programs for Classical Finite-State Transducers -- 8.3 C(M) Programs for Deterministic Transducers -- 8.4 C(M) Programs for Bimachines -- 9 The Aho-Corasick Algorithm -- 9.1 Formal Construction - First Version -- 9.2 Linear Computation of the Aho-Corasick Automaton -- 9.3 Space-Efficient Variant - Construction of the Aho-Corasick f-Automaton -- 10 The Minimal Deterministic Finite-State Automaton for a Finite Language -- 10.1 Formal Construction -- 10.2 C(M) Implementation of the Construction - First Version -- 10.3 Efficient Construction of the Minimal Dictionary Automaton -- 10.4 Adapting the Language of Minimal Dictionary Automata -- 10.5 The Minimal Subsequential Transducer for a Finite Two-Sided Dictionary -- 11 Constructing Finite-State Devices for Text Rewriting -- 11.1 Simple Text Rewriting Based on Regular Relations.. - 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.
|
| Emner | |
| Sjanger | |
| Dewey | |
| ISBN | 1-108-75694-8
|
