Galois Connections and Fixed Point Calculus

Introduces the fundamental algebraic structures in the mathematics of program construction with a focus on the algebraic properties of recursion and how these are applied to the generic solution of programming problems.

**Tag(s):**
Algebra

**Publication date**: 01 Oct 2001

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
n/a

**Views**: 16,012

**Type**: N/A

**Publisher**:
n/a

**License**:
n/a

**Post time**: 12 Oct 2006 09:33:12

Galois Connections and Fixed Point Calculus

Introduces the fundamental algebraic structures in the mathematics of program construction with a focus on the algebraic properties of recursion and how these are applied to the generic solution of programming problems.

Document Excerpts:

Recursion is a very powerful problem-solving technique that is used widely in computing science. It is used, for example, in the definition of programming languages, as a fundamental programming structure in functional and logic programming, and in the definition of data structures. A complete understanding of recursion can only be achieved by studying its algebraic properties.

This tutorial has been used as the literature for the course of Programming Algebra at the School of Computer Science and Information Technology, University of Nottingham. This course introduces the fundamental algebraic structures in the mathematics of program construction with a focus on the algebraic properties of recursion and how these are applied to the generic solution of programming problems.

This tutorial covers fixed point calculus, which is about the solution of recursive equations defined by a monotonic endofunction on a partially ordered set. It presents the basic theory of fixed point calculus together with a number of applications of direct relevance to the construction of computer programs. The tutorial also presents the theory and application of Galois connections between partially ordered sets. In particular, the intimate relation between Galois connections and fixed point equations is amply demonstrated.

Intended Audience:

The course assumes that the student has completed both courses on functional programming and the mathematics of program construction.

Recursion is a very powerful problem-solving technique that is used widely in computing science. It is used, for example, in the definition of programming languages, as a fundamental programming structure in functional and logic programming, and in the definition of data structures. A complete understanding of recursion can only be achieved by studying its algebraic properties.

This tutorial has been used as the literature for the course of Programming Algebra at the School of Computer Science and Information Technology, University of Nottingham. This course introduces the fundamental algebraic structures in the mathematics of program construction with a focus on the algebraic properties of recursion and how these are applied to the generic solution of programming problems.

This tutorial covers fixed point calculus, which is about the solution of recursive equations defined by a monotonic endofunction on a partially ordered set. It presents the basic theory of fixed point calculus together with a number of applications of direct relevance to the construction of computer programs. The tutorial also presents the theory and application of Galois connections between partially ordered sets. In particular, the intimate relation between Galois connections and fixed point equations is amply demonstrated.

Intended Audience:

The course assumes that the student has completed both courses on functional programming and the mathematics of program construction.

Tweet

About The Author(s)

Roland Backhouse joined the School of Computer Science in September 1999. He retired in November 2013 and is now an emeritus professor. (So he is not as young as the photograph might suggest!) He continues to do some research and to publish occasionally. His research interests include mathematics of program construction, calculus of relations, category theory, mathematical method, generic programming, and on-line document preparation systems oriented to the needs of authors of mathematical documents.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors