Muutke küpsiste eelistusi

Finite-State Techniques: Automata, Transducers and Bimachines [Kõva köide]

4.50/5 (4 hinnangut Goodreads-ist)
(Ludwig-Maximilians-Universität Munchen),
  • Formaat: Hardback, 314 pages, kõrgus x laius x paksus: 234x158x21 mm, kaal: 570 g, Worked examples or Exercises; 3 Tables, black and white; 8 Halftones, black and white; 38 Line drawings, black and white
  • Sari: Cambridge Tracts in Theoretical Computer Science
  • Ilmumisaeg: 01-Aug-2019
  • Kirjastus: Cambridge University Press
  • ISBN-10: 1108485413
  • ISBN-13: 9781108485418
Teised raamatud teemal:
Finite-State Techniques: Automata, Transducers and BimachinesSuurem pilt
  • Formaat: Hardback, 314 pages, kõrgus x laius x paksus: 234x158x21 mm, kaal: 570 g, Worked examples or Exercises; 3 Tables, black and white; 8 Halftones, black and white; 38 Line drawings, black and white
  • Sari: Cambridge Tracts in Theoretical Computer Science
  • Ilmumisaeg: 01-Aug-2019
  • Kirjastus: Cambridge University Press
  • ISBN-10: 1108485413
  • ISBN-13: 9781108485418
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781108485418.html
Märksõnad:
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.

Arvustused

' 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

Muu info

Covers the whole spectrum of finite-state methods, from theory to practical applications.
Preface ix
PART I FORMAL BACKGROUND
1 Formal Preliminaries
3(20)
1.1 Sets, Functions and Relations
3(5)
1.2 Lifting Functions to Sets and Tuples
8(2)
1.3 Alphabets, Words and Languages
10(3)
1.4 Word Tuples, String Relations and String Functions
13(3)
1.5 The General Monoidal Perspective
16(4)
1.6 Summing Up
20(1)
1.7 Exercises for
Chapter 1
21(2)
2 Monoidal Finite-State Automata
23(20)
2.1 Basic Concept and Examples
23(7)
2.2 Closure Properties of Monoidal Finite-State Automata
30(3)
2.3 Monoidal Regular Languages and Monoidal Regular Expressions
33(2)
2.4 Equivalence Between Monoidal Regular Languages and Monoidal Automaton Languages
35(2)
2.5 Simplifying the Structure of Monoidal Finite-State Automata
37(4)
2.6 Summing Up
41(1)
2.7 Exercises for
Chapter 2
41(2)
3 Classical Finite-State Automata and Regular Languages
43(29)
3.1 Deterministic Finite-State Automata
43(3)
3.2 Determinization of Classical Finite-State Automata
46(2)
3.3 Additional Closure Properties for Classical Finite-State Automata
48(2)
3.4 Minimal Deterministic Finite-State Automata and the Myhill-Nerode Equivalence Relation
50(7)
3.5 Minimization of Deterministic Finite-State Automata
57(5)
3.6 Coloured Deterministic Finite-State Automata
62(5)
3.7 Pseudo-Determinization and Pseudo-Minimization of Monoidal Finite-State Automata
67(2)
3.8 Summing Up
69(1)
3.9 Exercises for
Chapter 3
69(3)
4 Monoidal Multi-Tape Automata and Finite-State Transducers
72(22)
4.1 Monoidal Multi-Tape Automata
72(3)
4.2 Additional Closure Properties of Monoidal Multi-Tape Automata
75(2)
4.3 Classical Multi-Tape Automata and Letter Automata
77(3)
4.4 Monoidal Finite-State Transducers
80(3)
4.5 Classical Finite-State Transducers
83(2)
4.6 Deciding Functionality of Classical Finite-State Transducers
85(5)
4.7 Summing Up
90(1)
4.8 Exercises for
Chapter 4
91(3)
5 Deterministic Transducers
94(44)
5.1 Deterministic Transducers and Subsequential Transducers
94(6)
5.2 A Determinization Procedure for Functional Transducers with the Bounded Variation Property
100(8)
5.3 Deciding the Bounded Variation Property
108(7)
5.4 Minimal Subsequential Finite-State Transducers: Myhill-Nerode Relation for Subsequential Transducers
115(8)
5.5 Minimization of Subsequential Transducers
123(10)
5.6 Numerical Subsequential Transducers
133(2)
5.7 Summing Up
135(1)
5.8 Bibliographic Notes
135(1)
5.9 Exercises for
Chapter 5
136(2)
6 Bimachines
138(23)
6.1 Basic Definitions
138(7)
6.2 Equivalence of Regular String Functions and Classical Bimachines
145(4)
6.3 Pseudo-Minimization of Monoidal Bimachines
149(2)
6.4 Direct Composition of Classical Bimachines
151(5)
6.5 Summing Up
156(1)
6.6 Exercises for
Chapter 6
156(5)
PART II FROM THEORY TO PRACTICE
7 The C(M) language
161(16)
7.1 Basics and Simple Examples
161(7)
7.2 Types, Terms and Statements in C(M)
168(9)
8 C(M) Implementation of Finite-State Devices
177(59)
8.1 C(M) Implementations for Automata Algorithms
177(17)
8.2 C(M) Programs for Classical Finite-State Transducers
194(17)
8.3 C(M) Programs for Deterministic Transducers
211(11)
8.4 C(M) Programs for Bimachines
222(14)
9 The Aho-Corasick Algorithm
236(17)
9.1 Formal Construction -- First Version
236(8)
9.2 Linear Computation of the Aho-Corasick Automaton
244(2)
9.3 Space-Efficient Variant -- Construction of the Aho-Corasick f-Automaton
246(7)
10 The Minimal Deterministic Finite-State Automaton for a Finite Language
253(26)
10.1 Formal Construction
253(5)
10.2 C(M) Implementation of the Construction - First Version
258(4)
10.3 Efficient Construction of the Minimal Dictionary Automaton
262(3)
10.4 Adapting the Language of Minimal Dictionary Automata
265(5)
10.5 The Minimal Subsequential Transducer for a Finite Two-Sided Dictionary
270(9)
11 Constructing Finite-State Devices for Text Rewriting
279(19)
11.1 Simple Text Rewriting Based on Regular Relations
280(2)
11.2 Using Deterministic Machines for Simple Text Rewriting
282(6)
11.3 Leftmost-Longest Match Text Rewriting
288(2)
11.4 Regular Relations for Leftmost-Longest Match Rewriting
290(8)
References 298(4)
Index 302
Stoyan Mihov is Associate Professor at the Bulgarian Academy of Sciences (IICT) and a lecturer at Sofia University. He has published several efficient automata constructions and approximate search methods, which are widely used for natural language processing and information retrieval. Dr Mihov has led the development of multiple award-winning systems for language and speech processing. Klaus U. Schulz is Professor of Information and Language Processing at the Ludwig-Maximilians-Universität Munchen. He has published over 100 articles in distinct fields of computer science, with contributions in approximate search and transducer technology. He was head of many projects in text-correction and digital humanities, on both a national and European level.