Universal algebra and applications in theoretical computer science

Title:

Personal Author:

Denecke, Klaus

Publication Information:

Boca Raton, Fla. : Chapman & Hall/CRC, 2002

ISBN:

9781584882541

Subject Term:

Algebra, Universal

Computer science -- Mathematics

Added Author:

Wismath, Shelly L.

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010053039	QA251 D46 2002	Open Access Book	Book	Searching... Unknown

Over the past 20 years, the emergence of clone theory, hyperequational theory, commutator theory and tame congruence theory has led to a growth of universal algebra both in richness and in applications, especially in computer science. Yet most of the classic books on the subject are long out of print and, to date, no other book has integrated these theories with the long-established work that supports them.

Universal Algebra and Applications in Theoretical Computer Science introduces the basic concepts of universal algebra and surveys some of the newer developments in the field. The first half of the book provides a solid grounding in the core material. A leisurely pace, careful exposition, numerous examples, and exercises combine to form an introduction to the subject ideal for beginning graduate students or researchers from other areas. The second half of the book focuses on applications in theoretical computer science and advanced topics, including Mal'cev conditions, tame congruence theory, clones, and commutators.

The impact of the advances in universal algebra on computer science is just beginning to be realized, and the field will undoubtedly continue to grow and mature. Universal Algebra and Applications in Theoretical Computer Science forms an outstanding text and offers a unique opportunity to build the foundation needed for further developments in its theory and in its computer science applications.

Author Notes

Klaus Denecke is a Professor at the Institut fur Mathematik, Universitat Potsdam, Germany.
Shelly L. Wismath is a Professor in the Department of Mathematics and Computer Science, University of Lethbridge, Alberta, Canada

Introduction	p. v
1 Basic Concepts	p. 1
1.1 Algebras	p. 1
1.2 Examples	p. 4
1.3 Subalgebras	p. 13
1.4 Congruence Relations and Quotients	p. 21
1.5 Exercises	p. 27
2 Galois Connections and Closures	p. 31
2.1 Closure Operators	p. 32
2.2 Galois Connections	p. 37
2.3 Concept Analysis	p. 42
2.4 Exercises	p. 44
3 Homomorphisms and Isomorphisms	p. 47
3.1 The Homomorphism Theorem	p. 49
3.2 The Isomorphism Theorems	p. 58
3.3 Exercises	p. 61
4 Direct and Subdirect Products	p. 63
4.1 Direct Products	p. 63
4.2 Subdirect Products	p. 68
4.3 Exercises	p. 72
5 Terms, Trees, and Polynomials	p. 75
5.1 Terms and Trees	p. 76
5.2 Term Operations	p. 82
5.3 Polynomials and Polynomial Operations	p. 85
5.4 Exercises	p. 88
6 Identities and Varieties	p. 91
6.1 The Galois Connection (Id, Mod)	p. 91
6.2 Fully Invariant Congruence Relations	p. 95
6.3 The Algebraic Consequence Relation	p. 97
6.4 Relatively Free Algebras	p. 98
6.5 Varieties	p. 101
6.6 The Lattice of All Varieties	p. 109
6.7 Finite Axiomatizability	p. 110
6.8 Exercises	p. 113
7 Term Rewriting Systems	p. 115
7.1 Confluence	p. 116
7.2 Reduction Systems	p. 123
7.3 Term Rewriting	p. 129
7.4 Termination of Term Rewriting Systems	p. 141
7.5 Exercises	p. 145
8 Algebraic Machines	p. 147
8.1 Regular Languages	p. 148
8.2 Finite Automata	p. 150
8.3 Algebraic Operations on Finite Automata	p. 159
8.4 Tree Recognizers	p. 165
8.5 Regular Tree Grammars	p. 169
8.6 Operations on Tree Languages	p. 174
8.7 Minimal Tree Recognizers	p. 176
8.8 Tree Transducers	p. 182
8.9 Turing Machines	p. 185
8.10 Undecidable Problems	p. 187
8.11 Exercises	p. 191
9 Mal'cev-Type Conditions	p. 193
9.1 Congruence Permutability	p. 193
9.2 Congruence Distributivity	p. 195
9.3 Arithmetical Varieties	p. 201
9.4 n-Modularity and n-Permutability	p. 203
9.5 Congruence Regular Varieties	p. 205
9.6 Two-Element Algebras	p. 206
9.7 Exercises	p. 213
10 Clones and Completeness	p. 215
10.1 Clones as Algebraic Structures	p. 215
10.2 Operations and Relations	p. 217
10.3 The Lattice of All Boolean Clones	p. 219
10.4 The Functional Completeness Problem	p. 228
10.5 Primal Algebras	p. 231
10.6 Different Generalizations of Primality	p. 240
10.7 Preprimal Algebras	p. 245
10.8 Exercises	p. 249
11 Tame Congruence Theory	p. 251
11.1 Minimal Algebras	p. 251
11.2 Tame Congruence Relations	p. 262
11.3 Permutation Algebras	p. 269
11.4 The Types of Minimal Algebras	p. 276
11.5 Mal'cev Conditions and Omitting Types	p. 281
11.6 Residually Small Varieties	p. 286
11.7 Exercises	p. 287
12 Term Condition and Commutator	p. 289
12.1 The Term Condition	p. 289
12.2 The Commutator	p. 293
12.3 Exercises	p. 299
13 Complete Sublattices	p. 301
13.1 Conjugate Pairs of Closure Operators	p. 301
13.2 Galois Closed Subrelations	p. 308
13.3 Closure Operators on Complete Lattices	p. 316
13.4 Exercises	p. 323
14 G-Clones and M-Solid Varieties	p. 325
14.1 G-Clones	p. 325
14.2 H-clones	p. 331
14.3 M-Solid Varieties	p. 334
14.4 Intervals in the Lattice L([tau])	p. 342
14.5 Exercises	p. 345
15 Hypersubstitutions and Machines	p. 347
15.1 The Hyperunification Problem	p. 347
15.2 Hyper Tree Recognizers	p. 349
15.3 Tree Transformations	p. 357
15.4 Exercises	p. 361
Bibliography	p. 363
Index	p. 373

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents