Skip to main content
SpringerLink
Log in

Galois connection for multiple-output operations

  • Published:
Algebra universalis Aims and scope Submit manuscript

Abstract

It is a classical result from universal algebra that the notions of polymorphisms and invariants provide a Galois connection between suitably closed classes (clones) of finitary operations \(f:B^n\rightarrow B\), and classes (coclones) of relations \(r\subseteq B^k\). We will present a generalization of this duality to classes of (multi-valued, partial) functions \(f:B^n\rightarrow B^m\), employing invariants valued in partially ordered monoids instead of relations. In particular, our set-up encompasses the case of permutations \(f:B^n\rightarrow B^n\), motivated by problems in reversible computing.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aaronson, S.: Classifying reversible gates. Theoretical Computer Science Stack Exchange (2014). http://cstheory.stackexchange.com/q/25730. Accessed 14 Mar 2018

  2. Aaronson, S., Grier, D., Schaeffer, L.: The classification of reversible bit operations (2015). arXiv:1504.05155 (quant-ph)

  3. Bloom, S.L.: Varieties of ordered algebras. J. Comput. Syst. Sci. 13(2), 200–212 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bodnarchuk, V.G., Kaluzhnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras. I. Cybernetics 5(3), 243–252 (1969). (Translated from Kibernetika 5(3), 1–10 (1969))

    Article  MathSciNet  MATH  Google Scholar 

  5. Bodnarchuk, V.G., Kaluzhnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras. II. Cybernetics 5(5), 531–539 (1969). (Translated from Kibernetika 5(5), 1–9 (1969))

    Article  MATH  Google Scholar 

  6. Burris, S.N., Sankappanavar, H.P.: A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78. Springer, New York (1981)

    MATH  Google Scholar 

  7. Couceiro, M.: Galois Connections for Generalized Functions and Relational Constraints. In: Chajda, Dorfer, Eigenthaler, Halaš, Müller, Pöschel (eds.) Contributions to General Algebra, vol. 16, pp. 35–54. Verlag Johannes Heyn, Klagenfurt (2005)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Grillet, P.A.: On subdirectly irreducible commutative semigroups. Paci. J. Math. 69(1), 55–71 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  10. Iskander, A.A.: Subalgebra systems of powers of partial universal algebras. Pac. J. Math. 38(2), 457–463 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  11. Jaeger, G.: Quantum Information: An Overview. Springer, New York (2007)

    MATH  Google Scholar 

  12. Jeřábek, E.: Answer to [1]. Theoretical Computer Science Stack Exchange (2014). http://cstheory.stackexchange.com/a/25791. Accessed 14 Mar 2018

  13. Kerkhoff, S.: A general Galois theory for operations and relations in arbitrary categories. Algebra Universalis 68(3–4), 325–352 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  14. Krasner, M.: Généralisation abstraite de la théorie de Galois. In: Algèbre et théorie des nombres, Paris 25. 9.–1. 10. 1949. Colloques Internationaux du Centre National de la Recherche Scientifique, vol. 24, pp. 163–168 (1950)

  15. Krasner, M.: Abstract Galois theory and endotheory. I. Acta Sci. Math. 50, 253–286 (1986)

    MathSciNet  MATH  Google Scholar 

  16. Mal’cev, A.I.: On homomorphisms onto finite groups. Uchen. Zap. Ivanov. Gos. Ped. Inst. 18, 49–60 (1958)

    Google Scholar 

  17. Mal’cev, A.I.: Algebraic Systems, Die Grundlehren der mathematischen Wissenschaften, vol. 192. Springer, Berlin (1973). (Translated from Russian by B. D. Seckler and A. P. Doohovskoy (1973))

  18. Perumalla, K.S.: Introduction to Reversible Computing. Chapman and Hall/CRC, Computational Science Series, Boca Raton (2013)

  19. Pigozzi, D.: Partially ordered varieties and quasivarieties. Lecture notes (2004). http://orion.math.iastate.edu/dpigozzi. Accessed 14 Mar 2018

  20. Pöschel, R.: A General Galois Theory for Operations and Relations and Concrete Characterization of Related Algebraic Structures. Tech. Rep. R-01/80. Akademie der Wissenschaften der DDR, Zentralinstitut für Mathematik und Mechanik, Berlin (1980)

  21. Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic. No. 5 in Annals of Mathematics Studies. Princeton University Press, Princeton (1941)

    MATH  Google Scholar 

  22. Rosenberg, I.G.: A classification of universal algebras by infinitary relations. Algebra Universalis 1(1), 350–354 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  23. Rosenberg, I.G.: Galois theory for partial algebras. In: R.S. Freese, O.C. Garcia (eds.) Universal Algebra and Lattice Theory. Lecture Notes in Mathematics, vol. 1004, pp. 257–272. Springer, Berlin (1983)

  24. Schein, B.M.: Homomorphisms and subdirect decompositions of semigroups. Pac. J. Math. 17(3), 529–547 (1966)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics of the Czech Academy of Sciences, Žitná 25, 115 67, Praha 1, Czech Republic

    Emil Jeřábek

Authors
  1. Emil Jeřábek
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Emil Jeřábek.

Additional information

Presented by R. Pöschel.

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013) / ERC grant agreement no. 339691. The Institute of Mathematics of the Czech Academy of Sciences is supported by RVO: 67985840.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jeřábek, E. Galois connection for multiple-output operations. Algebra Univers. 79, 17 (2018). https://doi.org/10.1007/s00012-018-0499-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00012-018-0499-7

Mathematics Subject Classification

Keywords

Search

Navigation