Algebraic and Structural Automata Theory (eBook)

Front Cover 1
Algebraic and Structural Automata Theory 4
Copyright Page 5
Contents 18
Introduction 6
Preface 14
Chapter 0 . Basic mathematical concepts 24
Chapter 1. Automata and languages 30
1.1. Languages and grammars generating them 30
1.2. Tape automata 38
Exercises 56
Bibliographic note 57
Chapter 2. Finite automata 58
2.1. Definitions of automata 58
2.2. Automata without outputs 69
2.3. Acceptors of regular languages 87
Exercises 104
Bibliographic note 105
Chapter 3. Minimization of automata 106
3.1. Equivalence of automata 106
3.2. Minimization of deterministic complete automata 108
3.3. Minimization of deterministic incomplete automata 125
Exercises 137
Bibliographic note 140
Chapter 4. Input subautomata 142
4.1. Introduction 142
4.2. Equivalence of states and equivalence of automata 148
4.3. Connectedness 151
4.4. Other properties 169
Exercises 173
Bibliographic note 176
Chapter 5. Automata homomorphisms 178
5.1. State homomorphisms of automata 178
5.2. Generalized homomorphisms of automata 196
5.3. Comparison of automata properties with respect to functions preserving operations 212
5.4. Complexity of computing generalized automata homomorphisms Exercises 214
Exercises 217
Bibliographic note 218
Chapter 6. Realizations of automata. State assignment 220
6.1. The concepts of realizations 220
6.2. Structure of realization 226
6.3. Partition pairs and information flow in automata 230
6.4. Binary state assignment 236
6.5. m-ary assignment 246
6.6. Minimal control information for a component 249
Exercises 250
Bibliographic note 251
Chapter 7. Realizations of automata . Structures of nets 252
7.1. Loop-free realization 253
7.2. Serial and parallel decompositions of automata 259
7.3. Realization with a shift register 263
7.4. Asynchronous cooperation of components 269
7.5. Problem of a predecessor in cellular structure 280
7.6. Realizations with the minimal amount of feedback 288
Exercises 290
Bibliographic note 291
Chapter 8. Time-varying automata 292
8.1. Basic concepts 292
8.2. Equivalence of time-varying automata 295
8.3. Languages accepted by time-varying automata 299
8.4. Periodic automata 304
8.5. Automorphisms of periodlc automata 310
8.6. Periodic representations of automata 314
8.7. Extended periodic representations of automata 316
Exercises 321
Bibliographic note 321
Chapter 9. Transforms and extensions of automata 324
9.1. Transforms of automata 325
9.2. Extensions of automata 335
Bibliographic note 340
Chapter 10. Periodic sums of automata 342
10.1. Introduction 342
10.2. Connections of the periodic sum with the periodic extension and with input subautomata 344
10.3. Structural properties 364
10.4. Periodic sums with input mappings 364
Exercises 368
Bibliographic note 369
Chapter 11. Linear automata 370
11.1. Introducing remarks 370
11.2. Linear realizations of finite automata 375
11.3. Linear shift registers 381
Exercises 389
Bibliographic note 392
Bibliography 394
Index 410