@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{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:mfcs,
  author = "Stanislav \vZ}ivn\'y and David A. Cohen and Peter G. Jeavons",
  booktitle = "Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS'09)",
  series = "Lecture Notes in Computer Science",
  title = "The expressive power of binary submodular functions",
  url = "http://zivny.cz/publications/zcj09mfcs-preprint.pdf",
  year = "2009",
}


    
      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{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",
}


    
      @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{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",
}


    
      @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{GeometricSNP,
  abstract = "A common type of DNA variation is called a Single Nucleotide Polymorphism (SNP), where a single position within a DNA sequence is altered from one nucleotide base to another. The problem of identifying disease-associated SNPs has been the subject of extensive research by statisticians. However, less research has been done within the computing community. In this paper, we propose a novel geometrical computing model for the SNP Motif Identification Problem. The purpose of our research is to explore the properties of SNPs in a combinatorial way. We test our algorithm on two real clinical datasets, and give computational results which demonstrate the efficiency and effectiveness of our approach.",
  author = "Gaofeng Huang and Peter Jeavons",
  booktitle = "Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE 2007",
  doi = "10.1109/BIBE.2007.4375593",
  isbn = "978-1-4244-1509-0 ",
  pages = "395-402",
  title = "A Geometrical Model for the SNP Motif Identification Problem",
  url = "http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4375593",
  year = "2007",
}


    
      @inproceedings{ExactHeuristicSNP,
  abstract = "A Single Nucleotide Polymorphism (SNP) is a small DNA variation which occurs naturally between different individuals of the same species. Some combinations of SNPs in the human genome are known to increase the risk of certain complex genetic diseases. This paper formulates the problem of identifying such disease-associated SNP motifs as a combinatorial optimization problem and shows it to be NP-hard. Both exact and heuristic approaches for this problem are developed and tested on simulated data and real clinical data. Computational results are given to demonstrate that these approaches are sufficiently effective to support ongoing biological research.",
  author = "Gaofeng Huang and Peter Jeavons and Dominic Kwiatkowski",
  booktitle = "Proceedings of 5th Asia-Pacific Bioinformatics Conference, APBC 2007",
  isbn = "978-1-86094-783-4",
  pages = "175-184",
  publisher = "Imperial College Press",
  series = "Advances in Bioinformatics and Computational Biology",
  title = "Exact and Heuristic Approaches for Identifying Disease-Associated SNP Motifs",
  volume = "5",
  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",
}


    
      @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",
}


    
      @article{EnhancingBindingSitePrediction,
  abstract = "A problem faced by many algorithms for finding transcription factor (TF) binding sites is the high number of false positive hits that result with the increased sensitivity of their prediction. A main contributing factor to this is the short and degenerate nature of these sites which results in a low signal-to-noise ratio. In order to counter this problem, one needs to look beyond the assumption that individual bases of a TF binding site act independently from each other when binding to a transcription factor. In this paper, we present a new method based on templates, designed to exploit the discriminatory features, nucleotide polymorphism, and structural homology present in TF binding sites for distinguishing them from nonbinding sites.",
  author = "S. Gunewardena, P. Jeavons, Z. Zhang",
  doi = "10.1089/cmb.2006.13.929",
  journal = "Journal of Computational Biology",
  number = "4",
  pages = "929-945",
  title = "Enhancing the prediction of transcription factor binding sites by incorporating structural properties and nucleotide covariations",
  url = "http://www.liebertonline.com/doi/abs/10.1089/cmb.2006.13.929",
  volume = "13",
  year = "2006",
}


    
      @article{OperonMycobacteriumBovis,
  abstract = "Mycobacterium bovis BCG and Mycobacterium tuberculosis possess a single arylamine N-acetyltransferase whose gene is predicted to occur within a six-gene operon. Deletion of the nat gene caused an extended lag phase in M. bovis BCG and a cell morphology associated with an altered pattern of cell wall mycolates. Analysis of cDNA from M. bovis BCG shows that during in vitro growth all the genes in the putative nat operon are expressed and the open reading frames are contiguous, supporting the existence of an operon. Two genes in the operon, Mb3599c and Mb3600c, are predicted to encode homologues of enzymes annotated as a 2,3-dihydroxybiphenyl 1,2-dioxygenase (bphC5) and a 2-hydroxy-6-oxo-6-phenylhexa-2,4-dienoate hydrolase (bphD2), respectively, in Rhodococcus RHA1. As predicted, M. bovis BCG cell lysates metabolized the BphC substrate 2,3-dihydroxybiphenyl (2,3-DHB) to 2-hydroxy-6-oxo-6-phenylhexa-2,4-dienoic acid (HOPDA), a BphD substrate, which was subsequently hydrolysed. Immunoprecipitation of the BphD homologue from these lysates led to an accumulation of HOPDA. M. bovis BCG growth on both solid and liquid media was inhibited with either 2,3-DHB or an inhibitor of BphC, 3-chlorocatechol (3-CC). In addition, incubation with 2,3-DHB affects the lipid composition of the cell wall resulting in a diminished level of mycolates and an altered cell morphology similar to the &#916;nat strain. We propose the enzymes encoded by the putative operon have a similar endogenous role to that of the NAT enzyme and are part of a pathway important for cell wall synthesis.",
  author = "M. Anderton, S. Bhakta, G. Besra, P. Jeavons, L. Eltis, E. Sim ",
  doi = "10.1111/j.1365-2958.2005.04945.x",
  journal = "Molecular Microbiology",
  number = "1",
  pages = "181-192",
  title = "Characterization of the putative operon containing arylamine N-acetyltransferase (nat) in Mycobacterium bovis BCG",
  url = "http://www.blackwell-synergy.com/doi/abs/10.1111/j.1365-2958.2005.04945.x",
  volume = "59",
  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",
}


    
      @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{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",
}


    
      @techreport{RR-05-03,
  abstract = "A Single Nucleotide Polymorphism (SNP) is a small DNA variation which occurs naturally between different individuals of the same species. Some combinations of SNPs in the human genome are known to increase the risk of certain complex genetic diseases. This paper formulates the problem of identifying such disease-associated SNP motifs as a combinatorial optimization problem and shows it to be mathcal-hard. Both exact and heuristic approaches for this problem are developed and tested on simulated data and real clinical data. Computational results indicate that our algorithms are efficient AI tools which can support ongoing biological research.",
  author = "Gaofeng Huang and Peter Jeavons and Dominic Kwiatkowski",
  institution = "Oxford University Computing Laboratory",
  month = "July",
  number = "RR-05-03",
  title = "Exact and Heuristic Approaches for Identifying Disease-Associated SNP Motifs",
  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",
}


    
      @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",
}


    
      @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",
}


    
      @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-24,
  abstract = "This is a two-part report. In the first part we introduce the reader to biological sequence alignment. We discus dynamic programming as is used in sequence alignment, first in the case of two sequences and later, how it is adopted for multiple sequence alignment. Several references are given to the different sequence alignment strategies reported in the literature used to enhance the standard dynamic programming algorithm for sequence alignment to suit biological sequences. A short discussion on how alignments are scored is given. Finally, some of the existing sequence alignment tools are described.<p>The second part of this report presents a critical analysis of information as it relates to biological sequence alignment. Information relating to the sequences being aligned form the basis on which any alignment is built. In its basic form this information might quantify how individual residues are scored when aligned with each other or how gaps are scored when introduced between two residues. Every biological sequence has if not explicit, at least some form of implicit information relating to its residues that form distinguishing markers along the sequence. There are many ways of extracting this information such as from databases of the relevant sequences, from the literature, prior processing etc. It is reasonable to assume that the more sequence information we use in an alignment, the more confidant we can be of the resulting alignment, and hence make better hypothesis of the unknown sequences. The aim of this part of the report is to build a framework on how to represent this information in such a way as to facilitate the dynamic and flexible incorporation of it to facilitate sequence alignments.</p>",
  author = "Sumedha Gunewardena and Peter Jeavons",
  institution = "Oxford University Computing Laboratory",
  month = "November",
  number = "RR-04-24",
  title = "Information categorisation in biological sequence alignments",
  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",
}


    
      @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",
}


    
      @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",
}


    
      @techreport{RR-03-21,
  abstract = "A problem faced by many algorithms for finding transcription factor binding sites is the high number of false positive hits that result with the increased sensitivity of their prediction. A main contributing factor to this is the short and degenerate nature of these sites which results in a low signal to noise ratio. In order to counter this problem one needs to look beyond the base independence assumption. We propose a model based on templates designed to capture not only the vertical consensus but also the correlation of individual bases with the other bases of the site.",
  author = "Sumedha Gunewardena and Peter Jeavons",
  institution = "Oxford University Computing Laboratory",
  month = "October",
  number = "RR-03-21",
  title = "Finding transcription factor binding sites in DNA Sequences: A template based approach",
  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{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{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{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{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",
}


    
      @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{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{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{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",
}


    
      @article{AgaroseGelImage,
  abstract = "Motivation: Automatic tools to speed up routine biological processes are very much sought after in bio-medical research. Much repetitive work in molecular biology, such as allele calling in genetic analysis, can be made semi-automatic or task specific automatic by using existing techniques from computer science and signal processing. Computerized analysis is reproducible and avoids various forms of human error. Semi-automatic techniques with an interactive check on the results speed up the analysis and reduce the error. Results: We have successfully implemented an image processing software package to automatically analyze agarose gel images of polymorphic DNA markers. We have obtained up to 90% accuracy for the classification of alleles in good quality images and up to 70% accuracy in average quality images. These results are obtained within a few seconds. Even after subsequent interactive checking to increase the accuracy of allele classification to 100%, the overall speed with which the data can be processed is greatly increased, compared to manual allele classification.",
  author = "P. S. Umesh Adiga, A. Bhomra, M. G. Turri, A. Nicod, S. R. Datta, Peter Jeavons, Richard Mott, Jonathan Flint",
  journal = "Bioinformatics",
  number = "11",
  pages = "1084-1089",
  title = "Automatic analysis of agarose gel images",
  url = "http://bioinformatics.oxfordjournals.org/cgi/content/abstract/17/11/1084",
  volume = "17",
  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",
}


    
      @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{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",
}


    
      @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",
}


    
      @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",
}


    
      @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",
}


    
      @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",
}


    
      @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",
}


    
      @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",
}


    
      @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",
}


    
      @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",
}


    
      @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{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",
}


    
      @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{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",
}


    
      @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{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",
}


    
      @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",
}


    
      @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",
}


    
      @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{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",
}


    
      @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{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",
}