A Galois connection between sets of relations and sets of surjective functions
by
Ferdinand Börner
University of Potsdam

We investigate a Galois Connection Inv-sPol between sets of relations and sets of surjective functions on a finite basic set A. This connection is obtained from the Galois connection Inv-Pol by restricting the set of all functions on A to the set of all surjective functions. The investigations are motivated by complexity theoretical questions concerning the quantified constraint satisfaction problem. The results are obtained during collaboration with the coauthors of [1].

The Galois closed sets of functions can be represented by surjectively generated clones, and the Galois closed sets of relations are relational clones, closed under the additional operation of universal quantification. The set of all surjectively generated clones forms a complete and algebraic lattice S_A. Similar to the lattice L_A of all clones on A, this lattice is atomic and dually atomic with finitely many atoms and coatoms.

In the case |A|=2 we give a complete description of S_A. For |A| > 2 we prove some results which suggest that S_A is of similar complexity as L_A. Following I. Rosenbergs description of the maximal clones, we can describe the dual atoms in S_A.

[1] F. Börner, A. Bulatov, A. Krokhin, P. Jeavons: Quantified Constraints and Surjective Polymorphisms. Technical Report PRG-RR-02-11, Oxford Univ. Comp. Lab., 2002.

Date received: January 31, 2003