Skip to main content
SpringerLink
Log in
SpringerLink
Log in

Basics of Galois Connections

  • Chapter
Complexity of Constraints

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5250))

Abstract

We give an overview of basic properties of Galois connections between sets of relations and sets of functions or generalized functions. First we focus on the Galois connections lnv–Pol and lnv–mPol . Then we use these results to provide some tools for the representation of several closure operators on relations as closure operators of some Galois connections.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.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.

References

  1. Blyth, T.S., Janowitz, M.F.: Residuation Theory. Pergamon Press, Oxford (1972)

    MATH  Google Scholar 

  2. Bodnaržuk, V.G., Kalužnin, L.A., Kotov, N.N., Romov, B.A.: Galois theory for Post algebras I. Kibernetika 3, 1–10 (1969) (Russian)

    MathSciNet  Google Scholar 

  3. Bodnaržuk, V.G., Kalužnin, L.A., Kotov, N.N., Romov, B.A.: Galois theory for Post algebras II. Kibernetika 5, 1–9 (1969) (Russian)

    MathSciNet  Google Scholar 

  4. Börner, F.: Operationen auf Relationen. Diss., Universität Leipzig (1989)

    Google Scholar 

  5. Börner, F.: Krasneralgebren. Logos-Verlag (2000)

    Google Scholar 

  6. Börner, F.: Total multifunctions and relations. Contributions to General Algebra 13, 23–36 (2001)

    MathSciNet  MATH  Google Scholar 

  7. Börner, F., Pöschel, R., Sushchansky, V.: Boolean systems of relations and Galois connections. Acta Sci. Math (Szeged) 68, 535–560 (2002)

    MathSciNet  MATH  Google Scholar 

  8. Börner, F., Krokhin, A., Bulatov, A., Jeavons, P.: Quantified constraints and surjective polymorphisms. Technical Report PRG-RR-02-11, Comp. Lab., Univ. of Oxford, UK (2002)

    Google Scholar 

  9. Börner, F., Bulatov, A., Jeavons, P., Krokhin, A.: Quantified Constraints: Algorithms and Complexity. In: Baaz, M., Makowsky, J.A. (eds.) Proc. 17th Int. Workshop on Computer Science Logic CSL, pp. 58–70. Springer, Heidelberg (2003)

    Google Scholar 

  10. Bulatov, A., Krokhin, A., Jeavons, P.: The complexity of maximal constraint languages. In: Proc. 33rd ACM Symp. on Theory of Computing, STOC 2001, pp. 667–674 (2001)

    Google Scholar 

  11. Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Math. and Appl. 7 (2001)

    Google Scholar 

  12. Freivald, R.V.: Functional completeness for not everywhere defined functions of the algebra of logic. Diskr. Analiz. 8, 55–68 (1966)

    MathSciNet  Google Scholar 

  13. Geiger, D.: Closed systems of functions and predicates. Pacific J. Math. 27, 95–100 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  14. Jeavons, P., Cohen, D., Gyssens, M.: Closure Properties of Constraints. J. of the ACM 44, 527–548 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  15. Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science 200, 185–204 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  16. Krasner, M.: Une généralisation de la notion de corps. J. Math. pure et appl. 17, 367–385 (1938)

    MATH  Google Scholar 

  17. Krasner, M.: Généralisation abstraite de la théorie de Galois. Colloq. internat. Centre nat. Rech. Sci., Algèbre et Théorie des Nombres 24, 163–168 (1950)

    MATH  Google Scholar 

  18. Lau, D.: Function Algebras on Finite Sets. Springer, Heidelberg (2006)

    MATH  Google Scholar 

  19. McKenzie, R.N., McNulty, G.F., Taylor, W.F.: Algebras, Lattices, Varieties, vol. 1. Wadsworth & Brooks/Cole, Monterey (1987)

    MATH  Google Scholar 

  20. Pöschel, R., Kaluznin, L.A.: Funktionen- und Relationenalgebren. Verlag der Wissenschaften, Berlin (1979)

    Google Scholar 

  21. Pöschel, R.: Closure properties for relational systems with given endomorphism structure. Beitr. Alg. Geom. 18, 153–166 (1984)

    MathSciNet  MATH  Google Scholar 

  22. Pöschel, R.: Galois connections for operations and relations. Technical Report MATH-AL-8-2001, TU Dresden (2001)

    Google Scholar 

  23. Post, E.L.: Determination of all closed systems of truth tables. Bull. Amer. Math. Soc. 26, 437 (1920)

    Google Scholar 

  24. Post, E.L.: Introduction to a general theory of elementary propositions. Amer. J. Math. 43, 163–185 (1921)

    Article  MathSciNet  MATH  Google Scholar 

  25. Post, E.L.: The two-valued iterative system of mathematical logic. Annals Math. Stud. 5 (1941)

    Google Scholar 

  26. Romov, B.A.: The algebras of partial functions and their invariants. Kibernetika 2, 1–11 (1981); Engl. transl.: Cybernetics 17, 157–167 (1981)

    MathSciNet  MATH  Google Scholar 

  27. Romov, B.A.: Hyperclones on a finite set. In: Mult. Val. Logic 1998, vol. 3, pp. 285–300 (1998)

    Google Scholar 

  28. Romov, B.A.: Partial hyperclones on a finite set. In: Proc. 32nd IEEE Int. Symp. Multiple-Valued Logic, pp. 17–27 (2002)

    Google Scholar 

  29. Rosenberg, I.G.: Galois theory for partial algebras. In: Freese, R., Garcia, O. (eds.) Universal Algebra and Lattice Theory. Lect. Notes in Math., pp. 257–272. Springer, Heidelberg (1883)

    Google Scholar 

  30. Rosenberg, I.G.: Minimal clones I: the five types. Lectures in Universal Algebra. Colloq. Math. Soc. J. Bolyai 43, 405–427 (1983)

    MathSciNet  Google Scholar 

  31. Rosenberg, I.G.: Composition of functions on finite sets, completeness and relations, a short survey. In: Rine, D. (ed.) Multiple-valued Logic and Computer Science, 2nd edn., pp. 150–192. North-Holland, Amsterdam (1984)

    Google Scholar 

  32. Rosenberg, I.G.: An algebraic approach to hyperalgebras. In: Proc. 26th ISMVL, pp. 203–207. IEEE, Los Alamitos (1996)

    Google Scholar 

  33. Schaefer, T.: The complexity of satisfyability problems. In: Proc. 10th ACM Symp. on Theory of Computing, STOC 1978, pp. 216–226 (1978)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Universität Potsdam, PF 90 03 27, D–14 439, Potsdam, Germany

    Ferdinand Börner

Authors
  1. Ferdinand Börner
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. LIF (CNRS UMR 6166), Aix-Marseille Université, 163 avenue de Luminy, F-13288, Marseille, France

    Nadia Creignou

  2. IBM Almaden Research Center, Computer Science Principles and Methodologies, and Computer Science Department, University of California, Santa Cruz, USA

    Phokion G. Kolaitis

  3. Institut für Theoretische Informatik, Leibniz, Universität Hannover, Appelstr. 4, 30167, Hannover, Germany

    Heribert Vollmer

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Börner, F. (2008). Basics of Galois Connections. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds) Complexity of Constraints. Lecture Notes in Computer Science, vol 5250. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92800-3_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-92800-3_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-92799-0

  • Online ISBN: 978-3-540-92800-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation