{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T17:25:40Z","timestamp":1768584340973,"version":"3.49.0"},"reference-count":92,"publisher":"Elsevier","isbn-type":[{"value":"9780444527264","type":"print"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1016\/s1574-6526(06)80012-x","type":"book-chapter","created":{"date-parts":[[2008,2,26]],"date-time":"2008-02-26T16:51:39Z","timestamp":1204044699000},"page":"245-280","source":"Crossref","is-referenced-by-count":28,"title":["The Complexity of Constraint Languages"],"prefix":"10.1016","member":"78","reference":[{"key":"10.1016\/S1574-6526(06)80012-X_bib1","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","article-title":"Maintaining knowledge about temporal intervals","volume":"26","author":"Allen","year":"1983","journal-title":"Communications of the ACM"},{"key":"10.1016\/S1574-6526(06)80012-X_bib2","series-title":"Proceedings 20th IEEE Symposium on Logic in Computer Science (LICS 2005)","first-page":"106","article-title":"On digraph coloring problems and treewidth duality","author":"Atserias","year":"2005"},{"key":"10.1016\/S1574-6526(06)80012-X_bib3","unstructured":"M. Bodirsky and J. Ne\u0161et\u0159il. Constraint satisfaction with countable homogeneous templates. To appear in the the Journal of Logic and Computation."},{"key":"10.1016\/S1574-6526(06)80012-X_bib4","series-title":"Proceedings of Computer Science Logic and the 8th Kurt G\u00f6del Colloquium","first-page":"44","article-title":"Constraint satisfaction with countable homogeneous templates","volume":"volume 2803","author":"Bodirsky","year":"2003"},{"key":"10.1016\/S1574-6526(06)80012-X_bib5","series-title":"Proceedings of Computer Science Logic and the 8th Kurt G\u00f6del Colloquium","first-page":"58","article-title":"Quantified constraints: Algorithms and complexity","volume":"volume 2803","author":"Boerner","year":"2003"},{"issue":"1\u20132","key":"10.1016\/S1574-6526(06)80012-X_bib6","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0004-3702(02)00224-2","article-title":"Disjunctions, independence, refinements","volume":"140","author":"Broxvall","year":"2002","journal-title":"Artificial Intelligence"},{"issue":"1","key":"10.1016\/S1574-6526(06)80012-X_bib7","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.tcs.2005.09.028","article-title":"H-coloring dichotomy revisited","volume":"349","author":"Bulatov","year":"2005","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1574-6526(06)80012-X_bib8","unstructured":"A. Bulatov and V. Dalmau. Mal'tsev constraints are tractable. SIAM Journal on Computing. (To appear)."},{"key":"10.1016\/S1574-6526(06)80012-X_bib9","series-title":"Proceedings 44th Symposium on Foundations of Computer Science (FOCS 2003)","first-page":"562","article-title":"Towards a dichotomy theorem for the counting constraint satisfaction problem","author":"Bulatov","year":"2003"},{"key":"10.1016\/S1574-6526(06)80012-X_bib10","series-title":"Proceedings 9th International Conference on Constraint Programming\u2014CP'03 (Kinsale, September 2003)","first-page":"183","article-title":"An algebraic approach to multi-sorted constraints","volume":"volume 2833","author":"Bulatov","year":"2003"},{"issue":"3","key":"10.1016\/S1574-6526(06)80012-X_bib11","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","article-title":"Classifying the complexity of constraints using finite algebras","volume":"34","author":"Bulatov","year":"2005","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1574-6526(06)80012-X_bib12","series-title":"Proceedings of the School on Algorithmic Aspects of the Theory of Semigroups and its Applications, Coimbra, Portugal, 2001","first-page":"313","article-title":"Finite semigroups imposing tractable constraints","author":"Bulatov","year":"2002"},{"key":"10.1016\/S1574-6526(06)80012-X_bib13","series-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 2003)","first-page":"197","article-title":"Amalgams of constraint satisfaction problems","author":"Bulatov","year":"2003"},{"key":"10.1016\/S1574-6526(06)80012-X_bib14","series-title":"Proceedings 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02)","first-page":"649","article-title":"A dichotomy theorem for constraints on a three-element set","author":"Bulatov","year":"2002"},{"key":"10.1016\/S1574-6526(06)80012-X_bib15","article-title":"Mal'tsev constraints are tractable","author":"Bulatov","year":"2002"},{"key":"10.1016\/S1574-6526(06)80012-X_bib16","series-title":"Proceedings 18th IEEE Symposium on Logic in Computer Science (LICS'03)","first-page":"321","article-title":"Tractable conservative constraint satisfaction problems","author":"Bulatov","year":"2003"},{"key":"10.1016\/S1574-6526(06)80012-X_bib17","article-title":"Tractable constraints closed under a binary operation","author":"Bulatov","year":"2002"},{"key":"10.1016\/S1574-6526(06)80012-X_bib18","series-title":"Proceedings 27th International Colloquium on Automata, Languages and Programming (ICALP'00)","first-page":"272","article-title":"Constraint satisfaction problems and finite algebras","volume":"volume 1853","author":"Bulatov","year":"2000"},{"key":"10.1016\/S1574-6526(06)80012-X_bib19","series-title":"Proceedings 33rd ACM Symposium on Theory of Computing (STOC'01)","first-page":"667","article-title":"The complexity of maximal constraint languages","author":"Bulatov","year":"2001"},{"key":"10.1016\/S1574-6526(06)80012-X_bib20","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1023\/B:CONS.0000036045.82829.94","article-title":"Tractable decision for a constraint language implies tractable search","volume":"9","author":"Cohen","year":"2004","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80012-X_bib21","series-title":"Proceedings 10th International Conference on Constraint Programming\u2014CP'04","first-page":"212","article-title":"A complete characterization of complexity for Boolean constraint optimization problems","volume":"volume 3258","author":"Cohen","year":"2004"},{"key":"10.1016\/S1574-6526(06)80012-X_bib22","series-title":"Proceedings 9th International Conference on Constraint Programming\u2014CP'03 (Kinsale, September 2003)","first-page":"244","article-title":"Soft constraints: Complexity and multimorphisms","volume":"volume 2833","author":"Cohen","year":"2003"},{"key":"10.1016\/S1574-6526(06)80012-X_bib23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.1400","article-title":"A maximal tractable class of soft constraints","volume":"22","author":"Cohen","year":"2004","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"10.1016\/S1574-6526(06)80012-X_bib24","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1023\/A:1025623111033","article-title":"New tractable classes from old","volume":"8","author":"Cohen","year":"2003","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80012-X_bib25","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1145\/355483.355485","article-title":"Building tractable disjunctive constraints","volume":"47","author":"Cohen","year":"2000","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80012-X_bib26","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0004-3702(94)90021-3","article-title":"Characterising tractable constraints","volume":"65","author":"Cooper","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib27","article-title":"Complexity Classification of Boolean Constraint Satisfaction Problems","volume":"volume 7","author":"Creignou","year":"2001"},{"key":"10.1016\/S1574-6526(06)80012-X_bib28","series-title":"Proceedings 6th International Symposium on Artificial Intelligence and Mathematics","article-title":"A new tractable class of constraint satisfaction problems","author":"Dalmau","year":"2000"},{"key":"10.1016\/S1574-6526(06)80012-X_bib29","series-title":"Proceedings 20th IEEE Symposium on Logic in Computer Science, (LICS 2005)","first-page":"438","article-title":"Generalized majority-minority operations are tractable","author":"Dalmau","year":"2005"},{"key":"10.1016\/S1574-6526(06)80012-X_bib30","first-page":"1","article-title":"Linear datalog and bounded path duality of relational structures","volume":"1","author":"Dalmau","year":"2005","journal-title":"Logical Methods in Computer Science"},{"key":"10.1016\/S1574-6526(06)80012-X_bib31","series-title":"Proceedings 11th International Conference on Constraint Programming\u2014CP'05","first-page":"196","article-title":"Tractable clones of polynomials over semigroups","volume":"volume 3709","author":"Dalmau","year":"2005"},{"key":"10.1016\/S1574-6526(06)80012-X_bib32","series-title":"Constraint Processing","author":"Dechter","year":"2003"},{"issue":"1","key":"10.1016\/S1574-6526(06)80012-X_bib33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","article-title":"Network-based heuristics for constraint satisfaction problems","volume":"34","author":"Dechter","year":"1988","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib34","series-title":"Universal Algebra and Applications in Theoretical Computer Science","author":"Denecke","year":"2002"},{"key":"10.1016\/S1574-6526(06)80012-X_bib35","series-title":"Proceedings of IJCAI'97","first-page":"405","article-title":"Constraint satisfaction over connected row convex constraints","author":"Deville","year":"1997"},{"key":"10.1016\/S1574-6526(06)80012-X_bib36","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0004-3702(98)00093-9","article-title":"A complete classification of tractability in Allen's algebra relative to subsets of basic relations","volume":"106","author":"Drakengren","year":"1998","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib37","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","article-title":"The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory","volume":"28","author":"Feder","year":"1998","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1574-6526(06)80012-X_bib38","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S1574-6526(06)80012-X_bib39","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1023\/B:CONS.0000024049.41091.71","article-title":"Implementing a test for tractability","volume":"9","author":"Gault","year":"2004","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80012-X_bib40","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","article-title":"A comparison of structural CSP decomposition methods","volume":"124","author":"Gottlob","year":"2000","journal-title":"Artificial Intelligence"},{"issue":"3","key":"10.1016\/S1574-6526(06)80012-X_bib41","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1006\/jcss.2001.1809","article-title":"Hypertree decomposition and tractable queries","volume":"64","author":"Gottlob","year":"2002","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/S1574-6526(06)80012-X_bib42","series-title":"Proceedings 44th Annual IEEE Symposium on Foundations of Computer Science, (FOCS'03)","first-page":"552","article-title":"The complexity of homomorphism and constraint satisfaction problems seen from the other side","author":"Grohe","year":"2003"},{"issue":"1","key":"10.1016\/S1574-6526(06)80012-X_bib43","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","article-title":"Decomposing constraint satisfaction problems using database techniques","volume":"66","author":"Gyssens","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib44","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","article-title":"On the complexity of H-coloring","volume":"48","author":"Hell","year":"1990","journal-title":"Journal of Combinatorial Theory, Ser.B"},{"key":"10.1016\/S1574-6526(06)80012-X_bib45","article-title":"The Structure of Finite Algebras","volume":"volume 76","author":"Hobby","year":"1988"},{"key":"10.1016\/S1574-6526(06)80012-X_bib46","series-title":"A Shorter Model Theory","author":"Hodges","year":"1997"},{"key":"10.1016\/S1574-6526(06)80012-X_bib47","article-title":"Descriptive Complexity","author":"Immerman","year":"1998"},{"key":"10.1016\/S1574-6526(06)80012-X_bib48","series-title":"Proceedings 4th International Conference on Constraint Programming\u2014CP'98 (Pisa, October 1998)","first-page":"2","article-title":"Constructing constraints","volume":"volume 1520","author":"Jeavons","year":"1998"},{"key":"10.1016\/S1574-6526(06)80012-X_bib49","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","article-title":"On the algebraic structure of combinatorial problems","volume":"200","author":"Jeavons","year":"1998","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"10.1016\/S1574-6526(06)80012-X_bib50","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","article-title":"Constraints, consistency and closure","volume":"101","author":"Jeavons","year":"1998","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib51","series-title":"Proceedings 1st International Conference on Constraint Programming, CP'95","first-page":"276","article-title":"A unifying framework for tractable constraints","volume":"volume 976","author":"Jeavons","year":"1995"},{"key":"10.1016\/S1574-6526(06)80012-X_bib52","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","article-title":"Closure properties of constraints","volume":"44","author":"Jeavons","year":"1997","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80012-X_bib53","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1023\/A:1009890709297","article-title":"How to determine the expressive power of constraints","volume":"4","author":"Jeavons","year":"1999","journal-title":"Constraints"},{"issue":"2","key":"10.1016\/S1574-6526(06)80012-X_bib54","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","article-title":"Tractable constraints on ordered domains","volume":"79","author":"Jeavons","year":"1995","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib55","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0004-3702(98)00031-9","article-title":"A unifying approach to temporal constraint reasoning","volume":"102","author":"Jonsson","year":"1998","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib56","first-page":"191","article-title":"A polynomial time algorithm for linear programming","volume":"20","author":"Khachian","year":"1979","journal-title":"Soviet Math. Dokl."},{"issue":"6","key":"10.1016\/S1574-6526(06)80012-X_bib57","doi-asserted-by":"crossref","first-page":"1863","DOI":"10.1137\/S0097539799349948","article-title":"The approximability of constraint satisfaction problems","volume":"30","author":"Khanna","year":"2001","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1574-6526(06)80012-X_bib58","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0004-3702(93)90063-H","article-title":"Fast parallel constraint satisfaction","volume":"64","author":"Kirousis","year":"1993","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib59","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1006\/jcss.2000.1713","article-title":"Conjunctive-query containment and constraint satisfaction","volume":"61","author":"Kolaitis","year":"2000","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/S1574-6526(06)80012-X_bib60","series-title":"Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference (KR'92)","first-page":"24","article-title":"Dense time and temporal constraints with \u2260","author":"Koubarakis","year":"1992"},{"key":"10.1016\/S1574-6526(06)80012-X_bib61","series-title":"Proceedings 1st International Conference on Constraint Programming-CP'95 (Cassis, France, September 1995)","first-page":"53","article-title":"From local to global consistency in temporal constraint networks","volume":"volume 976","author":"Koubarakis","year":"1995"},{"key":"10.1016\/S1574-6526(06)80012-X_bib62","series-title":"Proceedings 2nd International Conference on Constraint Programming\u2014CP'96","first-page":"297","article-title":"Tractable disjunctions of linear constraints","volume":"volume 1118","author":"Koubarakis","year":"1996"},{"key":"10.1016\/S1574-6526(06)80012-X_bib63","series-title":"Proceedings 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL 2003)","first-page":"343","article-title":"Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey","author":"Krokhin","year":"2003"},{"key":"10.1016\/S1574-6526(06)80012-X_bib64","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1145\/876638.876639","article-title":"Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra","volume":"50","author":"Krokhin","year":"2003","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80012-X_bib65","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1137\/S0895480102410201","article-title":"Constraint satisfaction problems on intervals and lengths","volume":"17","author":"Krokhin","year":"2004","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"10.1016\/S1574-6526(06)80012-X_bib66","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/176584.176585","article-title":"On binary constraint problems","volume":"41","author":"Ladkin","year":"1994","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80012-X_bib67","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","article-title":"On the structure of polynomial time reducibility","volume":"22","author":"Ladner","year":"1975","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80012-X_bib68","series-title":"Constraint Logic Programming, Selected Research","first-page":"33","article-title":"A constraint sequent calculus","author":"Lassez","year":"1991"},{"key":"10.1016\/S1574-6526(06)80012-X_bib69","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0747-7171(92)90002-L","article-title":"A canonical form for generalized linear constraints","volume":"13","author":"Lassez","year":"1992","journal-title":"Journal of Symbolic Computation"},{"key":"10.1016\/S1574-6526(06)80012-X_bib70","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1023\/A:1009609327253","article-title":"Engineering dynamic scheduler for Work Manager","volume":"16","author":"Lesaint","year":"1998","journal-title":"BT Technology Journal"},{"key":"10.1016\/S1574-6526(06)80012-X_bib71","article-title":"A probabilistic approach to the dichotomy problem","author":"\u0141uczak","year":"2003"},{"key":"10.1016\/S1574-6526(06)80012-X_bib72","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","article-title":"Consistency in networks of relations","volume":"8","author":"Mackworth","year":"1977","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib73","first-page":"285","article-title":"Constraint satisfaction","volume":"volume 1","author":"Mackworth","year":"1992"},{"key":"10.1016\/S1574-6526(06)80012-X_bib74","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(93)90170-G","article-title":"The complexity of constraint satisfaction revisited","volume":"59","author":"Mackworth","year":"1993","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib75","volume":"volume I","author":"McKenzie","year":"1987"},{"key":"10.1016\/S1574-6526(06)80012-X_bib76","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","article-title":"Networks of constraints: Fundamental properties and applications to picture processing","volume":"7","author":"Montanari","year":"1974","journal-title":"Information Sciences"},{"key":"10.1016\/S1574-6526(06)80012-X_bib77","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/200836.200848","article-title":"Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra","volume":"42","author":"Nebel","year":"1995","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80012-X_bib78","series-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S1574-6526(06)80012-X_bib79","article-title":"A survey of tractable constraint satisfaction problems","author":"Pearson","year":"1997"},{"key":"10.1016\/S1574-6526(06)80012-X_bib80","series-title":"Theories of Computability","author":"Pippenger","year":"1997"},{"key":"10.1016\/S1574-6526(06)80012-X_bib81","series-title":"Funktionen- und Relationenalgebren","author":"P\u00f6schel","year":"1979"},{"key":"10.1016\/S1574-6526(06)80012-X_bib82","article-title":"The two-valued iterative systems of mathematical logic","volume":"volume 5","author":"Post","year":"1941"},{"key":"10.1016\/S1574-6526(06)80012-X_bib83","series-title":"Proceedings of 1st International Conference on The Practical Application of Constrain Technologies and Logic Programming \u2014 PACLP'99","first-page":"63","article-title":"Constraint tractability theory and its application to the product development process for a constraint-based scheduler","author":"Purvis","year":"1999"},{"key":"10.1016\/S1574-6526(06)80012-X_bib84","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0004-3702(99)00002-8","article-title":"On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus","volume":"108","author":"Renz","year":"1999","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib85","series-title":"Lectures in Universal Algebra (Proc. Conf. Szeged 1983)","first-page":"405","article-title":"Minimal clones I: the five types","volume":"volume 43","author":"Rosenberg","year":"1986"},{"key":"10.1016\/S1574-6526(06)80012-X_bib86","series-title":"Proceedings 10th ACM Symposium on Theory of Computing, STOC'78","first-page":"216","article-title":"The complexity of satisfiability problem","author":"Schaefer","year":"1978"},{"issue":"2\u20133","key":"10.1016\/S1574-6526(06)80012-X_bib87","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1023\/A:1009717525330","article-title":"Temporal constraints: a survey","volume":"3","author":"Schwalb","year":"1998","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80012-X_bib88","article-title":"Clones in Universal Algebra","volume":"volume 99","author":"Szendrei","year":"1986"},{"key":"10.1016\/S1574-6526(06)80012-X_bib89","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1145\/210346.210347","article-title":"On the minimality and decomposability of row-convex constraint networks","volume":"42","author":"van Beek","year":"1995","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80012-X_bib90","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/263867.263499","article-title":"Constraint tightness and looseness versus local and global consistency","volume":"44","author":"van Beek","year":"1997","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1574-6526(06)80012-X_bib91","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0004-3702(92)90020-X","article-title":"A generic arc-consistency algorithm and its specializations","volume":"57","author":"van Hentenryck","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80012-X_bib92","series-title":"Readings in Qualitative Reasoning about Physical Systems","first-page":"373","article-title":"Constraint propagation algorithms for temporal reasoning: A revised report","author":"Vilain","year":"1989"}],"container-title":["Foundations of Artificial Intelligence","Handbook of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S157465260680012X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S157465260680012X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T02:51:24Z","timestamp":1761619884000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S157465260680012X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9780444527264"],"references-count":92,"URL":"https:\/\/doi.org\/10.1016\/s1574-6526(06)80012-x","relation":{},"ISSN":["1574-6526"],"issn-type":[{"value":"1574-6526","type":"print"}],"subject":[],"published":{"date-parts":[[2006]]}}}