Galois Connections: algorithmic generation

Question

Given two finite posets $P,Q$, is it known any algorithm to count and/or generate every Galois Connection between $P$ and $Q$ ? I'm looking for references about this problem.

Answer 1

You should have a look at Formal Concept Analysis (FCA). Every Galois Connection can be expressed as a binary relation $I$ between two sets $G$ (whose eelements we call objects) and $M$ (whose elements are called attributes). You can define two derivation operators ${⋅}^I:\mathfrak PG\to \mathfrak PM$ and ${⋅}^I:\mathfrak PG\to\mathfrak PM$ in the following way: $$A⊆G:\qquad A^I:=\{m∈M\mid ∀g∈A:g\mathrel I m\}\\ B⊆M: \qquad B^I:=\{g∈G\mid ∀m∈B: g\mathrel I m\}$$

Then $G$ and $M$ can be preordered using this operator and the set inclusion: $$g,h∈G:\qquad g≤_gh:⇔g^I⊆h^I\\ m,n∈M: \qquad m≤_mn:⇔m^I⊆n^I$$

The derivation operators form a Galois Connection between the so preordered sets $(G,≤_g)$ and $(M,≤_m)$. Suppose you have two preorder relations ${\sqsubseteq_g}⊆G×G$ and ${\sqsubseteq_m}⊆M×M$. Then the derivation operators form a Galois connection between $(G,\sqsubseteq_g)$ and $(M,\sqsubseteq_m)$, iff ${\sqsubseteq_g}⊆{≤_g}$ and ${\sqsubseteq_m}⊆{≤_m}$.

Once you have a Galois Connection, each complete congruence relation on the corresponding concept lattice (or Galois lattice) describes another concept lattice and thus, another Galois Connection between the preordered sets. The linked book also includes the theory that links these congruences with the binary relation $I$ (chapter 3.2).

Furthermore, the relation $I$ is a bond (chapter 5.1). This fact tells you something about the structure of $I$.

In the FCA community several algorithms and mathematical methods have been developed. Naturally the main focus lies on the computation of concept lattices, but some some of the algorithms should be easily adopted to your problem.

EDIT: Bernhard Ganter has written an article about “Relational Galois Connections”, in Formal Concept Analysis, Lecture Notes in Computer Science Volume 4390, 2007, pp 1-17, which can be found here. It deals with the topic in a more general way.