Universal algebra for computer scientists
Author(s)
Bibliographic Information
Universal algebra for computer scientists
（EATCS monographs on theoretical computer science, v. 25）
Springer-Verlag, c1992
- : gw
- : us
- : pbk
Available at / 30 libraries
-
: gw007.1-E11-25923005967//923005974//923005981//92300599,10092300599
-
No Libraries matched.
- Remove all filters.
Note
Bibliographical references: p. [297]-303
Includes index
"Softcover reprint of the hardcover 1st edition 1992"--T.p. verso of paperback edition
Description and Table of Contents
- Volume
-
: gw ISBN 9783540542803
Description
Written for computer scientists, this volume offers a new model-theoretic approach to universal algebra and presents a systematic development of the methods of results of universal algebra that are useful in a variety of applications in computer science. The book is concerned with the algebraic characterization of axiomatic classes of algebras by closure operators generalizing the famous Birkhoff Variety Theorem and the algebraic characterization of related theories. The book also presents a study of term rewriting systems. Beside basic notions, the Knuth-Bendix completion procedure and terminal proof methods are considered. A third main topic is that of fixpoint techniques and complete ordered algebras. Algebraic specifications of abstract data types and algebraic semantics of recursive program schemes are treated as applications.
- Volume
-
: pbk ISBN 9783642767739
Description
A new model-theoretic approach to universal algebra is offered in this book. Written for computer scientists, it presents a systematic development of the methods and results of universal algebra that are useful in a variety of applications in computer science. The notation is simple and the concepts are clearly presented. The book concerns the algebraic characterization of axiomatic classes of algebras (equational, implicational, and universal Horn classes) by closure operators generalizing the famous Birkhoff Variety Theorem, and the algebraic characterization of the related theories. The book also presents a thorough study of term rewriting systems. Besides basic notions, the Knuth-Bendix completion procedure and termination proof methods are considered. A third main topic is that of fixpoint techniques and complete ordered algebras. Algebraic specifications of abstract data types and algebraic semantics of recursive program schemes are treated as applications. The book is self-contained and suitable both as a textbook for graduate courses and as a reference for researchers.
Table of Contents
1 Preliminaries.- 1.1 Basic Notions.- 1.1.1 Sets.- 1.1.2 Algebras.- 1.2 Generation, Structural Induction, Algebraic Recursion and Deductive Systems.- 1.2.1 Generation.- 1.2.2 Structural Induction.- 1.2.3 Terms and Algebraic Recursion.- 1.2.4 Deductive Systems.- 1.3 Relations.- 1.3.1 Regular Operations.- 1.3.2 Equivalence Relations.- 1.3.3 Partial Orders.- 1.3.4 Terminating Relations.- 1.3.5 Well-Quasi-Orders.- 1.3.6 Cofinality, Multiset Ordering and Polynomial Ordering.- 1.4 Trees.- 1.4.1 Trees and Well-Founded Partially Ordered Sets.- 1.4.2 Labelled Trees.- 1.5 ?-Complete Posets and Fixpoint Theorem.- 1.5.1 ?-Complete Posets.- 1.5.2 Fixpoint Theorem.- 1.5.3 Free ?-Completion.- 2 Reductions.- 2.1 Word Problem.- 2.1.1 Confluence Method.- 2.1.2 Word Problem for Congruences.- 2.2 Reduction Systems.- 2.2.1 Abstract Reduction Systems.- 2.2.2 Term Rewriting Systems.- 2.2.3 Termination of Term Rewriting Systems.- 3 Universal Algebra.- 3.1 Basic Constructions.- 3.1.1 Subalgebras and Generation.- 3.1.2 Images and Presentation.- 3.1.3 Direct Products and Subdirect Decompositions.- 3.1.4 Reduced Products and Ultraproducts.- 3.2 Equationally Defined Classes of Algebras.- 3.2.1 Equations.- 3.2.2 Free Algebras.- 3.2.3 Varieties.- 3.2.4 Equational Theories.- 3.2.5 Term Rewriting as an Algorithmic Tool for Equational Theories.- 3.3 Implicationally Defined Classes of Algebras.- 3.3.1 Implications, Finitary Implications and Universal Horn Clauses.- 3.3.2 Sur-Reflections.- 3.3.3 Sur-Reflective Classes, Semivarieties and Quasivarieties.- 3.3.4 Implicational Theories.- 3.3.5 Universal Horn Theories.- 3.3.6 Conditional Equational Theories and Conditional Term Rewriting.- 4 Applications.- 4.1 Algebraic Specification of Abstract Data Types.- 4.1.1 Many-Sorted Algebras.- 4.1.2 Initial Semantics of Equational Specifications.- 4.1.3 Operational Semantics.- 4.2 Algebraic Semantics of Recursive Program Schemes.- 4.2.1 Ordered Algebras.- 4.2.2 Strict Ordered Algebras.- 4.2.3 ?-Complete Ordered Algebras.- 4.2.4 Recursive Program Schemes.- References.- Appendix 1: Sets and Classes.- Appendix 2: Ordered Algebras as First-Order Structures.
by "Nielsen BookData"