{
  "id": "1612.04353",
  "version": "v1",
  "published": "2016-12-13T20:39:09.000Z",
  "updated": "2016-12-13T20:39:09.000Z",
  "title": "Galois connection for multiple-output operations",
  "authors": [
    "Emil Jeřábek"
  ],
  "comment": "35 pages",
  "categories": [
    "math.LO",
    "cs.LO"
  ],
  "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\\colon B^n\\to 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\\colon B^n\\to B^m$, employing invariants valued in partially ordered monoids instead of relations. In particular, our set-up encompasses the case of permutations $f\\colon B^n\\to B^n$, motivated by problems in reversible computing.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-12-13T20:39:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "08A40",
      "06F05"
    ],
    "keywords": [
      "galois connection",
      "multiple-output operations",
      "universal algebra",
      "set-up encompasses",
      "finitary operations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 35,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}