Automata, Languages, and Machines (eBook)

Front Cover 1
Automata, Languages, and Machines 4
Copyright Page 5
Contents 6
Preface 12
Chapter I. Transformation Semigroups 16
1. Semigroups, Monoids, and Groups 16
2. Transformation Semigroups 18
3. Examples of Transformation Semigroups 20
4. Coverings 23
5. Coverings of Semigroups 27
6. Inclusions and Restrictions 29
7. Isomorphisms and Equivalences 31
8. Join, Sum, and Direct Product 33
9. Some Simple Inequalities 37
10. The Wreath Product 41
References 47
Chapter II. Decomposition Theorems 48
1. Decompositions 48
2. Decomposition of Groups 49
3. Some UsefuI Decompositions 51
4. The Krohn–Rhodes Decomposition 54
5. Comments on the Proof 58
6. Height, Pavings, and Holonomy 58
7. The Holonomy Decomposition Theorem 61
8. Proof of Proposition 7.3 63
9. Examples 66
References 72
Chapter III. Transformation Semigroups (continued) 74
1. Classes and Closed Classes 74
2. Sinks in a ts 77
3. Transitivity Classes 81
4. Idempotents in Semigroups 82
5. Idempotents in a ts 84
6. Localization 87
7. Closed Classes Containing 2 89
8. The Derived ts and the Trace of a Covering 91
9. The Delay Covering 95
References 101
Chapter IV. Primes 102
1. The Exclusion Operator 102
2. Primes 103
3. Proof of Theorem 2.1 105
4. The Low Primes 109
5. The Primes C and C 111
6. The Primes F, 2, F , and 2 115
7. Switching Rules 117
8. Summary and Open Problems 120
References 123
Chapter V Semigroups and Varieties 124
1. Varieties of Semigroups and Monoids 124
2. Varieties Defined by Equations 127
3. Examples of Ultimately Equational Varieties 131
4. Semidirect Products 138
5. Varieties V.W 144
6. Varieties vs. Weakly Closed Classes 147
7. Closed Varieties 150
8. Examples of Closed Varieties 153
9. Triple Products 157
10. G-Varieties 159
11. Primes 165
12. A Tabulation 167
References 171
Chapter VI. Decomposition of Sequential Functions 172
1. Syntactic Invariants of Sequential Functions 172
2. Composition 177
3. Decomposition 178
4. Parallel Composition 183
5. Examples of Decompositions 189
6. The Function Š 193
7. Varieties of Sequential Functions 196
Chapter VII. Varieties of Sets 200
1. Syntactic Semigroups 200
2. Syntactic Semigroups and Recognizable Sets 203
3. Varieties of Sets 207
4. Proof of Theorems 3.2 and 3.2s 212
5. Operations on Varieties 214
6. The Syntactic tm and ts of a Set 217
Chapter VIII. Examples of Varieties of Sets 222
1. General Comments 222
2. Finite and Cofinite Sets 223
3. Finitely Generated Varieties 225
4. The Variety D 229
5. The Variety D 231
6. Locally Testable Sets 233
7. A Theorem on Graphs 237
8. Proof of Theorem 6.5 243
9. The *-Variety j 247
10. p-Groups 253
References 260
Chapter IX. Aperiodicity 262
1. Recognizable Sets and Sequential Functions 262
2. The Concatenation Product 264
3. Schützenberger's Theorem 268
4. The Brzozowski Hierarchy 271
5. Bn,1 Are +-Varieties 274
6. The Variety B2 276
7. The Variety A1 278
References 283
Chapter X. Unitary-Prefix Decompositions 284
1. Unitary-Prefix Decompositions 284
2. A Decomposition 287
3. Two Examples 289
4. Iterated Decomposition 292
5. Periods of Monoids 294
6. Proof of Theorem 5.2 297
References 300
Chapter XI. Depth Decomposition Theorem 302
1. Basic Orderings in Semigroups 302
2. The Depth Decomposition Theorem 310
3. The Rees Matrix Semigroup 312
4. The Reduction Theorem 315
5. Proof of Proposition 2.2 319
6. Comparison with Holonomy Decomposition 323
References 326
Chapter XII. Complexity of Semigroups and Morphisms 328
1. Definition and Basic Properties 328
2. The Standard Complexity 335
3. Complexity of Morphisms 341
4. Morphism Classes Defined by S-Varieties 346
5. The Main Theorems of Complexity 352
6. Examples 354
7. Complexity of Projections 366
8. The Derived Semigroup of a Morphism 371
9. The Rhodes Expansion 376
10. Proof of the Ideal Theorem 377
11. Construction of the Rhodes Expansion 382
12. S Is Fine 387
13. Proof of Property (9.6) 390
14. Problems, Conjectures, and Further Results 394
References 397
Index 400