Universal Algebra and Applications in Theoretical Computer Science

ISBN-13: 9781584882541 / Angielski / Twarda / 2002 / 383 str.

Klaus Denecke; Denecke Denecke; Shelly L. Wismath

Opis

Introduces the basic concepts of universal algebra and surveys some of the developments in the field. This book focuses on applications in theoretical computer science and various topics, including Mal'cev conditions, tame congruence theory, clones, and commutators.

Spis treści

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

O autorze

Denecke, Klaus; Wismath, Shelly L.