The q-theory of Finite Semigroups

0387097805......Page 1
Contents......Page 12
Preface......Page 6
List of Tables......Page 18
List of Figures......Page 19
Introduction......Page 20
Part I: The q-operator and Pseudovarieties of Relational Morphisms......Page 32
1. Foundations for Finite Semigroup Theory......Page 33
1.1 Basic Notation......Page 34
1.2 Foundations......Page 40
1.3 Relational Morphisms......Page 54
Notes......Page 65
2. The q-operator......Page 66
2.1 Axioms for Sets of Relational Morphisms......Page 67
2.2 Continuous Operators......Page 74
2.3 Definition of 
the q-operator......Page 78
2.4 Key Examples......Page 97
2.5 The Derived Semigroupoid Theorem......Page 110
2.6 The Kernel Semigroupoid Theorem......Page 121
2.7 The Slice Theorem and Joins......Page 131
2.8 Composition......Page 132
2.9 Reverse Global Mal'cev Condition......Page 140
Notes......Page 143
3. The Equational Theory......Page 144
3.1 Profinite Semigroups......Page 145
3.2 Reiterman's Theorem......Page 159
3.3 On pro-V Relational Morphisms......Page 164
3.4 Generators and Free pro-V Relational Morphisms......Page 170
3.5 Relational Pseudoidentities......Page 174
3.6 Composition and Inevitable Substitutions......Page 185
3.7 Basis Theorems......Page 205
3.8 Flows and the Basis Theorem for Semidirect Products......Page 216
3.9 The Equational Theory for Continuously Closed Classes......Page 223
Notes......Page 229
Part II: Complexity in Finite Semigroup Theory......Page 230
4. The Complexity of Finite Semigroups......Page 231
4.1 The Prime Decomposition Theorem......Page 232
4.2 Brown's Theorem......Page 250
4.3 The Definition of Complexity
......Page 253
4.4 Aperiodics and Schützenberger's Theorem......Page 258
4.5 Stiffler's Theorem
......Page 263
4.6 The Semilocal Theory......Page 265
4.7 The Classification of Subdirectly Indecomposable Semigroups......Page 283
4.8 The Exclusion Classes of U[sub(2)] and 2......Page 292
4.9 The Fundamental Lemma of Complexity......Page 297
4.10 The Decidability of Complexity for DS and Related Pseudovarieties......Page 304
4.11 The Karnofsky-Rhodes Decompositions and G * A
......Page 308
4.12 Lower Bounds for Complexity......Page 311
4.13 The Topology of Graphs and Graham's Theorem......Page 324
4.14 The Presentation Lemma......Page 339
4.15 Tilson's Two J-class Theorem......Page 354
4.16 Complexity Pseudovarieties Are Not Local......Page 359
4.17 The Type II Theorem......Page 365
4.18 The Ribes and Zalesskii Theorem......Page 379
4.19 Henckell's Theorem......Page 384
Notes......Page 399
5.1 Complexity of Operators......Page 403
5.2 Maximal Proper Surmorphisms......Page 409
5.3 The Two-Sided Decomposition Theory......Page 412
5.4 The Ideal Theorem......Page 423
5.5 Translational Hulls and Ideal Extensions......Page 425
5.6 Two-Sided Complexity of 2J-Semigroups......Page 434
5.7 Lower Bounds......Page 437
Notes......Page 440
Part III: The Algebraic Lattice of Semigroup Pseudovarieties......Page 441
6.1 Complete and Algebraic Lattices......Page 442
6.2 Continuous Lattices......Page 448
6.3 Closure and Kernel Operators, Ideals and Morphisms......Page 451
6.4 Topologies on Algebraic Lattices......Page 469
Notes......Page 474
7. The Abstract Spectral Theory of PV......Page 476
7.1 Birkhoff 's Subdirect Representation Theorem......Page 477
7.2 Locally Dually Algebraic Lattices......Page 486
7.3 A Brief Survey of Join Irreducibility......Page 495
7.4 Kovács-Newman Semigroups......Page 512
7.5 Irreducibility for the Semidirect Product......Page 524
7.6 Irreducibility for Pseudovarieties of Relational Morphisms......Page 527
7.7 The Abstract Spectral Theory of Cnt(PV)......Page 528
Notes......Page 533
Part IV: Quantales, Idempotent Semirings, Matrix Algebras and the Triangular Product......Page 535
8. Quantales......Page 536
8.1 Ordered Semigroups and Quantales......Page 537
8.2 Green's Preorders vs. the Quantale Ordering......Page 540
8.3 Homomorphism and Substructure Theorems for Quantales......Page 543
8.4 The Bialgebra of Regular Languages......Page 548
8.5 Matrix Quantales and an Embedding Theorem......Page 553
Notes......Page 558
9.1 Semirings......Page 559
9.2 The Triangular Product......Page 570
9.3 The Triangular Decomposition Theorem......Page 578
9.4 The Prime Decomposition Theorem for Idempotent Semirings......Page 585
9.5 Complexity of Idempotent Semirings......Page 599
Notes......Page 606
A.1 Ideal Structure and Green's Relations......Page 607
A.2 Stable Semigroups......Page 610
A.3 Green's Lemma and Maximal Subgroups......Page 613
A.3.1 The Schützenberger group......Page 616
A.4 Rees's Theorem......Page 618
B. Tables on Preservation of Sups and Infs......Page 625
List of Problems......Page 627
References......Page 634
Table of Pseudovarieties......Page 654
Table of Operators and Products......Page 656
Table of Implicit Operations......Page 657
Index of Notation......Page 658
E......Page 662
K......Page 663
P......Page 664
S......Page 665
Z......Page 666
A......Page 667
C......Page 668
G......Page 669
L......Page 670
P......Page 671
R......Page 672
T......Page 673
Z......Page 674