Algebraic and coalgebraic methods in the mathematics of program construction

Program construction is about turning specifications of computer software into implementations. Recent research aimed at improving the process of program construction exploits insights from abstract algebraic tools such as lattice theory, fixpoint calculus, universal algebra, category theory, and allegory theory.
This textbook-like tutorial presents, besides an introduction, eight coherently written chapters by leading authorities on ordered sets and complete lattices, algebras and coalgebras, Galois connections and fixed point calculus, calculating functional programs, algebra of program termination, exercises in coalgebraic specification, algebraic methods for optimization problems, and temporal algebra.

在线阅读本书

Program construction is about turning specifications of computer software into implementations. Recent research aimed at improving the process of program construction exploits insights from abstract algebraic tools such as lattice theory, fixpoint calculus, universal algebra, category theory, and allegory theory.
This textbook-like tutorial presents, besides an introduction, eight coherently written chapters by leading authorities on ordered sets and complete lattices, algebras and coalgebras, Galois connections and fixed point calculus, calculating functional programs, algebra of program termination, exercises in coalgebraic specification, algebraic methods for optimization problems, and temporal algebra.

Charter 1 Introduction
　1. Preliminaries
　　1.1. Assumed Knowledge
　　1.2. Volume Overview
　2. A Mathematical History Tour
　　2.1. Fixed Points
　　2.2. Induction and Coinduction
　　2.3. Types and Categories
　　2.4. Algebras and Coalgebras
　3. Mathematics in ACMMPC
3.1. Chapter 2: Ordered Sets and Complete Lattices
3.2. Chapter 3: Introducing Algebras and Coalgebras
3.3. Chapter 4: Galois Connections and Fixed Point Calculus
3.4. Chapter 5: Calculating Functional Programs
3.5. Chapter 6: Algebra of Program Termination
3.6. Chapter 7: Exercises in Coalgebraic Specification
3.7. Chapter 8: Algebraic Methods for Optimization Problems
3.8. Chapter 9: Temporal Algebra
Chapter 2 Ordered Sets and Complete Lattices
　1. Introduction
　2. From Binary Relations to Diagrams
2.1. A Fundamental Example: Powersets
2.2. Input-Output Relations Pictorially
2.3. Exercise
2.4. Binary Relations and Their Polars
2.5. Exercise
2.6. Summing Up So Far
　3. Order, Order, Order
3.1. Partial Order
3.2. Information Orderings
3.3. Diagrams
3.4. Duality: Buy One, Get One Free
3.5. Bottom and Top
3.6. Lifting
3.7. New Posets from Old: Sums and Products
3.8. Maps between Posets
3.9. Pointwise Ordering of Maps
3.10. Up-Sets: An Inbred Example
3.11. Monotone Maps and Up-Sets
3.12. Exercise (More on Monotone Maps and Up-Sets)
3.13. Down Is Nice Too
3.14. Exercise (Turning Things Upside Down)
3.15. The Down-Set Operator, and the Up-Set Operator,
3.16. Exercise (A Context Explored)
3.17. Maximal and Minimal Elements
3.18. Stocktaking
4. Lattices in General and Complete Lattices in Particular
4.1. Lattices
4.2. Examples of Lattices
4.3. Distributive Lattices
4.4. Boolean Algebras
4.5. Lattices in Logic
4.6. Upper Bounds and Sups, Lower Bounds and Infs
4.7. Much Ado about Nothing, and about Everything
4.8. Complete Lattices
4.9. Completeness on the Cheap
4.10. A Special Class of Complete Lattices
4.11. Suprema, Infima, and Monotone Maps
5. Complete Lattices, Concretely: Closure Systems and Closure Operators
5.1. A Useful Technical Remark
5.2. Complete Lattices of Sets
5.3. Closure Systems
5.4. Closure Systems
5.5. Examples
5.6. From a Complete Lattice to a Closure System
5.7. Defining Closure Operators
5.8. New Complete Lattices from Old:From a Closure Operator to a Complete Lattice
5.9. Closure Operators more Concretely
6. Galois Connections: Basics
6.1. Introduction
6.2. Lattice Representation via Galois Connections
6.3. Galois Connections from Binary Relations: Method I
6.4. Galois Connections and Algebras--A Fleeting Glimpse
6.5. Galois Connections by Sectioning
6.6. Galois Connections from Binary Relations: Method II
6.7. Galois Connections: Basic Properties
6.8. and Have Isomorphic Images
6.9. Equivalent Definitions for Galois Connections
6.10. The Good (and Less Good) Behaviour of Galois Maps
6.11. Uniqueness of Adjoints:from and from
6.12. Exercise (Surjective and Injective Galois Maps)
6.13. A Look Ahead
……
Chapter 3 Algebras and Coalebras
Chapter 4 Galois Connections and Fixed Point Calculus
Chapter 5 Calculating Functional Programs
Chapter 6 Algebra of Program Termination
Chapter 7 Exercises in Coalgebraic Specification
Chapter 8 Algebraic Methods for Optimization Problems
Chapter 9 Temporal Algebra
Author Index