Algebraic automata theory

M. Holcombe0521231965, 9780521231961

This is a self-contained, modern treatment of the algebraic theory of machines. Dr Holcombe examines various applications of the idea of a machine in biology, biochemistry and computer science and gives also a rigorous treatment of the way in which these machines can be decomposed and simulated by simpler ones. This treatment is based on fundamental ideas from modern algebra. Motivation for many of the newer results is provided by way of applications so this account should be accessible and valuable for those studying applied algebra or theoretical computer science at advanced undergraduate or beginning postgraduate level, as well as for those undertaking research in those areas.

---

Table of contents :
Contents……Page 4
Introduction……Page 6
1.1 Relations……Page 9
1.2 Semigroups and homomorphisms……Page 16
1.3 Products……Page 23
1.4 Groups……Page 27
1.5 Permutation groups……Page 29
1.6 Exercises……Page 30
2 Machines and semigroups……Page 33
2.1 State machines……Page 34
2.2 The semigroup of a state machine……Page 39
2.3 Homomorphisms and quotients……Page 44
2.4 Coverings……Page 51
2.5 Mealy machines……Page 55
2.6 Products of transformation semigroups……Page 60
2.7 More on products……Page 69
2.8 Examples and applications……Page 72
2.9 Exercises……Page 79
3 Decompositions……Page 84
3.1 Decompositions……Page 85
3.2 Orthogonal partitions……Page 87
3.3 General admissible partitions……Page 90
3.4 Permutation-reset machines……Page 94
3.5 Group machines……Page 99
3.6 Connected transformation semigroups……Page 102
3.7 Automorphism decompositions……Page 106
3.8 Admissible subset system decompositions……Page 110
3.9 Complexity……Page 113
3.10 Exercises……Page 121
4 The holonomy decomposition……Page 122
4.1 Relational coverings……Page 123
4.2 The skeleton and height functions……Page 126
4.3 The holonomy groups……Page 131
4.4 An ‘improved’ holonomy decomposition and examples……Page 141
4.5 The Krohn-Rhodes decomposition……Page 149
4.6 Exercises……Page 151
5.1 Automata or recognizers……Page 153
5.2 Minimal recognizers……Page 160
5.3 Recognizable sets……Page 164
5.4 The syntactic monoid……Page 167
5.5 Rational decompositions of recognizable sets……Page 170
5.6 Prefix decompositions of recognizable sets……Page 174
5.7 The pumping lemma and the size of a recognizable set……Page 180
5.8 Exercises……Page 184
6.1 Mealy machines again……Page 185
6.2 Minimizing Mealy machines……Page 190
6.3 Two sorts of covering……Page 204
6.4 Sequential functions……Page 210
6.5 Decompositions of sequential functions……Page 216
6.7 Exercises……Page 220
Appendix……Page 223
References……Page 228
Index of notation……Page 230
Index……Page 233