Automata, Languages, and Machines (eBook)

Front Cover 1
Automata, Languages, and Machines 4
Copyright Page 5
Contents 8
Preface 14
Chapter I. Preliminaries 18
1. Functions 18
2. Relations and Partial Functions 19
3. Monoids 20
4. Categories 23
5. Equivalences and Congruences 25
6. Miscellaneous Conventions 27
References 28
Chapter II. Automata and Recognizable Sets 29
1. Basic Definitions 29
2. Examples 32
3. Operations on Automata 34
4. Accessibility 38
5. Finiteness and Iteration 41
6. Local Sets 43
References 46
Chapter III. Deterministic Automata 47
1. Basic Definitions 47
2. The Subset Construction 49
3. The Division Calculus 51
4. State-Mappings 55
5. Minimal Automata 60
6. A Decision Problem 66
7. Examples 68
8. The Quotient Criterion 72
9. Right Congruences 76
10. The Syntactic Monoid 78
11. Examples of Syntactic Monoids 82
12. Generalization to Arbitrary Monoids 85
13. Automata of Type ( p , r) 89
References 91
Chapter IV. Structure of Recognizable Sets 93
1. Unitary Sets 93
2. Prefixes 95
3. Unitary Monoids 97
4. The Decomposition Algorithm 100
5. Bases of Unitary Monoids 105
6. Iterated Up-Decomposition 108
7. Maximal Prefixes 109
8. Recurrent States 114
References 116
Chapter V. The Integers 117
1. The Monoid N 117
2. Integers at Base k 120
3. k-Recognizable Sets 123
4. Iteration 127
5. Gap Theorems 128
6. Other Interpretations 132
7. Coding 134
References 135
Chapter VI. Multiplicity 137
1. Multiplicity in Automata 137
2. Semirings 139
3. K-Subsets 143
4. Relations and Functions 146
5. Monoids and Matrices 150
6. K-S-Automata 152
7. Recognizable K-Subsets 156
8. The Equality Theorem 160
9. The Case K = N 164
10. The Division Theorem 167
11. The Subtraction Theorem 170
12. Undecidable Propositions 172
References 175
Chapter VII. Rational Sets 176
1. + -Algebras 176
2. Rational K-Subsets 180
3. Rational Expressions and Identities 183
4. Locally Finite Monoids 187
5. Kleene's Theorem 192
6. Linear Equations 196
7. Examples 199
8. Unambiguous Rational Sets 203
9. The Semirings N and N 205
10. Generalized Automata 208
References 211
Chapter VIII. An Excursion into Analysis 212
1. Generating Functions 212
2. K-Recognizable Power Series 216
3. The Case When k Is a Ring 221
4. The Case K = Z 224
5. Positive Analytic Functions 225
6. R+-Recognizable Functions 232
7. Behavior of Coefficients 236
8. Bernouili Distributions 240
9. Prefixes and Bases 244
References 252
Chapter IX. Rational Relations 253
1. Definitions and Examples 253
2. First Factorization Theorem 257
3. Evaluation Theorem 259
4. Composition Theorem 262
5. Second Factorization Theorem 265
6. Length-Preserving Relations 269
7. A Cross-Section Theorem 273
8. Rational Partial Functions 275
9. Iteration 278
References 282
Chapter X. Machines 283
1. Basic Definitions 283
2. Automata as Machines 288
3. Transducers and Rational Relations 289
4. Accelerated Transducers 293
5. Positive Rational Relations and Transducers 296
6. Two-way Automata 299
7. Other Machines 303
8. Deterministic Machines 305
9. A Conversion Theorem 309
References 312
Chapter XI. Sequential Machines 313
1. Basic Definitions 313
2. Notation and Interpretation 317
3. Properties of Sequential Functions 323
4. Digital Computation 326
5. State-Dependent Sequential Machines 329
6. Recognition of gsp-Functions 331
7. Sequential Bimachines 337
8. Examples of Bimachines 339
9. Proof of Theorem 7.1 342
Chapter XII. Operations on Sequential Machines 347
1. State-Mappings 347
2. Accessibility 350
3. Reduction 352
4. Minimal gs-Machines 355
5. Decision Problems 358
6. The Strong Minimization Problem 360
7. The Synthesis Probleml 365
8. Composition of Sequential Llachines 366
9. 2-Categories 369
10. Parallel Products 371
References 373
Chapter XIII. Infinite Words 375
1. The Sets SN 375
2. Ultimately Periodic Sequences 379
3. Expansion of Real Numbers 380
4. Infinite Digital Computation 385
5. The Peano Curve 388
6. The Hilbert Curve 393
References 395
Chapter XIV. Infinite Behavior of Finite Automata 396
1. Main Definitions and Results 396
2. An Auxiliary Proposition 400
3. Proof of Theorem 403
4. Examples and Exercises 407
References 410
Chapter XV. k-Recognizable Sequences 411
1. k-Recognizable Sequences 411
2. k-Generic Sequences 413
3. Examples and Exercises 416
4. k-Recognizable Sequences and Sequential Functions 418
References 421
Chapter XVI. Linear Sequential Machines 422
1. Algebraic Preliminaries 422
2. Linear Sequential Machines 425
3. The Free Case Comparison with Automata
4. Quality 432
5. Minimization 433
6. Parallel Composition 439
7. Series Composition 441
8. The Case When K Is a Field 444
9. Rationality and Recurrence 448
10. Sequential Functions and Rationality 450
11. Integral Closure and Entire Rings 454
12. The Main Rationality Theorems 456
13. Proof of Theorems 12.1 and 12.2 457
References 461
Index 464