Abstract. We study the basic Galois connection induced by the ``satisfaction" relation between external operations $A^n\rightarrow B$ defined on a set $A$ and valued in a possibly different set $B$ on the one hand, and ordered pairs $(R,S)$ of relations $R\subseteq A^m$ and $S\subseteq B^m$, called relational constraints, on the other hand. We decompose the closure maps associated with this Galois connection, in terms of closure operators corresponding to simple closure conditions describing the corresponding Galois closed sets of functions and constraints. We consider further Galois correspondences by restricting the sets of primal and dual objects to fixed arities. We describe the restricted Galois closure systems by means of parametrized analogues of the simple closure conditions, and present factorizations of the corresponding Galois closure maps into simpler closure operators.

AMS Subject Classification (1991): 08A02

Keyword(s): Galois connections, external operations, homomorphisms, function classes, class composition, relations, constraints, preservation, constraint satisfaction, minors, factorizations, operator decompositions

Received February 25, 2005, and in revised form December 31, 2005. (Registered under 5904/2009.)