Abstract
Fixed point calculus is about the solution of recursive equations defined by a monotonic endofunction on a partially ordered set. This tutorial 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 summarises 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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. C. Backhouse and B. A. Carré. Regular algebra applied to path-finding problems. Journal of the Institute of Mathematics and its Applications, 15:161–186, 1975.
Garrett Birkhoff. Lattice Theory, volume 25 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, Rhode Island, 3rd edition, 1967.
B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press, first edition, 1990.
E. W. Dijkstra and C. S. Scholten. Predicate Calculus and Program Semantics. Springer-Verlag, Berlin, 1990.
W. H. J. Feijen and Lex Bijlsma. Exercises in formula manipulation. In E. W. Dijkstra, editor, Formal Development of Programs and Proofs, pages 139–158. Addison-Wesley Publ. Co., 1990.
Maureen H. Fenrick. Introduction to the Galois Correspondence. Birkhaüser Boston, 1991.
G. Gentzen. Investigations into logical deduction. In M. E. Szabo, editor, The Collected Papers of Gerhard Gentzen, pages 68–213. North-Holland, Amsterdam, 1969.
G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott. A Compendium of Continuous Lattices. Springer-Verlag, 1980.
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Publishing Company, 1989.
Bernhard Ganter and Rudolf Wille. Formal Concept Analysis. Mathematical Foundations. Springer-Verlag Berlin Heidelberg, 1999. Translated from the German by Cornelia Franzke. Title of the original German edition: Formale Begriffsanalyse — Mathematische Grundlagen.
C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the ACM, 12(10):576–580, 1969.
J. Hartmanis and R. E. Stearns. Pair algebras and their application to automata theory. Information and Control, 7(4):485–507, 1964.
J. Hartmanis and R. E. Stearns. Algebraic Structure Theory of Sequential Machines. Prentice-Hall, 1966.
S. C. Kleene. Representation of events in nerve nets and finite automata. In Shannon and McCarthy, editors, Automata Studies, pages 3–41. Princeton Univ. Press, 1956.
Dexter Kozen. A completeness theorem for Kleene algebras and the algebra of regular events. Information and Computation, 110(2):366–390, 1994.
J. Lambek. The influence of Heraclitus on modern mathematics. In J. Agassi and R. S. Cohen, editors, Scientific Philosophy Today, pages 111–121. D. Reidel Publishing Co., 1981.
J. Lambek. Some Galois connections in elementary number theory. J. of Number Theory, 47(3):371–377, June 1994.
P. (Ed.) Naur. Revised report on the algorithmic language ALGOL 60. Comm. ACM, 6:1–20, Also in The Computer Journal, 5: 349-67 (1963); Numerische Mathematik, 4: 420-52 (1963) 1963.
Oystein Ore. Galois connexions. Transactions of the American Mathematical Society, 55:493–513, 1944.
J. Schmidt. Beitrage für Filtertheorie. II. Math. Nachr., 10:197–232, 1953.
Ian Stewart. Galois Theory. Chapman and Hall, 2nd edition, 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Backhouse, R. (2002). Galois Connections and Fixed Point Calculus. In: Backhouse, R., Crole, R., Gibbons, J. (eds) Algebraic and Coalgebraic Methods in the Mathematics of Program Construction. Lecture Notes in Computer Science, vol 2297. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47797-7_4
Download citation
DOI: https://doi.org/10.1007/3-540-47797-7_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43613-3
Online ISBN: 978-3-540-47797-6
eBook Packages: Springer Book Archive