{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:29:26Z","timestamp":1750307366300,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T00:00:00Z","timestamp":1277942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["07-BLAN-0327-04"],"award-info":[{"award-number":["07-BLAN-0327-04"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2010,7]]},"abstract":"<jats:p>We study the computational complexity of Boolean constraint satisfaction problems with cardinality constraint. A Galois connection between clones and coclones has received a lot of attention in the context of complexity considerations for constraint satisfaction problems. This connection does not seem to help when considering constraint satisfaction problems that support in addition a cardinality constraint. We prove that a similar Galois connection, involving a weaker closure operator and partial polymorphisms, can be applied to such problems. Thus, we establish dichotomies for the decision as well as for the counting problems in Schaefer's framework.<\/jats:p>","DOI":"10.1145\/1805950.1805954","type":"journal-article","created":{"date-parts":[[2010,7,15]],"date-time":"2010-07-15T12:48:46Z","timestamp":1279198126000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Nonuniform Boolean constraint satisfaction problems with cardinality constraint"],"prefix":"10.1145","volume":"11","author":[{"given":"Nadia","family":"Creignou","sequence":"first","affiliation":[{"name":"Aix-Marseille Universit\u00e9, Marseille, France"}]},{"given":"Henning","family":"Schnoor","sequence":"additional","affiliation":[{"name":"Christian-Albrechts-Universit\u00e4t Kiel, Kiel, Germany"}]},{"given":"Ilka","family":"Schnoor","sequence":"additional","affiliation":[{"name":"Universit\u00e4t zu L\u00fcbeck, L\u00fcbeck, Germany"}]}],"member":"320","published-online":{"date-parts":[[2010,7,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_12"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_63"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.08.024"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/954092.954101"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 16th International Workshop on Computer Science Logic. Lecture Notes in Computer Science","volume":"2471","author":"B\u00f6hler E.","unstructured":"B\u00f6hler , E. , Hemaspaandra , E. , Reith , S. , and Vollmer , H . 2002. Equivalence and isomorphism for Boolean constraint satisfaction . In Proceedings of the 16th International Workshop on Computer Science Logic. Lecture Notes in Computer Science , vol. 2471 . Springer Verlag, Berlin, 412--426. B\u00f6hler, E., Hemaspaandra, E., Reith, S., and Vollmer, H. 2002. Equivalence and isomorphism for Boolean constraint satisfaction. In Proceedings of the 16th International Workshop on Computer Science Logic. Lecture Notes in Computer Science, vol. 2471. Springer Verlag, Berlin, 412--426."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science","volume":"2996","author":"B\u00f6hler E.","unstructured":"B\u00f6hler , E. , Hemaspaandra , E. , Reith , S. , and Vollmer , H . 2004. The complexity of Boolean constraint isomorphism . In Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science , vol. 2996 . Springer Verlag, Berlin Heidelberg, 164--175. B\u00f6hler, E., Hemaspaandra, E., Reith, S., and Vollmer, H. 2004. The complexity of Boolean constraint isomorphism. In Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2996. Springer Verlag, Berlin Heidelberg, 164--175."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.06.003"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1087"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0016"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.02.005"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446311"},{"key":"e_1_2_1_15_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability A Guide to the Theory of NP-Completeness. Freeman New York.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability A Guide to the Theory of NP-Completeness. Freeman New York."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00037-3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0195-9"},{"key":"e_1_2_1_21_1","first-page":"1","article-title":"The two-valued iterative systems of mathematical logic","volume":"5","author":"Post E. L.","year":"1941","unstructured":"Post , E. L. 1941 . The two-valued iterative systems of mathematical logic . Ann. Math. Stud. 5 , 1 -- 122 . Post, E. L. 1941. The two-valued iterative systems of mathematical logic. Ann. Math. Stud. 5, 1--122.","journal-title":"Ann. Math. Stud."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00092-0"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01069627"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_9"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0019-5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90369-Q"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054191000066"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805950.1805954","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1805950.1805954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:42Z","timestamp":1750245762000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805950.1805954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["10.1145\/1805950.1805954"],"URL":"https:\/\/doi.org\/10.1145\/1805950.1805954","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2010,7]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}