1

{Art98} E. Artin. Galois Theory. Dover Publications, 1998.

2

Elmar Böhler , Edith Hemaspaandra , Steffen Reith , Heribert Vollmer, Equivalence and Isomorphism for Boolean Constraint Satisfaction, Proceedings of the 16th International Workshop and 11th Annual Conference of the EACSL on Computer Science Logic, p.412-426, September 22-25, 2002

3

{BHRV04} E. Böhler, E. Hemaspaandra, S. Reith, and H. Vollmer. The complexity of Boolean constraint isomorphism. In Proceedings 21st Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Berlin Heidelberg, 2004. Springer Verlag. To appear.

4

{BKKR69} V. G. Bodnarchuk, L. A. Kalužnin, V. N. Kotov, and B. A. Romov. Galois theory for Post algebras. i, ii. Cybernetics, 5:243--252, 531--539, 1969.

5

Nadia Creignou , Miki Hermann, Complexity of generalized satisfiability counting problems, Information and Computation, v.125 n.1, p.1-12, Feb. 25, 1996  [doi>10.1006/inco.1996.0016]

6

{CH97} N. Creignou and J.-J. Hébrard. On generating all solutions of generalized satisfiability problems. Informatique Théorique et Applications/Theoretical Informatics and Applications, 31(6):499--511, 1997.

7

Nadia Creignou , Sanjeev Khanna , Madhu Sudan, Complexity classifications of boolean constraint satisfaction problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001

8

Nadia Creignou, A dichotomy theorem for maximum generalized satisfiability problems, Journal of Computer and System Sciences, v.51 n.3, p.511-522, Dec. 1995  [doi>10.1006/jcss.1995.1087]

9

Nadia Creignou, Complexity versus stability for classes of propositional formulas, Information Processing Letters, v.68 n.4, p.161-165, Nov. 30, 1998  [doi>10.1016/S0020-0190(98)00163-X]

10

{Dal00} V. Dalmau. Computational complexity of problems over generalized formulas. PhD thesis, Department de Llenguatges i Sistemes Informàtica, Universitat Politécnica de Catalunya, 2000.

11

Rina Dechter , Judea Pearl, Structure identification in relational data, Artificial Intelligence, v.58 n.1-3, p.237-270, Dec. 1992  [doi>10.1016/0004-3702(92)90009-M]

12

{Gei68} D. Geiger. Closed systems of functions and predicates. Pac. J. Math, 27(2):228--250, 1968.

13

Peter Jeavons , David Cohen, An Algebraic Characterization of Tractable Constraints, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.633-642, August 24-26, 1995

14

Peter Jeavons , David Cohen , Marc Gyssens, Closure properties of constraints, Journal of the ACM (JACM), v.44 n.4, p.527-548, July 1997  [doi>10.1145/263867.263489]

15

Peter Jeavons , David Cohen , Marc Gyssens, How to Determine the Expressive Power of Constraints, Constraints, v.4 n.2, p.113-131, May 1999  [doi>10.1023/A:1009890709297]

16

Peter Jeavons, On the algebraic structure of combinatorial problems, Theoretical Computer Science, v.200 n.1-2, p.185-204, June 28, 1998  [doi>10.1016/S0304-3975(97)00230-2]

17

Laurent Juban, Dichotomy Theorem for the Generalized Unique Satisfiability Problem, Proceedings of the 12th International Symposium on Fundamentals of Computation Theory, p.327-337, August 30-September 03, 1999

18

{KJ03} A. Krokhin and P. Jonsson. Recognizing frozen variables in constraint satisfaction problems. Technical Report TR03-062, ECCC Reports, 2003.

19

Lefteris M. Kirousis , Phokion G. Kolaitis, The complexity of minimal satisfiability problems, Information and Computation, v.187 n.1, p.20-39, November 25, 2003  [doi>10.1016/S0890-5401(03)00037-3]

20

{Kol03} P. Kolaitis. Constraint satisfaction, databases, and logic. In Proceedings 18th International Joint Conference on Artificial Intelligence, pages 1587--1595, 2003.

21

Dimitris Kavvadias , Martha Sideri, The Inverse Satisfiability Problem, SIAM Journal on Computing, v.28 n.1, p.152-163, Feb. 1999  [doi>10.1137/S0097539795285114]

22

Sanjeev Khanna , Madhu Sudan , Luca Trevisan, Constraint Satisfaction: The Approximability of Minimization Problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.282, June 24-27, 1997

23

Sanjeev Khanna , Madhu Sudan , David P. Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.11-20, May 04-06, 1997, El Paso, Texas, United States  [doi>10.1145/258533.258538]

24

Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Journal of Computer and System Sciences, v.61 n.2, p.302-332, Oct. 2000  [doi>10.1006/jcss.2000.1713]

25

{Pap94} C. H. Papadimitriou. Computational Complexity. Addison-Wesley, Reading, MA, 1994.

26

Nicholas Pippenger, Theories of computability, Cambridge University Press, New York, NY, 1997

27

{PK79} R. Pöschel and L. A. Kalu znin. Funktionen- und Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin, 1979.

28

{Pös01} R. Pöschel. Galois connection for operations and relations. Technical Report MATH-LA-8-2001, Technische Universität Dresden, 2001.

29

Steffen Reith , Heribert Vollmer, Optimal satisfiability for propositional calculi and constraint satisfaction problems, Information and Computation, v.186 n.1, p.1-19, 10 October 2003  [doi>10.1016/S0890-5401(03)00092-0]

30

Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States  [doi>10.1145/800133.804350]

31

Uri Zwick, Finding almost-satisfying assignments, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.551-560, May 24-26, 1998, Dallas, Texas, United States  [doi>10.1145/276698.276869]

Lane A. Hemaspaandra: colleagues