1st Edition
Universal Algebra and Applications in Theoretical Computer Science
396 Pages
40 B/W Illustrations
by
Chapman & Hall
383 Pages
40 B/W Illustrations
by
Chapman & Hall
Also available as eBook on:
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... Read more
BASIC CONCEPTS
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
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.
