Universal Algebra and Applications in Theoretical Computer Science: 1st Edition (Hardback) book cover

Universal Algebra and Applications in Theoretical Computer Science

1st Edition

By Klaus Denecke, Shelly L. Wismath

Chapman and Hall/CRC

383 pages | 40 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781584882541
pub: 2002-01-18
$120.00
x
eBook (VitalSource) : 9781315273686
pub: 2018-10-03
from $28.98


FREE Standard Shipping!

Description

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.

Table of Contents

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

Subject Categories

BISAC Subject Codes/Headings:
COM051300
COMPUTERS / Programming / Algorithms
MAT002000
MATHEMATICS / Algebra / General
MAT028000
MATHEMATICS / Set Theory