@techreport{RR-09-07,
  abstract = "The general constraint satisfaction problem for variables with finite domains is known to be NP-complete, but many different conditions have been identified which are sufficient to ensure that classes of instances satisfying those conditions are tractable, that is, solvable in polynomial time. Results about tractability have generally been presented in theoretical terms, with little discussion of how these results impact on practical constraint-solving techniques. In this paper we investigate the performance of several standard constraint solvers on benchmark instances that are designed to satisfy various different conditions that ensure tractability. We show that in certain cases some existing solvers are able to automatically take advantage of the problem features which ensure tractability, and hence solve the corresponding instances very efficiently. However, we also show that in many cases the existing pre-processing techniques and solvers are unable to solve efficiently the families of instances of tractable problems that we generate. We therefore suggest that such families of instances may provide useful benchmarks for improving pre-processing and solving techniques.",
  author = "Justyna Petke and Peter Jeavons",
  institution = "OUCL",
  number = "RR-09-07",
  title = "Tractable Benchmarks For Constraint Programming",
  year = "2009",
}


    
      @article{ZJ09constraints,
  author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
  doi = "10.1007/s10601-009-9078-z",
  journal = "Constraints",
  title = "Classes of submodular constraints expressible by graph cuts",
  url = "http://zivny.cz/publications/zj09constraints-preprint.pdf",
  year = "2009",
}


    
      @article{Z09:ipl,
  author = "Stanislav \v{Z}ivn\'y",
  doi = "10.1016/j.ipl.2009.07.009",
  journal = "Information Processing Letters",
  number = "19",
  pages = "1131--1135",
  title = "Structural properties of oracle classes",
  url = "http://zivny.cz/publications/z09ipl-preprint.pdf",
  volume = "109",
  year = "2009",
}


    
      @article{Zivny09:dam,
  author = "Stanislav \v{Z}ivn\'y and David A. Cohen and Peter G. Jeavons",
  doi = "10.1016/j.dam.2009.07.001",
  journal = "Discrete Applied Mathematics",
  number = "15",
  pages = "3347--3358",
  title = "The expressive power of binary submodular functions",
  url = "http://zivny.cz/publications/zcj09dam-preprint.pdf",
  volume = "157",
  year = "2009",
}


    
      @inproceedings{Zivny09:models,
  author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
  booktitle = "Proceedings of the 15th International Conference on Principles and Practice of Contraint Programming (CP'09)",
  doi = "10.1007/978-3-642-04244-7_64",
  number = "5732",
  series = "Lecture Notes in Computer Science",
  title = "The complexity of valued constraint models",
  url = "http://zivny.cz/publications/zj09cp-preprint.pdf",
  year = "2009",
}


    
      @inproceedings{Zivny09:same,
  author = "Christopher Jefferson and Serdar Kadioglu and Karen E. Petrie and Meinolf Sellmann and Stanislav \v{Z}ivn\'y",
  booktitle = "Proceedings of the 15th International Conference on Principles and Practice of Contraint Programming (CP'09)",
  doi = "10.1007/978-3-642-04244-7_38",
  number = "5732",
  series = "Lecture Notes in Computer Science",
  title = "Same-relation constraints",
  url = "http://zivny.cz/publications/jkpsz09cp-preprint.pdf",
  year = "2009",
}


    
      @article{zz09ipl,
  abstract = "Valued constraint satisfaction problem (VCSP) is an optimisation framework originally coming from Artificial Intelligence and generalising the classical constraint satisfaction problem (CSP). The VCSP is powerful enough to describe many important classes of problems. In order to investigate the complexity and expressive power of valued constraints, a number of algebraic tools have been developed in the literature. In this note we present alternative proofs of some known results without using the algebraic approach, but by representing valued constraints explicitly by combinations of other valued constraints.",
  author = "Bruno Zanuttini and Stanislav \v{Z}ivn\'y",
  doi = "10.1016/j.ipl.2009.01.018",
  journal = "Information Processing Letters",
  number = "11",
  pages = "534--538",
  title = "A note on some collapse results of valued constraints",
  url = "http://zivny.cz/publications/zz09ipl-preprint.pdf",
  volume = "109",
  year = "2009",
}


    
      @article{Green08:domain,
  author = "Martin J. Green and David A. Cohen",
  doi = "10.1016/j.artint.2007.12.001",
  journal = "Artificial Intelligence",
  number = "8-9",
  pages = "1094-1118",
  title = "Domain permutation reduction for constraint satisfaction problems",
  volume = "172",
  year = "2008",
}


    
      Warning - the bibtex entry below may be invalid: 
