Nothing Special   »   [go: up one dir, main page]

Skip to main content

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2297))

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook
USD 15.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 15.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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.

    Article  MATH  MathSciNet  Google Scholar 

  2. Garrett Birkhoff. Lattice Theory, volume 25 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, Rhode Island, 3rd edition, 1967.

    Google Scholar 

  3. B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press, first edition, 1990.

    Google Scholar 

  4. E. W. Dijkstra and C. S. Scholten. Predicate Calculus and Program Semantics. Springer-Verlag, Berlin, 1990.

    MATH  Google Scholar 

  5. 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.

    Google Scholar 

  6. Maureen H. Fenrick. Introduction to the Galois Correspondence. Birkhaüser Boston, 1991.

    Google Scholar 

  7. G. Gentzen. Investigations into logical deduction. In M. E. Szabo, editor, The Collected Papers of Gerhard Gentzen, pages 68–213. North-Holland, Amsterdam, 1969.

    Google Scholar 

  8. G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott. A Compendium of Continuous Lattices. Springer-Verlag, 1980.

    Google Scholar 

  9. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Publishing Company, 1989.

    Google Scholar 

  10. 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.

    MATH  Google Scholar 

  11. C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the ACM, 12(10):576–580, 1969.

    Article  MATH  Google Scholar 

  12. J. Hartmanis and R. E. Stearns. Pair algebras and their application to automata theory. Information and Control, 7(4):485–507, 1964.

    Article  MathSciNet  Google Scholar 

  13. J. Hartmanis and R. E. Stearns. Algebraic Structure Theory of Sequential Machines. Prentice-Hall, 1966.

    Google Scholar 

  14. 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.

    Google Scholar 

  15. Dexter Kozen. A completeness theorem for Kleene algebras and the algebra of regular events. Information and Computation, 110(2):366–390, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  16. 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.

    Google Scholar 

  17. J. Lambek. Some Galois connections in elementary number theory. J. of Number Theory, 47(3):371–377, June 1994.

    Article  MATH  MathSciNet  Google Scholar 

  18. 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.

    Google Scholar 

  19. Oystein Ore. Galois connexions. Transactions of the American Mathematical Society, 55:493–513, 1944.

    Article  MATH  MathSciNet  Google Scholar 

  20. J. Schmidt. Beitrage für Filtertheorie. II. Math. Nachr., 10:197–232, 1953.

    Article  MATH  MathSciNet  Google Scholar 

  21. Ian Stewart. Galois Theory. Chapman and Hall, 2nd edition, 1989.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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

Publish with us

Policies and ethics