1st Edition
Universal Algebra and Applications in Theoretical Computer Science
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.
Algebras
Examples
Subalgebras
Congruence Relations and Quotients
Exercises
GALOIS CONNECTIONS AND CLOSURES
Closure Operators
Galois Connections
Concept Analysis
Exercises
HOMOMORPHISMS AND ISOMORPHISMS
The Homomorphism Theorem
The Isomorphism Theorems
Exercises
DIRECT AND SUBDIRECT PRODUCTS
Direct Products
Subdirect Products
Exercises
TERMS, TREES, AND POLYNOMIALS
Terms and Trees
Term Operations
Polynomials and Polynomial Operations
Exercises
IDENTITIES AND VARIETIES
The Galois-Connection (Id, Mod)
Fully Invariant Congruence Relations
The Algebraic Consequence Relation
Relatively Free Algebras
Varieties
The Lattice of All Varieties
Finite Axiomatizability
Exercises
TERM REWRITING SYSTEMS
Confluence
Reduction Systems
Term Rewriting
Termination of Term Rewriting Systems
Exercises
ALGEBRAIC MACHINES
Regular Languages
Finite Automata
Algebraic Operations on Finite Automata
Tree-Recognizers
Regular Tree Grammars
Operations on Tree Languages
Minimal Tree-Recognizers
Tree Transducers
Turing Machines
Undecidable Problems
Exercises
MAL'CEV-TYPE CONDITIONS
Congruence Permutability
Congruence Distributivity
Arithmetical Varieties
n-Modularity and n-Permutability
Congruence Regular Varieties
Two-Element Algebras
Exercises
CLONES AND COMPLETENESS
Clones as Algebraic Structures
Operations and Relations
The Lattice of all Boolean Clones
The Functional Completeness Problem
Primal Algebras
Different Generalizations of Primality
Preprimal Algebras
TAME CONGRUENCE THEORY
Minimal Algebras
Tame Congruence Relations
Permutation Algebras
The Types of Minimal Algebras
Mal'cev Conditions and Omitting Types
Residually Small Varieties
TERM CONDITION AND COMMUTATOR
The Term Condition
The Commutator
COMPLETE SUBLATTICES
Conjugate Pairs of Closure Operators
Galois-Closed Subrelations
Closure Operators on Complete Lattices
G-CLONES AND M-SOLID VARIETIES
G-Clones
H-Clones
M-Solid Varieties
Intervals in the Lattice L(t)
HYPERSUBSTITUTIONS AND MACHINES
The Hyperunification Problem
Hyper-Tree-Recognizers
Tree Transformations
BIBLIOGRAPHY
INDEX
Biography
Denecke, Klaus; Wismath, Shelly L.