Missing 'institution' field 
@techreport{zcj08arx,
  abstract = "It has previously been an open problem whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively. Our results have several corollaries. First, we characterise precisely which submodular functions of arity 4 can be expressed by binary submodular functions. Next, we identify a novel class of submodular functions of arbitrary arities which can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.",
  author = "Stanislav \v{Z}ivn\'y and David A. Cohen and Peter G. Jeavons",
  note = "arXiv:0811.1885 [cs.DM]",
  title = "The Expressive Power of Binary Submodular Functions",
  url = "http://arxiv.org/abs/0811.1885",
  year = "2008",
}


    
      @article{Zivny08:tcs,
  abstract = "In this paper we investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. We show that in some cases a large class of valued constraints, of all possible arities, can be expressed by using valued constraints of a fixed finite arity. We also show that some simple classes of valued constraints, including the set of all monotonic valued constraints with finite cost values, cannot be expressed by a subset of any fixed finite arity, and hence form an infinite hierarchy.",
  author = "David A. Cohen and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
  doi = "10.1016/j.tcs.2008.08.036",
  journal = "Theoretical Computer Science",
  number = "1",
  pages = "137--153",
  title = "The expressive power of valued constraints: Hierarchies and collapses",
  url = "http://zivny.cz/publications/cjz08tcs-preprint.pdf",
  volume = "409",
  year = "2008",
}


    
      @techreport{Zivny08:sub-tr,
  abstract = "Submodular functions occur in many combinatorial optimisation problems and a number of polynomial-time algorithms have been devised to minimise such functions. The time complexity of the fastest known general algorithm for submodular function minimisation (SFM) is O(n^6+n^5L), where n is the number of variables and L is the time required to evaluate the function. <br/> However, many important special cases of SFM can be solved much more efficiently, and with much simpler algorithms. For example, the (s,t)-Min-Cut problem is a special case of SFM which can be solved in cubic time. Moreover, any submodular function which can be expressed as a sum of binary submodular functions can be minimised by computing a minimal cut in a suitable graph. It has been known for some time that all ternary submodular functions are expressible in this way, by introducing additional variables. We have recently identified, for each k&gt;=4, a subclass of k-ary submodular functions which are also expressible in this way. <br/> It was previously an open question whether all submodular functions could be expressed as a sum of binary submodular functions over a larger set of variables: in this paper we show that they cannot. Moreover, we characterise precisely which 4-ary submodular functions can be expressed in this way. This result can also be seen as characterising which pseudo-Boolean functions of degree 4 can be expressed as projections of quadratic submodular functions. <br/> Our results provide a more efficient algorithm for certain discrete optimisation problems which can be formulated as valued constraint satisfaction problems (VCSP). We define a new maximal class of VCSP instances with submodular constraints which are expressible using binary submodular functions with a bounded number of additional variables. It follows that optimal solutions to such instances can be computed in O((n+k)^3) time, where n is the number of variables and k is the number of higher-order (non-binary) constraints, by a straightforward reduction to the (s,t)-Min-Cut problem.",
  address = "Oxford, UK",
  author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
  institution = "OUCL",
  month = "June",
  number = "RR-08-08",
  title = "Which submodular functions are expressible using binary submodular functions?",
  type = "Research Report",
  url = "http://zivny.cz/publications/zj08sub-tr.pdf",
  year = "2008",
}


    
      @article{TournamentTCS,
  abstract = "The submodular function minimization problem (SFM) is a fundamental problem in combinatorial optimization and several fully combinatorial polynomial-time algorithms have recently been discovered to solve this problem. The most general versions of these algorithms are able to minimize any submodular function whose domain is a set of tuples over any totally-ordered finite set and whose range includes both finite and infinite values. In this paper we demonstrate that this general form of SFM is just one example of a much larger class of tractable discrete optimization problems defined by valued constraints. These tractable problems are characterized by the fact that their valued constraints have an algebraic property which we call a tournament pair multimorphism. This larger tractable class also includes the problem of satisfying a set of Horn clauses (Horn-SAT), as well as various extensions of this problem to larger finite domains.",
  author = "David Cohen, Martin Cooper, Peter Jeavons",
  doi = "doi:10.1016/j.tcs.2008.03.015",
  journal = "Theoretical Computer Science",
  number = "1-3",
  pages = "36-51",
  publisher = "Elsevier",
  title = "Generalising submodularity and Horn clauses: tractable optimization problems defined by tournament pair multimorphisms",
  volume = "401",
  year = "2008",
}


    
      @inproceedings{Salamon2008:perfect,
  abstract = "By using recent results from graph theory, including the Strong Perfect Graph Theorem, we obtain a unifying framework for a number of tractable classes of constraint problems. These include problems with chordal microstructure; problems with chordal microstructure complement; problems with tree structure; and the ``all-different'' constraint. In each of these cases we show that the associated microstructure of the problem is a perfect graph, and hence they are all part of the same larger family of tractable problems.",
  author = "Andr{\'a}s Z. Salamon and Peter G. Jeavons",
  booktitle = "Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming, {CP} 2008, Sydney, Australia, 14--18 September",
  doi = "10.1007/978-3-540-85958-1_35",
  isbn = "978-3-540-85957-4",
  pages = "524-528",
  publisher = "Springer",
  series = "Lecture Notes in Computer Science",
  title = "Perfect Constraints Are Tractable",
  url = "http://www.gaon.net/andras/academic/sj-cp2008.pdf",
  volume = "5202",
  year = "2008",
}


    
      @inproceedings{Cooper2008:hybrid,
  abstract = "The constraint satisfaction problem (CSP) is a central generic problem in artificial intelligence. Considerable progress has been made in identifying properties which ensure tractability in such problems, such as the property of being tree-structured. In this paper we introduce the broken-triangle property, which allows us to define a hybrid tractable class for this problem which significantly generalizes the class of problems with tree structure. We show that the broken-triangle property is conservative (i.e., it is preserved under domain reduction and hence under arc consistency operations) and that there is a polynomial-time algorithm to determine an ordering of the variables for which the broken-triangle property holds (or to determine that no such ordering exists). We also present a non-conservative extension of the broken-triangle property which is also sufficient to ensure tractability and can be detected in polynomial time.",
  author = "Martin C. Cooper and Peter G. Jeavons and Andr{\'a}s Z. Salamon",
  booktitle = "{ECAI} 2008, Proceedings of the 18th European Conference on Artificial Intelligence, July 21--25, Patras, Greece",
  editor = "Malik Ghallab, Constantine D. Spyropoulos, Nikos Fakotakis, Nikos Avouris",
  isbn = "978-1-58603-891-5",
  issn = "0922-6389",
  note = "Best paper award.",
  pages = "530--534",
  publisher = "IOS Press",
  series = "Frontiers in Artificial Intelligence and Applications",
  title = "Hybrid tractable {CSP}s which generalize tree structure",
  url = "http://www.gaon.net/andras/academic/cjs-ecai2008.pdf",
  volume = "178",
  year = "2008",
}


    
      @inproceedings{Zivny08:cp,
  abstract = "Submodular constraints play an important role both in theory and practice of valued constraint satisfaction problems (VCSPs). It has previously been shown, using results from the theory of combinatorial optimisation, that instances of VCSPs with submodular constraints can be minimised in polynomial time. However, the general algorithm is of order O(n^6) and hence rather impractical. In this paper, by using results from the theory of pseudo-Boolean optimisation, we identify several broad classes of submodular constraints over a Boolean domain which are expressible using binary submodular constraints, and hence can be minimised in cubic time. We also discuss the question of whether all submodular constraints of bounded arity over a Boolean domain are expressible using only binary submodular constraints, and can therefore be minimised efficiently.",
  author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
  booktitle = "Proceedings of the 14th International Conference on Principles and Practice of Contraint Programming (CP'08)",
  doi = "10.1007/978-3-540-85958-1_8",
  pages = "112-127",
  series = "Lecture Notes in Computer Science",
  title = "Classes of submodular constraints expressible by graph cuts",
  url = "http://zivny.cz/publications/zj08cp-preprint.pdf",
  volume = "5202",
  year = "2008",
}


    
      @article{StructuralTractability,
  abstract = "In this paper we derive a generic form of structural decomposition for the constraint satisfaction problem, which we call a guarded decomposition. We show that many existing decomposition methods can be characterised in terms of finding guarded decompositions satisfying certain specified additional conditions. Using the guarded decomposition framework we are also able to define a new form of decomposition, which we call a spread-cut. We show that the discovery of width-k spread-cut decompositions is tractable for each k, and that spread-cut decompositions strongly generalise many existing decomposition methods. Finally we exhibit a family of hypergraphs Hn, for n=1,2,3..., where the minimum width of any hypertree decomposition of each Hn is 3n, but the width of the best spread-cut decomposition is only 2n+1.",
  author = "David Cohen and Peter Jeavons and Marc Gyssens",
  doi = "10.1016/j.jcss.2007.08.001",
  journal = "Journal of Computer and System Sciences",
  note = "Earlier, uncorrected, version appears in Proceedings of IJCAI'05, pp. 72--77: \url{http://www.ijcai.org/papers/0521.pdf}",
  pages = "721-743",
  title = "A unified theory of structural tractability for constraint satisfaction problems",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/JCSSspreadcut.pdf",
  volume = "74",
  year = "2008",
}


    
      @techreport{RR-07-08,
  abstract = "In this paper we investigate the use of a system of multivariate polynomials to represent the restrictions imposed by a collection of constraints. The advantage of using polynomials to represent constraints is that it allows many different forms of constraints to be treated in a uniform way. Systems of polynomials have been widely studied, and a number of general techniques have been developed, including algorithms that generate an equivalent system with certain desirable properties, called a Gr&ouml;bner Basis. General algorithms to compute a Gr&ouml;bner Basis have doubly exponential complexity, but we observe that for the systems we use to describe constraint problems over finite domains a Gr&ouml;bner Basis can be computed more efficiently than this. We also describe a family of algorithms, related to the calculation of Gr&ouml;bner Bases, that can be used on any system of polynomials to compute an equivalent system in polynomial time. We show that these modified algorithms can simulate the effect of the local-consistency algorithms used in constraint programming. Finally, we describe how these algorithms can be used in a similar way to local consistency techniques to solve certain broad classes of constraint problems in polynomial time.",
  author = "Chris Jefferson and Peter Jeavons and Martin J. Green and M.R.C. van Dongen",
  institution = "Oxford University Computing Laboratory",
  month = "October",
  number = "RR-07-08",
  title = "Representing and Solving Finite-Domain Constraint Problems Using Systems of Polynomials",
  year = "2007",
}


    
      @techreport{Zivny07:expressiveTR,
  abstract = "In this paper we investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. We show that in some cases a large class of valued constraints, of all possible arities, can be expressed by using valued constraints of a fixed finite arity. We also show that some simple classes of valued constraints, including the set of all monotonic valued constraints with finite cost values, cannot be expressed by a subset of any fixed finite arity, and hence form an infinite hierarchy.",
  address = "Oxford, UK",
  author = "David A. Cohen and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
  institution = "Computing Laboratory, University of Oxford",
  month = "April",
  number = "RR-07-03",
  title = "The expressive power of valued constraints: hierarchies and collapses",
  url = "http://web.comlab.ox.ac.uk/oucl/publications/tr/RR-07-03.html",
  year = "2007",
}


    
      @inproceedings{Zivny07:cp,
  abstract = "In this paper we investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. We show that in some cases a large class of valued constraints, of all possible arities, can be expressed by using valued constraints of a fixed finite arity. We also show that some simple classes of valued constraints, including the set of all monotonic valued constraints with finite cost values, cannot be expressed by a subset of any fixed finite arity, and hence form an infinite hierarchy.",
  author = "David A. Cohen and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
  booktitle = "Proceedings of the 13th International Conference on Principles and Practice of Contraint Programming (CP'07)",
  doi = "10.1007/978-3-540-74970-7_57",
  pages = "798-805",
  series = "Lecture Notes in Computer Science",
  title = "The expressive power of valued constraints: Hierarchies and collapses",
  url = "http://zivny.cz/publications/cjz07cp-preprint.pdf",
  volume = "4741",
  year = "2007",
}


    
      @inproceedings{Cohen06:guarded,
  author = "David A. Cohen and Martin J. Green",
  booktitle = "Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP'06)",
  doi = "10.1007/11889205_11",
  pages = "122-136",
  series = "Lecture Notes in Computer Science",
  title = "Typed Guarded Decompositions for Constraint Satisfaction",
  volume = "4204",
  year = "2006",
}


    
      @inproceedings{Houghton06:effect,
  author = "Chris Houghton and David A. Cohen and Martin J. Green",
  booktitle = "Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP'06)",
  doi = "10.1007/11889205_59",
  pages = "726-730",
  series = "Lecture Notes in Computer Science",
  title = "The Effect of Constraint Representation on Structural Tractability",
  volume = "4204",
  year = "2006",
}


    
      @article{SymmetryDefinitions,
  author = "David Cohen and Peter Jeavons and Christopher Jefferson and Karen Petrie and Barbara Smith",
  doi = "10.1007/s10601-006-8059-8",
  journal = "Constraints",
  note = "Received a Best Paper award.",
  pages = "115-137",
  title = "Symmetry definitions for constraint satisfaction problems",
  url = "http://ai.uwaterloo.ca/\%7Evanbeek/Constraints/Papers/CohenJJPS06.pdf",
  volume = "11",
  year = "2006",
}


    
      @techreport{RR-06-06,
  abstract = "<em>The submodular function minimization problem</em>&nbsp;(SFM) is a fundamental problem in combinatorial optimization and several fully combinatorial polynomial-time algorithms have recently been discovered to solve this problem. The most general versions of these algorithms are able to minimize any submodular function whose domain is a set of tuples over any totally-ordered finite set and whose range includes both finite and infinite values. In this paper we demonstrate that this general form of SFM is just one example of a much larger class of tractable discrete optimization problems defined by valued constraints. These tractable problems are characterized by the fact that their valued constraints have an algebraic property which we call a<em>tournament pair multimorphism.</em>&nbsp;This larger tractable class also includes the problem of satisfying a set of Horn clauses (Horn-SAT), as well as various extensions of this problem to larger finite domains.",
  author = "Peter Jeavons and Martin C Cooper and David A Cohen",
  institution = "Oxford University Computing Laboratory",
  month = "December",
  number = "RR-06-06",
  title = "Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms",
  year = "2006",
}


    
      @inproceedings{AlgebraicCharacterisation,
  author = "David Cohen and Martin Cooper and Peter Jeavons",
  booktitle = "Proceedings of the 12th International Conference on Principles and Practice of Contraint Programming (CP'06)",
  doi = "10.1007/11889205_10",
  pages = "107-121",
  series = "Lecture Notes in Computer Science",
  title = "An algebraic characterisation of complexity for valued constraints",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/CP06expressibility.pdf",
  volume = "4204",
  year = "2006",
}


    
      @inbook{ComplexityConstraintLanguages,
  author = "David Cohen and Peter Jeavons",
  booktitle = "Handbook of Constraint Programming",
  chapter = "8",
  publisher = "Elsevier",
  title = "The complexity of constraint languages",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/ComplexityLanguages.pdf",
  year = "2006",
}


    
      @article{ComplexityOfSoft,
  author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
  doi = "10.1016/j.artint.2006.04.002",
  journal = "Artificial Intelligence",
  pages = "983-1016",
  title = "The complexity of soft constraint satisfaction",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/AIJ-3418.pdf",
  volume = "170",
  year = "2006",
}


    
      @inproceedings{Houghton05:solution,
  author = "Chris Houghton and David A. Cohen",
  booktitle = "Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming (CP'05)",
  doi = "10.1007/11564751_89",
  pages = "851",
  series = "Lecture Notes in Computer Science",
  title = "Solution Equivalent Subquadrangle Reformulations of Constraint Satisfaction Problems",
  volume = "3709",
  year = "2005",
}


    
      @article{SupermodularFunctions,
  author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
  doi = "10.1016/j.dam.2005.03.003",
  journal = "Discrete Applied Mathematics ",
  note = "Earlier version appeared as Identifying efficiently solvable cases of Max CSP \url{http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/STACS04maxCSP.ps} in: Proceedings of STACS'04, Lecture Notes in Computer Science 2996 (2004)",
  pages = "53-72",
  title = "Supermodular functions and the complexity of MAX CSP",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/DAMsupermodular.pdf",
  volume = "149",
  year = "2005",
}


    
      @article{ClassifyingComplexity,
  author = "Andrei Bulatov and Peter Jeavons and Andrei Krokhin",
  doi = "10.1137/S0097539700376676",
  journal = "SIAM Journal on Computing",
  number = "34",
  pages = "720-742",
  title = "Classifying the complexity of constraints using finite algebras",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/SIAMclassifying.pdf",
  year = "2005",
}


    
      @inproceedings{Bulatov04:graph,
  author = "Andrei A. Bulatov",
  booktitle = "Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04)",
  pages = "448-45",
  title = "A Graph of a Relational Structure and Constraint Satisfaction Problems",
  url = "http://csdl.computer.org/comp/proceedings/lics/2004/2192/00/21920448abs.htm",
  year = "2004",
}


    
      @inproceedings{Bulatov04:partition,
  author = "Andrei A. Bulatov and Martin Grohe",
  booktitle = "Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04)",
  pages = "294-306",
  series = "Lecture Notes in Computer Science",
  title = "The complexity of partition functions",
  url = "http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3142{\&}spage=294",
  volume = "3142",
  year = "2004",
}


    
      @article{Cohen04:tractable,
  author = "David A. Cohen",
  journal = "Constraints",
  number = "3",
  pages = "219--229",
  title = "Tractable Decision for a Constraint Language Implies Tractable Search",
  url = "http://www.springerlink.com/content/v21231p3601625v4/",
  volume = "9",
  year = "2004",
}


    
      @techreport{RR-04-08,
  abstract = "Many computational problems arising in artificial intelligence, computer science and elsewhere can be represented as constraint satisfaction and optimization problems. In this survey paper we discuss an algebraic approach that has proved to be very successful in studying the complexity of constraint problems.",
  author = "Andrei Krokhin and Andrei Bulatov and Peter Jeavons",
  institution = "Oxford University Computing Laboratory",
  month = "May",
  number = "RR-04-08",
  title = "The Complexity of Constraint Satisfaction: An Algebraic Approach",
  year = "2004",
}


    
      @techreport{RR-04-01,
  abstract = "In this paper we study the complexity of the maximum constraint satisfaction problem (Max CSP) over an arbitrary finite domain. An instance of Max CSP consists of a set of variables and a collection of constraints which are applied to certain specified subsets of these variables; the goal is to find values for the variables which maximize the number of simultaneously satisfied constraints. We describe for the first time a general approach to the question of classifying the complexity of Max CSP for different types of constraints. This approach is based on establishing a novel connection with the theory of sub- and supermodular functions on finite lattice-ordered sets. Using this connection, we are able to identify large classes of efficiently solvable subproblems of Max CSP arising from certain restrictions on the constraint types. All previously known complexity classification results for Max CSP were restricted to constraints over a 2-valued (Boolean) domain. Here we show that these previous results can be restated using supermodularity, and from this we obtain the first examples of general families of efficiently solvable cases of Max CSP for arbitrary finite domains. In addition, we provide the first dichotomy result for a special class of non-Boolean Max CSP, by considering binary constraints given by supermodular functions on a totally ordered set. Finally, we show that the equality constraint over a non-Boolean domain is non-supermodular, and, when combined with some simple unary constraints, gives rise to cases of Max CSP which are hard even to approximate.",
  author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
  institution = "Oxford University Computing Laboratory",
  month = "January",
  number = "RR-04-01",
  title = "Supermodular Functions and the Complexity of MAX CSP",
  year = "2004",
}


    
      @inproceedings{CompleteCharacterization,
  author = "David Cohen, Martin Cooper and Peter Jeavons",
  booktitle = "Proceedings of CP'04",
  number = "3258",
  pages = "212--226",
  series = "Lecture Notes in Computer Science",
  title = "A complete characterization of complexity for Boolean constraint optimization problems",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/CP04vsatdichotomy.ps",
  year = "2004",
}


    
      @article{ImplementingTest,
  author = "Richard Gault and Peter Jeavons",
  journal = "Constraints",
  pages = "139--160",
  title = "Implementing a test for tractability",
  url = "http://www.kluweronline.com/article.asp?PIPS=5268458",
  volume = "9",
  year = "2004",
}


    
      @article{MaximalTractable,
  author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
  journal = "Journal of Artificial Intelligence Research",
  note = "Earlier version appeared in: Proceedings of IJCAI'03, pp. 209-214: \url{http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/IJCAI03submodular.pdf}",
  number = "22",
  pages = "01/01/22",
  title = "A maximal tractable class of soft constraints",
  url = "http://www.jair.org/papers/paper1400.html",
  year = "2004",
}


    
      @article{ConstraintSatisfaction,
  author = "Andrei Krokhin and Peter Jeavons and Peter Jonsson",
  journal = "SIAM Journal on Discrete Mathematics",
  note = "Earlier version appears in Proceedings of STACS'02, Lecture Notes in Computer Science, 2285, (2002), pp. 443--454: \url{http://link.springer.de/link/service/series/0558/bibs/2285/22850443.htm} Preprint version available from Electronic Colloquium on Computational Complexity, as Report TR01-077: \url{ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2001/TR01-077/index.html}",
  number = "17",
  pages = "453--477",
  title = "Constraint satisfaction problems on intervals and lengths",
  url = "http://epubs.siam.org/sam-bin/dbq/article/41020",
  year = "2004",
}


    
      @inproceedings{Bulatov03:conservative,
  author = "Andrei A. Bulatov",
  booktitle = "Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS'03)",
  title = "Tractable conservative Constraint Satisfaction Problems",
  url = "http://csdl.computer.org/comp/proceedings/lics/2003/1884/00/18840321abs.htm",
  year = "2003",
}


    
      @inproceedings{Bulatov03:ijcai,
  author = "Andrei A. Bulatov and Evgeny S. Skvortsov",
  booktitle = "Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03)",
  pages = "197-202",
  title = "Amalgams of Constraint Satisfaction Problem",
  year = "2003",
}


    
      @inproceedings{Green03:tractability,
  author = "Martin J. Green and David A. Cohen",
  booktitle = "Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming (CP'03)",
  series = "Lecture Notes in Computer Science",
  title = "Tractability by Approximating Constraint Languages",
  url = "http://www.springerlink.com/content/ewc4fxag1bupg9wh/",
  volume = "2833",
  year = "2003",
}


    
      @inproceedings{Cohen03:new,
  author = "David A. Cohen",
  booktitle = "Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming (CP'03)",
  pages = "807-811",
  series = "Lecture Notes in Computer Science",
  title = "A New Classs of Binary CSPs for which Arc-Constistency Is a Decision Procedure",
  url = "http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=2833{\&}spage=807",
  volume = "2833",
  year = "2003",
}


    
      @inproceedings{Bulatov03:trichotomy,
  author = "Andrei A. Bulatov and Victor Dalmau",
  booktitle = "Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS'03)",
  title = "Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem",
  url = "http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400562abs.htm",
  year = "2003",
}


    
      @article{Learnability,
  author = "Victor Dalmau and Peter Jeavons",
  journal = "Theoretical Computer Science",
  note = "Earlier version appeared in Proceedings of EuroCOLT 99, Nordkirchen, Germany, (1999), pp. 63-78 : \url{http://link.springer.de/link/service/series/0558/bibs/1572/15720063.htm}",
  number = "306",
  pages = "485--511",
  title = "Learnability of quantified formulas",
  url = "http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V1G-48WPV2S-1&amp;_coverDate=09\%2F05\%2F2003&amp;_alid=143417703&amp;_rdoc=1&amp;_fmt=&amp;_orig=search&amp;_qd=1&amp;_cdi=5674&amp;_sort=d&amp;view=c&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=ed1f9936cab222df6e92ce0b37aa9f4b",
  year = "2003",
}


    
      Warning - the bibtex entry below may be invalid: 
