Universal Algebra and Applications in Theoretical Computer Science

by Denecke; Klaus

• ISBN13: 9781584882541
• ISBN10: 1584882549
• Edition: 1st
• Format: Hardcover
• Copyright: 2002-01-18
• Publisher: Chapman & Hall/

Summary

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 Biography

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

Table of Contents

Introduction	v
Basic Concepts	1	(30)
Algebras	1	(3)
Examples	4	(9)
Subalgebras	13	(8)
Congruence Relations and Quotients	21	(6)
Exercises	27	(4)
Galois Connections and Closures	31	(16)
Closure Operators	32	(5)
Galois Connections	37	(5)
Concept Analysis	42	(2)
Exercises	44	(3)
Homomorphisms and Isomorphisms	47	(16)
The Homomorphism Theorem	49	(9)
The Isomorphism Theorems	58	(3)
Exercises	61	(2)
Direct and Subdirect Products	63	(12)
Direct Products	63	(5)
Subdirect Products	68	(4)
Exercises	72	(3)
Terms, Trees, and Polynomials	75	(16)
Terms and Trees	76	(6)
Term Operations	82	(3)
Polynomials and Polynomial Operations	85	(3)
Exercises	88	(3)
Identities and Varieties	91	(24)
The Galois Connection (Id, Mod)	91	(4)
Fully Invariant Congruence Relations	95	(2)
The Algebraic Consequence Relation	97	(1)
Relatively Free Algebras	98	(3)
Varieties	101	(8)
The Lattice of All Varieties	109	(1)
Finite Axiomatizability	110	(3)
Exercises	113	(2)
Term Rewriting Systems	115	(32)
Confluence	116	(7)
Reduction Systems	123	(6)
Term Rewriting	129	(12)
Termination of Term Rewriting Systems	141	(4)
Exercises	145	(2)
Algebraic Machines	147	(46)
Regular Languages	148	(2)
Finite Automata	150	(9)
Algebraic Operations on Finite Automata	159	(6)
Tree Recognizers	165	(4)
Regular Tree Grammars	169	(5)
Operations on Tree Languages	174	(2)
Minimal Tree Recognizers	176	(6)
Tree Transducers	182	(3)
Turing Machines	185	(2)
Undecidable Problems	187	(4)
Exercises	191	(2)
Mal'cev-Type Conditions	193	(22)
Congruence Permutability	193	(2)
Congruence Distributivity	195	(6)
Arithmetical Varieties	201	(2)
n-Modularity and n-Permutability	203	(2)
Congruence Regular Varieties	205	(1)
Two-Element Algebras	206	(7)
Exercises	213	(2)
Clones and Completeness	215	(36)
Clones as Algebraic Structures	215	(2)
Operations and Relations	217	(2)
The Lattice of All Boolean Clones	219	(9)
The Functional Completeness Problem	228	(3)
Primal Algebras	231	(9)
Different Generalizations of Primality	240	(5)
Preprimal Algebras	245	(4)
Exercises	249	(2)
Tame Congruence Theory	251	(38)
Minimal Algebras	251	(11)
Tame Congruence Relations	262	(7)
Permutation Algebras	269	(7)
The Types of Minimal Algebras	276	(5)
Mal'cev Conditions and Omitting Types	281	(5)
Residually Small Varieties	286	(1)
Exercises	287	(2)
Term Condition and Commutator	289	(12)
The Term Condition	289	(4)
The Commutator	293	(6)
Exercises	299	(2)
Complete Sublattices	301	(24)
Conjugate Pairs of Closure Operators	301	(7)
Galois Closed Subrelations	308	(8)
Closure Operators on Complete Lattice	316	(7)
Exercises	323	(2)
G-Clones and M-Solid Varieties	325	(22)
G-Clones	325	(6)
H-Clones	331	(3)
M-Solid Varieties	334	(8)
Intervals in the Lattice L(τ)	342	(3)
Exercises	345	(2)
Hypersubstitutions and Machines	347	(16)
The Hyperunification Problem	347	(2)
Hyper Tree Recognizers	349	(8)
Tree Transformations	357	(4)
Exercises	361	(2)
Bibliography	363	(10)
Index	373