Universal Algebra for Computer Scientists: 25 - Brossura

Wechler, Wolfgang

Brossura

ISBN 10: 3642767737 ISBN 13: 9783642767739

Casa editrice: Springer, 2012

Riassunto

A new model-theoretic approach to universal algebra for computer scientists is offered in this book. The approach covers algebraic characterization, term rewriting systems, and fixpoint methods. The book is self-contained and suitable both as a graduate text and as a reference for researchers.

Su questo libro

Contenuti

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.

Dettagli dell'edizione

• Editore: Springer
• Data di pubblicazione: 2012
• Lingua: Inglese
• ISBN 10: 3642767737
• ISBN 13: 9783642767739
• Rilegatura: Copertina flessibile
• Numero di pagine: 356
• Contatto del produttore: Springer Nature Customer Service Center GmbH; ProductSafety@springernature.com; ; Europaplatz 3; Heidelberg; 69115; Germania