Universal algebra and applications in theoretical computer science. (English) Zbl 0993.08001

Boca Raton, FL: Chapman & Hall/CRC. xii, 383 p. (2002).
This new universal algebra text comprises an introduction, a bibliography (121 items), an index, and the following fifteen chapters: 1. Basic concepts; 2. Galois connections and closures; 3. Homomorphisms and isomorphisms; 4. Direct and subdirect products; 5. Terms, trees, and polynomials; 6. Identities and varieties; 7. Term rewriting systems; 8. Algebraic machines; 9. Mal’cev-type conditions; 10. Clones and completeness; 11. Tame congruence theory; 12. Term condition and commutator; 13. Complete sublattices; 14. \(G\)-clones and \(M\)-solid varieties; 15. Hypersubstitutions and machines.
Chapters 1-6, perhaps together with Chapter 9, form a fairly usual exposition of basic universal algebra. Special attention is paid to all the Galois connections and closure systems arising in various contexts, and these actually form a central theme of the book. Chapters 7 and 8 provide brief introductions to term rewriting and the algebraic theory of automata, including tree automata, respectively. The remaining chapters treat various more advanced or specialized topics, and here much quite recent material is presented. Thus Chapter 10 discusses clones, functional completeness, primality, and related matters. In particular, the lattice of Boolean clones is described. Chapter 11 introduces the Hobby-McKenzie structural theory of finite algebras. In Chapters 13 and 14 some special Galois connections, clones of operations, clones of relations, and varieties are studied. Chapter 14 also introduces hypersubstitutions which replace each function symbol by a term. This notion is used in Chapter 15 to define some new tree automata.
The book is suitable as an introduction to universal algebra but also as further reading in certain special topics. Apart from some minor flaws, it is well written in a good textbook style with detailed explanations and many exercises. The proofs of some central results are omitted, but on the other hand, several additional topics are mentioned along with useful references. In spite of the title, this is not a theoretical computer science book in the same way as W. Wechler’s Universal algebra for computer scientists [Berlin: Springer (1992; Zbl 0748.68002)], where applications are explicitly considered and the theory is developed with these in mind. Nevertheless, the book can be recommended also to computer science students, and the topics related to computer science could well interest mathematicians, too.


08-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to general algebraic systems
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
06A15 Galois correspondences, closure operators (in relation to ordered sets)
08A70 Applications of universal algebra in computer science
08A40 Operations and polynomials in algebraic structures, primal algebras
68Q42 Grammars and rewriting systems
68Q70 Algebraic theory of languages and automata
08Axx Algebraic structures
08Bxx Varieties


Zbl 0748.68002