Universal Algebra and Applications in Theoretical Computer Science

This graduate-level textbook provides an introduction to the basic ideas and concepts of universal algebra and surveys of newer developments. Universal Algebra and Applications in Theoretical Computer Science is written in a style accessible to beginners, with every new concept clearly explained and numerous examples provided. The main ideas of concept lattices as an important tool for conceptual analysis of data are developed, and several examples are given. The algebraic theory of tree automata and its interconnections to universal-algebraic concepts are described. The final part of the book is devoted to key applications of universal algebra in theoretical computer science.

Contents

Introduction

1 Basic Concepts 1
2 Galois Connections and Closures 31
3 Homomorphisms and Isomorphisms 47
4 Direct and Subdirect Products 63
5 Terms, Trees, and Polynomials 75
6 Identities and Varieties 91
7 Term Rewriting Systems 115
8 Algebraic Machines 147
9 Mal'cev-Type Conditions 193
10 Clones and Completeness 215
11 Tame Congruence Theory 251
12 Term Condition and Commutator 289
13 Complete Sublattices 301
14 G-Clones and M-Solid Varieties 325
15 Hypersubstitutions and Machines 347

Bibliography 363
Index 373