Missing 'booktitle' field 
@inproceedings{NewTractableClasses,
  author = "David Cohen and Peter Jeavons and Richard Gault",
  doi = "10.1023/A:1025623111033",
  journal = "Constraints",
  note = "Earlier version appears in Proceedings of CP2000, Lecture Notes In Computer Science, 1894, 2000, pp. 160--171 : \url{http://link.springer.de/link/service/series/0558/bibs/1894/18940160.htm}",
  number = "8",
  pages = "263--282",
  title = "New Tractable Classes From Old",
  year = "2003",
}


    
      @inproceedings{ComplexityConstraintSatisfaction,
  address = "University of Montreal",
  author = "Andrei Krokhin and Andrei Bulatov and Peter Jeavons",
  booktitle = "Proceedings of SMS-NATO ASI",
  note = "Earlier version available as an OUCL Research Report: \url{http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-04-08.html}",
  pages = "181-213",
  title = "Structural Theory of Automata, Semigroups, and Universal Algebra",
  url = "http://www.springer.com/sgw/cda/frontpage/0,11855,4-10043-22-52121384-0,00.html",
  year = "2003",
}


    
      @inproceedings{SoftConstraints,
  author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
  booktitle = "Proceedings of CP'03",
  number = "2833",
  pages = "244--258",
  series = "Lecture Notes in Computer Science",
  title = "Soft constraints: complexity and multimorphsims",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/CP03multimorphisms.pdf",
  year = "2003",
}


    
      @inproceedings{QuantifiedConstraints,
  author = "Ferdinand B{\"o}rner and Andrei Bulatov and Peter Jeavons and Andrei Krokhin",
  booktitle = "Proceedings of CSL'03",
  doi = "10.1007/b13224",
  note = "Longer version available as an OUCL Research Report: \url{http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-02-11.html}",
  number = "2803",
  pages = "58--70",
  series = "Lecture Notes in Computer Science",
  title = "Quantified constraints: algorithms and complexity",
  url = "http://springerlink.metapress.com/content/2gmm51wv6xjx1u3e/fulltext.pdf",
  year = "2003",
}


    
      @inproceedings{FunctionsOf,
  author = "Andrei Krokhin and Andrei Bulatov and Peter Jeavons",
  booktitle = "Proceedings of 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL'03)",
  pages = "343--351",
  title = "Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/ISMVL03survey.ps",
  year = "2003",
}


    
      @inproceedings{AlgebraicApproach,
  author = "Andrei Bulatov and Peter Jeavons",
  booktitle = "Proceedings of CP'03",
  note = "Earlier version available as an OUCL Research Report : \url{http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-01-18.html}",
  number = "2833",
  pages = "183--198",
  series = "Lecture Notes in Computer Science",
  title = "An algebraic approach to multi-sorted constraints",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/CP03multisorted.pdf",
  year = "2003",
}


    
      @article{ReasoningTemporalRelations,
  author = "Andrei Krokhin and Peter Jeavons and Peter Jonsson",
  doi = "10.1145/876639",
  journal = "Journal of the ACM",
  note = "Earlier version available as an OUCL Research Report : \url{http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-01-12.html}",
  number = "50",
  pages = "591--640",
  title = "Reasoning about temporal relations : the tractable subalgebras of Allen's interval algebra",
  year = "2003",
}


    
      @inproceedings{Bulatov02:3-element,
  author = "Andrei A. Bulatov",
  booktitle = "Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS'02)",
  title = "A Dichotomy Theorem for Constraints on a Three-Element Set",
  url = "http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181990",
  year = "2002",
}


    
      @inproceedings{FiniteSemigroups,
  author = "Andrei Bulatov and Peter Jeavons and Mikhail Volkov",
  booktitle = "Proceedings of the School on Algorithmic Aspects of the Theory of Semigroups and its Applications, Coimbra, Portugal, 2001",
  pages = "313--329",
  publisher = "World Scientific, Singapore",
  title = "Finite semigroups imposing tractable constraints",
  year = "2002",
}


    
      @inproceedings{ComplexityMaximal,
  author = "Andrei Bulatov and Andrei Krokhin and Peter Jeavons",
  booktitle = "Proceedings of STOC'01, Crete, Greece",
  doi = "10.1145/380752.380868",
  note = "Earlier version available as an OUCL Research Report : \url{http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-01-03.html}",
  pages = "667--674",
  title = "The complexity of maximal constraint languages",
  year = "2001",
}


    
      @techreport{AlgebraicStructures,
  author = "Andrei Bulatov and Peter Jeavons",
  institution = "Technische Universitat Dresden",
  number = "MATH-AL-4-2001",
  pages = "32",
  title = "Algebraic structures in combinatorial problems",
  url = "http://www.cs.sfu.ca/~abulatov/papers/varieties.ps",
  year = "2001",
}


    
      @inproceedings{CompleteClassification,
  author = "Andrei Krokhin and Peter Jeavons and Peter Jonsson",
  booktitle = "Proceedings of IJCAI'01, Seattle, USA",
  note = "Longer version available as an OUCL Research Report : \url{http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-01-02.html}",
  pages = "83--88",
  title = "A complete classification of complexity in Allen's algebra in the presence of a non-trivial basic relation",
  year = "2001",
}


    
      @article{BuildingTractable,
  author = "David Cohen and Peter Jeavons and Peter Jonsson and Manolis Koubarakis",
  doi = "http://doi.acm.org/10.1145/355483.355485",
  journal = "Journal of the ACM",
  number = "47",
  pages = "826--853",
  title = "Building tractable disjunctive constraints",
  url = "http://portal.acm.org/citation.cfm?id=355483.355485",
  year = "2000",
}


    
      @techreport{TractableConstraints,
  author = "Andrei Bulatov and Peter Jeavons",
  institution = "Oxford University Computing Laboratory",
  number = "PRG-TR-12-00",
  pages = "27",
  title = "Tractable constraints closed under a binary operation",
  url = "http://web.comlab.ox.ac.uk/oucl/publications/tr/tr-12-00.html",
  year = "2000",
}


    
      @inproceedings{ConstraintSatisfactionProblems,
  author = "Andrei Bulatov and Andrei Krokhin, and Peter Jeavons",
  booktitle = "Proceedings of ICALP'00",
  doi = "10.1007/3-540-45022-X_24",
  note = "Longer version available as an OUCL Technical Report : \url{http://web.comlab.ox.ac.uk/oucl/publications/tr/tr-4-99.html}",
  number = "1853",
  pages = "272--282",
  series = "Lecture Notes in Computer Science",
  title = "Constraint satisfaction problems and finite algebras",
  url = "http://link.springer.de/link/service/series/0558/bibs/1853/18530272.htm",
  year = "2000",
}


    
      @inproceedings{HowToDetermine,
  author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
  booktitle = "Constraints",
  number = "4",
  pages = "113--131",
  title = "How to determine the expressive power of constraints",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/how_to_determine.ps",
  year = "1999",
}


    
      @inproceedings{ConstraintTractability,
  author = "Lisa Purvis and Peter Jeavons",
  booktitle = "Proceedings of the 1st International Conference on The Practical Application of Constraint Technologies and Logic Programming",
  note = "This paper was awarded First Prize in the Constraints Technologies area of PACLP'99",
  pages = "63--79",
  title = "Constraint Tractability Theory And Its Application to the Product Development Process for a Constraint-Based Scheduler",
  url = "http://home.rochester.rr.com/thepurvises/PACLPFinal.doc",
  year = "1999",
}


    
      @article{OnTheAlgebraicStructure,
  author = "P.G.Jeavons",
  journal = "Theoretical Computer Science",
  number = "200",
  pages = "185--204",
  title = "On The Algebraic Structure Of Combinatorial Problems",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/algebraic.ps",
  year = "1998",
}


    
      @article{ConstraintsConsistencyClosure,
  author = "P.G.Jeavons and D.A.Cohen and M.Cooper",
  journal = "Artificial Intelligence",
  number = "101 (1-2)",
  pages = "251--265",
  title = "Constraints, Consistency and Closure",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/conconclo.ps",
  year = "1998",
}


    
      @article{ConstraintsAndUniversalAlgebra,
  author = "P.G.Jeavons and D.A.Cohen and J.K.Pearson",
  journal = "Annals of Mathematics and Artificial Intelligence",
  number = "24",
  pages = "51--67",
  title = "Constraints and Universal Algebra",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/con_and_universal.ps",
  year = "1998",
}


    
      @inproceedings{WhyHigher,
  author = "P.G.Jeavons and N.W.Dunkin and J.E.Bater",
  booktitle = "ECAI'98 Workshop on Non-binary constraints",
  title = "Why higher order constraints are necessary to model frequency assignment problems",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/ecaiversion.ps",
  year = "1998",
}


    
      @techreport{TowardsHighOrder,
  author = "N.W.Dunkin and J.E.Bater and P.G.Jeavons and D.A.Cohen",
  institution = "Royal Holloway, University of London",
  month = "June",
  number = "CSD-TR-98-05",
  title = "Towards High Order Constraint Representations for the Frequency Assignment Problem",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/CSD-TR-98-05.ps",
  year = "1998",
}


    
      @inproceedings{ConstructingConstraints,
  abstract = "It is well-known that there is a trade-off between the expressive power of a constraint language and the tractability of the problems it can express. But how can you determine the expressive power of a given constraint language, and how can you tell if problems expressed in that language are tractable? In this paper we discuss some general approaches to these questions We show that for languages over a finite domain the concept of an �indicator Problem� gives a universal construction for any constraint within the expressive power of a language. We also discuss the fact that all known tractable languages over finite domains are characterised by the presence of a particular solution to a corresponding indicator problem, and raise the question of whether this is a universal property of tractable languages",
  author = "P.G.Jeavons",
  booktitle = "Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP98)",
  doi = "10.1007/3-540-49481-2_2",
  pages = "2-16",
  series = "Lecture Notes in Computer Science",
  title = "Constructing constraints",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/constructing.ps",
  volume = "1520",
  year = "1998",
}


    
      @techreport{AreThere,
  author = "J.E.Bater and P.G.Jeavons and D.A.Cohen",
  institution = "Royal Holloway, University of London",
  month = "February",
  number = "CSD-TR-98-01",
  title = "Are there optimal reuse distance constraints for FAPs with random Tx placements?",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/CSD-TR-98-01.ps",
  year = "1998",
}


    
      @article{ClosreProperties,
  author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
  journal = "Journal of the ACM",
  number = "44",
  pages = "527--548",
  title = "Closure Properties of Constraints",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/closure.ps",
  year = "1997",
}


    
      @inproceedings{TractableDisjunctive,
  author = "D.A.Cohen and P.G.Jeavons and M.Kourabarakis",
  booktitle = "Proceedings 3rd International Conference on Principles and Practice of Constraint Programming (CP97)",
  doi = "10.1007/BFb0017461",
  number = "1330",
  pages = "478--490",
  series = "Lecture Notes in Computer Science",
  title = "Tractable Disjunctive Constraints",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/tractable.ps",
  volume = "1330",
  year = "1997",
}


    
      @inproceedings{Expressiveness,
  author = "N.W.Dunkin and P.G.Jeavons",
  booktitle = "DIAL-M Workshop, 3rd Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM'97)",
  title = "Expressiveness of Binary Constraints for the Frequency Assignment Problem",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/dunk97.ps",
  year = "1997",
}


    
      @techreport{SurveyTractable,
  author = "J.K.Pearson and P.G.Jeavons",
  institution = "Royal Holloway, University of London",
  month = "July",
  number = "CSD-TR-97-15",
  title = "A Survey of Tractable Constraint Satisfaction Problems",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/survey.ps",
  year = "1997",
}


    
      @inproceedings{DerivationOfConstraint,
  author = "D.A.Cohen and M.Gyssens and P.G.Jeavons",
  booktitle = "Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP96)",
  doi = "10.1007/3-540-61551-2_71",
  pages = "134--148",
  series = "Lecture Notes in Computer Science",
  title = "Derivation of Constraints and Database Relations",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/derivation.ps",
  volume = "1118",
  year = "1996",
}


    
      @inproceedings{TestForTractability,
  author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
  booktitle = "Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP96)",
  doi = "10.1007/3-540-61551-2_80",
  pages = "267-281",
  series = "Lecture Notes in Computer Science",
  title = "A Test for Tractability",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/tractability.ps",
  volume = "1118",
  year = "1996",
}


    
      @article{TractableConstraintsOrdered,
  author = "P.G.Jeavons and M.C.Cooper",
  journal = "Artificial Intelligence",
  number = "79(2)",
  pages = "327--339",
  title = "Tractable Constraints on Ordered Domains",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/maxclos.ps",
  year = "1995",
}


    
      @inproceedings{UnifyingFramework,
  author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
  booktitle = "Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP95)",
  doi = "10.1007/3-540-60299-2_17",
  pages = "276-291",
  series = "Lecture Notes in Computer Science",
  title = "A Unifying Framework for Tractable Constraints",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/unifying.ps",
  volume = "976",
  year = "1995",
}


    
      @inproceedings{SubstitutionOperation,
  author = "P.G.Jeavons and D.A.Cohen and M.C.Cooper",
  booktitle = "Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP95)",
  doi = "10.1007/3-540-58601-6_85",
  pages = "161-177",
  series = "Lecture Notes in Computer Science",
  title = "A Substitution Operation for Constraints",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/substitution.ps",
  volume = "874",
  year = "1995",
}


    
      @article{RecoveringRelation,
  author = "P.G.Jeavons",
  journal = "Information Sciences",
  number = "78",
  pages = "229--256",
  title = "Recovering a Relation from a Decomposition using Constraint Satisfaction Techniques",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/recovering.ps",
  year = "1994",
}


    
      @article{StructuralDecomposition,
  author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
  journal = "Contemporary Mathematics",
  number = "178",
  pages = "161--177",
  title = "A Structural Decomposition for Hypergraphs",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/contmath.ps",
  year = "1994",
}


    
      @article{DecomposingConstraint,
  author = "M.Gyssens and P.G.Jeavons and D.A.Cohen",
  journal = "Artificial Intelligence",
  number = "66(1)",
  pages = "57-89",
  title = "Decomposing Constraint Satisfaction Problems Using Database Techniques",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/decomposing.ps",
  year = "1994",
}


    
      @article{CharacterisingTractable,
  author = "M.C.Cooper and D.A.Cohen and P.G.Jeavons",
  journal = "Artificial Intelligence",
  number = "65(2)",
  pages = "347--361",
  title = "Characterising Tractable Constraints",
  url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/characterising.ps",
  year = "1994",
}