{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:19:22Z","timestamp":1750306762262,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/H00677X\/1"],"award-info":[{"award-number":["EP\/H00677X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"name":"LIX-Qualcomm Postdoctoral Fellowship"},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["(FP7\/2007-2013 Grant Agreement no. 257039)"],"award-info":[{"award-number":["(FP7\/2007-2013 Grant Agreement no. 257039)"]}],"id":[{"id":"10.13039\/501100004963","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":[[2013,11]]},"abstract":"<jats:p>\n            A famous result by Jeavons, Cohen, and Gyssens shows that every Constraint Satisfaction Problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called universal algebraic approach to a systematic theory of tractability and hardness in finite domain constraint satisfaction. Not surprisingly, the theorem of Jeavons et al. fails for arbitrary infinite domain CSPs. Many CSPs of practical interest, though, and in particular those CSPs that are motivated by qualitative reasoning calculi from artificial intelligence, can be formulated with constraint languages that are rather well-behaved from a model-theoretic point of view. In particular, the automorphism group of these constraint languages tends to be\n            <jats:italic>large<\/jats:italic>\n            in the sense that the number of orbits of\n            <jats:italic>n<\/jats:italic>\n            -subsets of the automorphism group is bounded by some function in\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            In this article we present a generalization of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits of\n            <jats:italic>n<\/jats:italic>\n            -subsets grows subexponentially in\n            <jats:italic>n<\/jats:italic>\n            , and prove that preservation under a semi-lattice operation for such CSPs implies polynomial-time tractability. Unlike the result of Jeavons et al., this includes CSPs that cannot be solved by Datalog.\n          <\/jats:p>","DOI":"10.1145\/2528933","type":"journal-article","created":{"date-parts":[[2013,12,4]],"date-time":"2013-12-04T14:04:47Z","timestamp":1386165887000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Constraint satisfaction tractability from semi-lattice operations on infinite sets"],"prefix":"10.1145","volume":"14","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique, France"}]},{"given":"H. Dugald","family":"Macpherson","sequence":"additional","affiliation":[{"name":"University of Leeds, UK"}]},{"given":"Johan","family":"Thapper","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Sud 11, France"}]}],"member":"320","published-online":{"date-parts":[[2013,11,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.34"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(1:2)2007"},{"key":"e_1_2_1_3_1","first-page":"3","article-title":"On the scope of the universal-algebraic approach to constraint satisfaction","volume":"8","author":"Bodirsky M.","year":"2012","journal-title":"Logical Methods Comput. Sci."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1740582.1740583"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"e_1_2_1_7_1","unstructured":"Bodirsky M. and Pinsker M. 2012. Minimal functions on the random graph. Israel Journal of Mathematics. http:\/\/arxiv.org\/pdf\/1003.4030.pdf.  Bodirsky M. and Pinsker M. 2012. Minimal functions on the random graph. Israel Journal of Mathematics. http:\/\/arxiv.org\/pdf\/1003.4030.pdf."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01214702"},{"volume-title":"Oligomorphic Permutation Groups","author":"Cameron P. J.","key":"e_1_2_1_10_1"},{"volume-title":"LMS Student Text 45","author":"Cameron P. J.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","unstructured":"Chen H. Dalmau V. and Grussien B. 2011. Arc consistency and friends. http:\/\/arxiv.org\/pdf\/1104.4993.pdf.  Chen H. Dalmau V. and Grussien B. 2011. Arc consistency and friends. http:\/\/arxiv.org\/pdf\/1104.4993.pdf."},{"volume-title":"Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP'99)","author":"Dalmau V.","key":"e_1_2_1_13_1"},{"volume-title":"Constraint Processing. Morgan Kaufmann","author":"Dechter R.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"volume-title":"Invariant Descriptive Set Theory. Pure and Applied Mathematics","author":"Gao S.","key":"e_1_2_1_16_1"},{"volume-title":"A Shorter Model Theory","author":"Hodges W.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(87)90003-0"},{"key":"e_1_2_1_20_1","first-page":"2","article-title":"Finite posets and topological spaces in locally finite varieties","volume":"52","author":"Larose B.","year":"2004","journal-title":"Algebra Universalis"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-51.2.246"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2528933","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2528933","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:45Z","timestamp":1750231725000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2528933"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2528933"],"URL":"https:\/\/doi.org\/10.1145\/2528933","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}