Abstract
In our ISMVL 2012 paper, we introduced the notion of max-co-clone as a set of relations closed under a new type of quantification, max-quantification. This new concept was motivated by its connections to approximation complexity of counting constraint satisfaction problems. In this paper, we go beyond scattered examples of max-co-clones and describe all max-co-clones on a 2-elements set (Boolean max-co-clones). It turns out that there are infinitely many Boolean max-co-clones and that all of them are regular co-clones, although it is not true for larger sets. Also, there are many usual co-clones that are not closed under max-quantification, and therefore are not max-co-clones.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahlswede R., Daykin D.E.: An inequality for the weights of two families of sets, their unions and intersections. Z. Wahrsch. Verw. Gebiete 43, 183–185 (1978)
Bodnarchuk, V.G., Kaluzhnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras. I. Kibernetika, 3, 1–10 (1969) (Russian)
Börner, F.: Basics of Galois connections. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints, pp. 38–67, LNCS, vol. 5250. Springer (2008)
Börner F., Bulatov A., Chen H., Jeavons P., Krokhin A.: The complexity of constraint satisfaction games and QCSP. Inf. Comput. 207, 923–944 (2009)
Börner F., Pöschel R., Sushchansky V.: Boolean systems of relations and Galois connections. Acta Sci. Math. (Szeged) 68, 535–560 (2002)
Bulatov, A.: The complexity of the counting constraint satisfaction problem. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I: Track A: Algorithms, Automata, Complexity, and Games, pp. 646–661, LNCS, vol. 5125. Springer (2008)
Bulatov, A.: Counting problems and clones of functions. In: ISMVL 2009, 39th International Symposium on Multiple-Valued Logic, 21–23 May 2009, Naha, Okinawa, Japan, pp. 1–6, IEEE Computer Society (2009)
Bulatov, A.: The complexity of the counting constraint satisfaction problem. J. of the ACM, 60 (2013)
Bulatov, A., Dyer, M.E., Goldberg, L.A., Jerrum, M.: Log-supermodular functions, functional clones and counting CSPs. In: Dürr, C., Wilke, T. (eds.) The 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th–March 3rd, 2012, Paris, France, pp. 302–313, LIPIcs, vol. 14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
Bulatov, A., Dyer, M.E., Goldberg, L.A., Jerrum, M., Mcquillan, C.: The expressibility of functions on the boolean domain, with applications to counting CSPs J. of the ACM, 60 (2013)
Bulatov, A., Hedayaty, A.: Counting quantifiers, subset surjective functions, and counting CSPs. In: Miller, D.M, Gaudet, V.C. (eds.) The 42nd IEEE International Symposium on Multiple-Valued Logic, ISMVL 2012, Victoria, BC, Canada, May 14–16, 2012, pp. 331–336, IEEE (2012)
Bulatov A., Hedayaty A.: Counting problems and clones of functions. Multiple-Valued Logic and Soft Computing 18, 117–138 (2012)
Creignou, N., Khanna, S., Sudan, M.: Complexity classifications of Boolean constraint satisfaction problems. SIAM Monographs on Discrete Mathematics and Applications, vol. 7. SIAM (2001)
Creignou N., Kolaitis P.G., Zanuttini B.: Structure identification of Boolean relations and plain bases for co-clones. J. Comput. Syst. Sci. 74, 1103–1115 (2008)
Dyer M.E., Goldberg L.A., Greenhill C., Jerrum M.: On the relative complexity of approximate counting problems. Algorithmica 38, 471–500 (2003)
Dyer M.E., Goldberg L.A., Jerrum M.: An approximation trichotomy for Boolean #CSP. J. Comput. Syst. Sci. 76, 267–277 (2010)
Geiger D.: Closed systems of function and predicates. Pacific J. of Math. 27, 95–100 (1968)
Jeavons P.G., Cohen D.A., Gyssens G.: Closure properties of constraints. J. of the ACM 44, 527–548 (1997)
Madelaine, F.R., Martin, B., Stacho, J.: Constraint satisfaction with counting quantifiers. In: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds.) Computer Science—Theory and Applications—7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3–7, 2012, pp. 253–265, LNCS, vol. 7353, Springer (2012)
Pöschel, R.: Galois connection for operations and relations. Technical Report MATH-AL-8-2001, Technische Universität Dresden, Germany (2001)
Pöschel, R., Kalužnin, L.A.: Funktionen- und Relationenalgebren. DVW, Berlin (1979)
Post, E.L.: The two-valued iterative systems of mathematical logic. Annals Mathematical Studies, vol. 5, Princeton University Press (1941)
Schaefer, T.: The complexity of satisfiability problems. In: Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., Aho, A.V. (eds.) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1–3, 1978, San Diego, California, USA, pp. 216–226, ACM (1978)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by M. Jackson.
Dedicated to Brian Davey on the occasion of his 65th birthday
This research was supported by NSERC Discovery Grant.
Rights and permissions
About this article
Cite this article
Bulatov, A.A. Boolean max-co-clones. Algebra Univers. 74, 139–162 (2015). https://doi.org/10.1007/s00012-015-0336-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00012-015-0336-1