Peter Jeavons : Publications
Click here to download all publications in a single bibtex file
@inproceedings{10932,
title = "Minimal Weighted Clones with Boolean Support",
author = "Peter G. Jeavons and Andrius Vaicenavičius and Stanislav Živný",
year = "2016",
booktitle = "Proceedings of the 46th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2016, Sapporo, Japan, May 18-20, 2016",
editor = "Takahiro Hanyu",
month = "May",
pages = "90--95",
publisher = "IEEE Computer Society",
url = "https://doi.org/10.1109/ISMVL.2016.10",
}
@article{steering2015,
title = "Steering Evolution with Sequential Therapy to Prevent the Emergence of Bacterial Antibiotic Resistance",
author = "Daniel Nichol and Peter Jeavons and Alexander G. Fletcher and Robert A. Bonomo and Philip K. Maini and Jerome L. Paul and Robert A. Gatenby and Alexander R.A. Anderson and Jacob G. Scott",
year = "2015",
journal = "PLoS Computational Biology",
doi = "10.1371/journal.pcbi.1004493",
}
@article{leader2015,
title = "Simple Algorithms for Distributed Leader Election in Anonymous Synchronous Rings and Complete Networks Inspired by Neural Development in Fruit Flies",
author = "Lei Xu and Peter Jeavons",
year = "2015",
journal = "International Journal of Neural Systems",
url = "http://www.worldscientific.com/doi/abs/10.1142/S0129065715500252?journalCode=ijns",
doi = "10.1142/S0129065715500252",
}
@article{patterns2015,
title = "Patterns from nature: Distributed greedy colouring with simple messages and minimal graph knowledge",
author = "Lei Xu and Peter Jeavons",
year = "2015",
journal = "Information Sciences",
pages = "550-566",
publisher = "Elsevier",
url = "http://www.sciencedirect.com/science/article/pii/S002002551400663X",
volume = "316",
doi = "doi:10.1016/j.ins.2014.06.035",
}
@inproceedings{ccjz15:ijcai,
title = "Tractable Classes of Binary {C}{S}{P}s Defined by Excluded Topological Minors",
author = "David A. Cohen and Martin C. Cooper and Peter Jeavons and Stanislav \v{Z}ivn\'y",
year = "2015",
booktitle = "Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15)",
pages = "1945--1951",
publisher = "AAAI Press",
url = "http://ijcai.org/papers15/Papers/IJCAI15-276.pdf",
}
@inproceedings{ccjz15:aaai,
title = "Binarisation via dualisation for valued constraints",
author = "David A. Cohen and Martin C. Cooper and Peter Jeavons and Stanislav \v{Z}ivn\'y",
year = "2015",
booktitle = "Proceedings of the Twenty-Ninth {AAAI} Conference on Artificial Intelligence",
pages = "3731--3737",
publisher = "AAAI Press",
url = "http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9328/9699",
}
@inproceedings{cp2015:groebnerabstract,
title = "Representing and Solving Finite-Domain Constraint Problems using Systems of Polynomials (Extended Abstract)",
author = "Chris Jefferson and Peter Jeavons and Martin J. Green and M.R.C. van Dongen",
year = "2015",
booktitle = "Principles and Practice of Constraint Programming - Proceedings of CP2015",
url = "http://www.cs.ox.ac.uk/peter.jeavons/CP2015:groebnerabstract.pdf",
}
@article{jkz14:survey,
title = "The complexity of valued constraint satisfaction",
author = "Peter Jeavons and Andrei Krokhin and Stanislav \v{Z}ivn\'y",
year = "2014",
journal = "Bulletin of the European Association for Theoretical Computer Science (EATCS)",
note = "Errata can be found <a href="http://community.dur.ac.uk/andrei.krokhin/papers/BEATCScolumnerrata.txt">here</a>.",
pages = "21-55",
url = "http://eatcs.org/beatcs/index.php/beatcs/article/view/266/249",
volume = "113",
}
@article{cccjz13:sicomp,
title = "An algebraic theory of complexity for discrete optimisation",
author = "David A. Cohen and Martin C. Cooper and P\'aid\'i Creed and Peter Jeavons and Stanislav \v{Z}ivn\'y",
year = "2013",
journal = "SIAM Journal on Computing",
number = "5",
pages = "1915-1939",
url = "http://zivny.cz/publications/cccjz13sicomp-preprint.pdf",
volume = "42",
doi = "10.1137/130906398",
}
@article{DBLP:journals/neco/0002J13,
title = "Simple Neural-Like P Systems for Maximal Independent Set Selection",
author = "Lei Xu and Peter G. Jeavons",
year = "2013",
journal = "Neural Computation",
number = "6",
pages = "1642-1659",
url = "http://dx.doi.org/10.1162/NECO_a_00443",
volume = "25",
doi = "10.1162/NECO_a_00443",
}
@article{DBLP:journals/amai/JeffersonJGD13,
title = "Representing and solving finite-domain constraint problems using systems of polynomials",
author = "Christopher Jefferson and Peter Jeavons and Martin J. Green and Marc R. C. van Dongen",
year = "2013",
journal = "Annals of Mathematics and Artificial Intelligence",
number = "3-4",
pages = "359-382",
url = "http://dx.doi.org/10.1007/s10472-013-9365-7",
volume = "67",
doi = "10.1007/s10472-013-9365-7",
}
@inproceedings{DBLP:conf/cp/CohenJTZ13,
title = "Tractable Combinations of Global Constraints",
author = "David A. Cohen and Peter G. Jeavons and Evgenij Thorstensen and Stanislav \v{Z}ivn\'{y}",
year = "2013",
booktitle = "Principles and Practice of Constraint Programming - 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings",
editor = "Christian Schulte",
pages = "230-246",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/cjtz13cp-preprint.pdf",
volume = "8124",
doi = "10.1007/978-3-642-40627-0_20",
}
@inproceedings{DBLP:conf/podc/ScottJ013,
title = "Feedback from nature: an optimal distributed algorithm for maximal independent set selection",
author = "Alex Scott and Peter Jeavons and Lei Xu",
year = "2013",
booktitle = "ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22-24, 2013",
editor = "Panagiota Fatourou and Gadi Taubenfeld",
pages = "147-156",
doi = "10.1145/2484239.2484247",
}
@inbook{jz12,
title = "Tractable valued constraints",
author = "Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
year = "2012",
booktitle = "Tractability: Practical Approaches to Hard Problems",
editor = "Lucas Bordeaux and Youssef Hamadi and Pushmeet Kohli and Robert Mateescu",
note = "This work is in copyright. The draft is for personal use only. No further distribution without permission.",
publisher = "Cambridge University Press",
url = "http://zivny.cz/publications/jz12cup-draft.pdf",
}
@article{DBLP:journals/jair/JeavonsP12,
title = "Local Consistency and SAT-Solvers",
author = "Peter Jeavons and Justyna Petke",
year = "2012",
journal = "Journal of Artificial Intelligence Research (JAIR)",
pages = "329-351",
url = "http://dx.doi.org/10.1613/jair.3531",
volume = "43",
doi = "10.1613/jair.3531",
}
@inproceedings{ccjz11:mfcs,
title = "An algebraic theory of complexity for valued constraints: Establishing a Galois connection",
author = "David A. Cohen and P\'aid\'i Creed and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
year = "2011",
booktitle = "Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS'11)",
pages = "231--242",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/ccjz11mfcs-preprint.pdf",
volume = "6907",
doi = "10.1007/978-3-642-22993-0_23",
}
@inproceedings{PUPIJCAI2011,
title = "Tackling the Partner Units Configuration Problem",
author = "Markus Aschinger and Conrad Drescher and Georg Gottlob and Peter Jeavons and Evgenij Thorstensen",
year = "2011",
address = "Barcelona, Spain",
booktitle = "Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011)",
}
@inproceedings{PUPCPAIOR2011,
title = "Optimization Methods for the Partner Units Problem",
author = "Markus Aschinger and Conrad Drescher and Gerhard Friedrich and Georg Gottlob and Peter Jeavons and Anna Ryabokon and Evgenij Thorstensen",
year = "2011",
address = "Berlin, Germany",
booktitle = "Proceedings of the 8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2011)",
series = "Lecture Notes in Computer Science",
}
@techreport{RR-11-04,
title = "The order encoding: from tractable CSP to tractable SAT",
author = "Justyna Petke and Peter Jeavons",
year = "2011",
institution = "DCS, University of Oxford",
number = "RR-11-04",
pages = "19",
}
@misc{SDSTACS11,
title = "Structural Decomposition Methods, and What They are Good For",
author = "Markus Aschinger and Conrad Drescher and Georg Gottlob and Peter Jeavons and Evgenij Thorstensen",
year = "2011",
address = "Dortmund, Germany",
booktitle = "Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)",
note = "Invited Paper at STACS 2011",
}
@techreport{3925,
title = "An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection",
author = "David A. Cohen and Paidi Creed and Peter G. Jeavons and Stanislav Zivny",
year = "2010",
institution = "OUCL",
month = "November",
number = "RR-10-16",
pages = "30",
}
@article{DBLP:journals/ai/CooperJS10,
title = "Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination",
author = "Martin C. Cooper and Peter G. Jeavons and Andr{\'a}s Z. Salamon",
year = "2010",
journal = "Artif. Intell.",
number = "9-10",
pages = "570-584",
volume = "174",
doi = "10.1016/j.artint.2010.03.002",
}
@article{ZJ10constraints,
title = "Classes of submodular constraints expressible by graph cuts",
author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
year = "2010",
journal = "Constraints",
number = "3",
pages = "430-452",
url = "http://zivny.cz/publications/zj10constraints-preprint.pdf",
volume = "15",
doi = "10.1007/s10601-009-9078-z",
}
@inproceedings{3744,
title = "Local consistency and SAT-solvers",
author = "Peter Jeavons and Justyna Petke",
year = "2010",
booktitle = "Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming - CP 2010",
pages = "398-413",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
volume = "6308",
doi = "10.1007/978-3-642-15396-9_33",
}
@techreport{PUPTechRep10,
title = "Tackling the Partner Units Configuration Problem",
author = "Markus Aschinger and Conrad Drescher and Gerhard Friedrich and Georg Gottlob and Peter Jeavons and Anna Ryabokon and Evgenij Thorstensen",
year = "2010",
institution = "Computing Laboratory, University of Oxford",
number = "CS-RR-10-28",
}
@article{DBLP:journals/iandc/BornerBCJK09,
title = "The complexity of constraint satisfaction games and QCSP",
author = "Ferdinand B{\"o}rner and Andrei A. Bulatov and Hubie Chen and Peter Jeavons and Andrei A. Krokhin",
year = "2009",
journal = "Inf. Comput.",
number = "9",
pages = "923-944",
volume = "207",
doi = "10.1016/j.ic.2009.05.003",
}
@article{Zivny09:dam,
title = "The expressive power of binary submodular functions",
author = "Stanislav \v{Z}ivn\'y and David A. Cohen and Peter G. Jeavons",
year = "2009",
journal = "Discrete Applied Mathematics",
number = "15",
pages = "3347--3358",
url = "http://zivny.cz/publications/zcj09dam-preprint.pdf",
volume = "157",
doi = "10.1016/j.dam.2009.07.001",
}
@inproceedings{DBLP:conf/tableaux/Jeavons09,
title = "Presenting Constraints",
author = "Peter Jeavons",
year = "2009",
booktitle = "TABLEAUX",
crossref = "DBLP:conf/tableaux/2009",
editor = "Martin Giese and Arild Waaler",
isbn = "978-3-642-02715-4",
journal = "Automated Reasoning with Analytic Tableaux and Related Methods, 18th International Conference, TABLEAUX 2009, Oslo, Norway, July 6-10, 2009. Proceedings",
pages = "1-15",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
volume = "5607",
doi = "10.1007/978-3-642-02716-1_1",
}
@inproceedings{Zivny09:models,
title = "The complexity of valued constraint models",
author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
year = "2009",
booktitle = "Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP'09)",
number = "5732",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/zj09cp-preprint.pdf",
doi = "10.1007/978-3-642-04244-7_64",
}
@inproceedings{Zivny09:mfcs,
title = "The expressive power of binary submodular functions",
author = "Stanislav \vZ}ivn\'y and David A. Cohen and Peter G. Jeavons",
year = "2009",
booktitle = "Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS'09)",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/zcj09mfcs-preprint.pdf",
}
@techreport{RR-09-07,
title = "Tractable Benchmarks For Constraint Programming",
author = "Justyna Petke and Peter Jeavons",
year = "2009",
institution = "OUCL",
number = "RR-09-07",
}
@techreport{Zivny08:sub-tr,
title = "Which submodular functions are expressible using binary submodular functions?",
author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
year = "2008",
address = "Oxford, UK",
institution = "OUCL",
month = "June",
number = "RR-08-08",
url = "http://zivny.cz/publications/zj08sub-tr.pdf",
}
@article{Zivny08:tcs,
title = "The expressive power of valued constraints: Hierarchies and collapses",
author = "David A. Cohen and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
year = "2008",
journal = "Theoretical Computer Science",
number = "1",
pages = "137--153",
url = "http://zivny.cz/publications/cjz08tcs-preprint.pdf",
volume = "409",
doi = "10.1016/j.tcs.2008.08.036",
}
@article{TournamentTCS,
title = "Generalising submodularity and Horn clauses: tractable optimization problems defined by tournament pair multimorphisms",
author = "David Cohen and Martin Cooper and Peter Jeavons",
year = "2008",
journal = "Theoretical Computer Science",
number = "1-3",
pages = "36-51",
publisher = "Elsevier",
volume = "401",
doi = "doi:10.1016/j.tcs.2008.03.015",
}
@article{StructuralTractability,
title = "A unified theory of structural tractability for constraint satisfaction problems",
author = "David Cohen and Peter Jeavons and Marc Gyssens",
year = "2008",
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",
url = "http://www.comlab.ox.ac.uk/activities/constraints/publications/JCSSspreadcut.pdf",
volume = "74",
doi = "10.1016/j.jcss.2007.08.001",
}
@inproceedings{Zivny08:cp,
title = "Classes of submodular constraints expressible by graph cuts",
author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
year = "2008",
booktitle = "Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP'08)",
pages = "112-127",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/zj08cp-preprint.pdf",
volume = "5202",
doi = "10.1007/978-3-540-85958-1_8",
}
@inproceedings{Cooper2008:hybrid,
title = "Hybrid tractable {CSP}s which generalize tree structure",
author = "Martin C. Cooper and Peter G. Jeavons and Andr{\'a}s Z. Salamon",
year = "2008",
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",
url = "http://www.gaon.net/andras/academic/cjs-ecai2008.pdf",
volume = "178",
}
@inproceedings{Salamon2008:perfect,
title = "Perfect Constraints Are Tractable",
author = "Andr{\'a}s Z. Salamon and Peter G. Jeavons",
year = "2008",
booktitle = "Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming, {CP} 2008, Sydney, Australia, 14--18 September",
isbn = "978-3-540-85957-4",
pages = "524-528",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://www.gaon.net/andras/academic/sj-cp2008.pdf",
volume = "5202",
doi = "10.1007/978-3-540-85958-1_35",
}
@techreport{zcj08arx,
title = "The Expressive Power of Binary Submodular Functions",
author = "Stanislav \v{Z}ivn\'y and David A. Cohen and Peter G. Jeavons",
year = "2008",
note = "arXiv:0811.1885 [cs.DM]",
url = "http://arxiv.org/abs/0811.1885",
}
@techreport{Zivny07:expressiveTR,
title = "The expressive power of valued constraints: hierarchies and collapses",
author = "David A. Cohen and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
year = "2007",
address = "Oxford, UK",
institution = "Computing Laboratory, University of Oxford",
month = "April",
number = "RR-07-03",
url = "http://web.comlab.ox.ac.uk/oucl/publications/tr/RR-07-03.html",
}
@techreport{RR-07-07,
title = "Representing and Solving Finite-Domain Constraint Problems Using Systems of Polynomials",
author = "Chris Jefferson and Peter Jeavons and Martin J. Green and M.R.C. van Dongen",
year = "2007",
institution = "Oxford University Computing Laboratory",
month = "October",
number = "RR-07-07",
}
@inproceedings{GeometricSNP,
title = "A Geometrical Model for the SNP Motif Identification Problem",
author = "Gaofeng Huang and Peter Jeavons",
year = "2007",
booktitle = "Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering, BIBE 2007",
isbn = "978-1-4244-1509-0 ",
pages = "395-402",
url = "http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4375593",
doi = "10.1109/BIBE.2007.4375593",
}
@inproceedings{ExactHeuristicSNP,
title = "Exact and Heuristic Approaches for Identifying Disease-Associated SNP Motifs",
author = "Gaofeng Huang and Peter Jeavons and Dominic Kwiatkowski",
year = "2007",
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",
volume = "5",
}
@inproceedings{Zivny07:cp,
title = "The expressive power of valued constraints: Hierarchies and collapses",
author = "David A. Cohen and Peter G. Jeavons and Stanislav \v{Z}ivn\'y",
year = "2007",
booktitle = "Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP'07)",
pages = "798-805",
series = "Lecture Notes in Computer Science",
url = "http://zivny.cz/publications/cjz07cp-preprint.pdf",
volume = "4741",
doi = "10.1007/978-3-540-74970-7_57",
}
@techreport{RR-06-06,
title = "Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms",
author = "Peter Jeavons and Martin C Cooper and David A Cohen",
year = "2006",
institution = "Oxford University Computing Laboratory",
month = "December",
number = "RR-06-06",
}
@inbook{ComplexityConstraintLanguages,
title = "The complexity of constraint languages",
author = "David Cohen and Peter Jeavons",
year = "2006",
booktitle = "Handbook of Constraint Programming",
chapter = "8",
publisher = "Elsevier",
url = "http://www.comlab.ox.ac.uk/activities/constraints/publications/ComplexityLanguages.pdf",
}
@article{EnhancingBindingSitePrediction,
title = "Enhancing the prediction of transcription factor binding sites by incorporating structural properties and nucleotide covariations",
author = "S. Gunewardena, P. Jeavons, Z. Zhang",
year = "2006",
journal = "Journal of Computational Biology",
number = "4",
pages = "929-945",
url = "http://www.liebertonline.com/doi/abs/10.1089/cmb.2006.13.929",
volume = "13",
doi = "10.1089/cmb.2006.13.929",
}
@article{OperonMycobacteriumBovis,
title = "Characterization of the putative operon containing arylamine N-acetyltransferase (nat) in Mycobacterium bovis BCG",
author = "M. Anderton, S. Bhakta, G. Besra, P. Jeavons, L. Eltis, E. Sim",
year = "2006",
journal = "Molecular Microbiology",
number = "1",
pages = "181-192",
url = "http://www.blackwell-synergy.com/doi/abs/10.1111/j.1365-2958.2005.04945.x",
volume = "59",
doi = "10.1111/j.1365-2958.2005.04945.x",
}
@article{SymmetryDefinitions,
title = "Symmetry definitions for constraint satisfaction problems",
author = "David Cohen and Peter Jeavons and Christopher Jefferson and Karen Petrie and Barbara Smith",
year = "2006",
journal = "Constraints",
note = "Received a Best Paper award.",
pages = "115-137",
url = "http://www.crt.umontreal.ca/~pesant/Constraints/Papers/CohenJJPS06.pdf",
volume = "11",
doi = "10.1007/s10601-006-8059-8",
}
@article{ComplexityOfSoft,
title = "The complexity of soft constraint satisfaction",
author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
year = "2006",
journal = "Artificial Intelligence",
pages = "983-1016",
url = "http://www.comlab.ox.ac.uk/activities/constraints/publications/AIJ-3418.pdf",
volume = "170",
doi = "10.1016/j.artint.2006.04.002",
}
@inproceedings{AlgebraicCharacterisation,
title = "An algebraic characterisation of complexity for valued constraints",
author = "David Cohen and Martin Cooper and Peter Jeavons",
year = "2006",
booktitle = "Proceedings of the 12th International Conference on Principles and Practice of Contraint Programming (CP'06)",
pages = "107-121",
series = "Lecture Notes in Computer Science",
url = "http://www.comlab.ox.ac.uk/activities/constraints/publications/CP06expressibility.pdf",
volume = "4204",
doi = "10.1007/11889205_10",
}
@techreport{RR-05-03,
title = "Exact and Heuristic Approaches for Identifying Disease-Associated SNP Motifs",
author = "Gaofeng Huang and Peter Jeavons and Dominic Kwiatkowski",
year = "2005",
institution = "Oxford University Computing Laboratory",
month = "July",
number = "RR-05-03",
}
@article{ClassifyingComplexity,
title = "Classifying the complexity of constraints using finite algebras",
author = "Andrei Bulatov and Peter Jeavons and Andrei Krokhin",
year = "2005",
journal = "SIAM Journal on Computing",
number = "34",
pages = "720-742",
url = "http://www.comlab.ox.ac.uk/activities/constraints/publications/SIAMclassifying.pdf",
doi = "10.1137/S0097539700376676",
}
@article{SupermodularFunctions,
title = "Supermodular functions and the complexity of MAX CSP",
author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
year = "2005",
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",
url = "http://www.comlab.ox.ac.uk/activities/constraints/publications/DAMsupermodular.pdf",
volume = "149",
doi = "10.1016/j.dam.2005.03.003",
}
@techreport{RR-04-08,
title = "The Complexity of Constraint Satisfaction: An Algebraic Approach",
author = "Andrei Krokhin and Andrei Bulatov and Peter Jeavons",
year = "2004",
institution = "Oxford University Computing Laboratory",
month = "May",
number = "RR-04-08",
}
@techreport{RR-04-24,
title = "Information categorisation in biological sequence alignments",
author = "Sumedha Gunewardena and Peter Jeavons",
year = "2004",
institution = "Oxford University Computing Laboratory",
month = "November",
number = "RR-04-24",
}
@techreport{RR-04-01,
title = "Supermodular Functions and the Complexity of MAX CSP",
author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
year = "2004",
institution = "Oxford University Computing Laboratory",
month = "January",
number = "RR-04-01",
}
@article{ConstraintSatisfaction,
title = "Constraint satisfaction problems on intervals and lengths",
author = "Andrei Krokhin and Peter Jeavons and Peter Jonsson",
year = "2004",
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{http://eccc.hpi-web.de/report/2001/077/}",
number = "17",
pages = "453--477",
url = "http://epubs.siam.org/sam-bin/dbq/article/41020",
}
@article{ImplementingTest,
title = "Implementing a test for tractability",
author = "Richard Gault and Peter Jeavons",
year = "2004",
journal = "Constraints",
pages = "139--160",
url = "http://www.kluweronline.com/article.asp?PIPS=5268458",
volume = "9",
}
@article{MaximalTractable,
title = "A maximal tractable class of soft constraints",
author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
year = "2004",
journal = "Journal of Artificial Intelligence Research",
note = "Earlier version appeared in: Proceedings of IJCAI'03, pp. 209-214: \url{http://www.comlab.ox.ac.uk/activities/constraints/publications/IJCAI03submodular.pdf}",
number = "22",
pages = "01/01/22",
url = "http://www.jair.org/papers/paper1400.html",
}
@inproceedings{CompleteCharacterization,
title = "A complete characterization of complexity for Boolean constraint optimization problems",
author = "David Cohen and Martin Cooper and Peter Jeavons",
year = "2004",
booktitle = "Proceedings of CP'04",
number = "3258",
pages = "212--226",
series = "Lecture Notes in Computer Science",
url = "http://www.comlab.ox.ac.uk/activities/constraints/publications/CP04vsatdichotomy.ps",
}
@techreport{RR-03-21,
title = "Finding transcription factor binding sites in DNA Sequences: A template based approach",
author = "Sumedha Gunewardena and Peter Jeavons",
year = "2003",
institution = "Oxford University Computing Laboratory",
month = "October",
number = "RR-03-21",
}
@article{Learnability,
title = "Learnability of quantified formulas",
author = "Victor Dalmau and Peter Jeavons",
year = "2003",
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",
url = "http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-48WPV2S-1&_user=126524&_coverDate=09%2F05%2F2003&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_rerunOrigin=scholar.google&_acct=C000010360&_version=1&_urlVersion=0&_userid=126524&md5=44eca8b4241d08eae4b7d80f4f4b4d39&searchtype=a",
}
@article{ReasoningTemporalRelations,
title = "Reasoning about temporal relations : the tractable subalgebras of Allen's interval algebra",
author = "Andrei Krokhin and Peter Jeavons and Peter Jonsson",
year = "2003",
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",
doi = "10.1145/876638.876639",
}
@inproceedings{NewTractableClasses,
title = "New Tractable Classes From Old",
author = "David Cohen and Peter Jeavons and Richard Gault",
year = "2003",
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",
doi = "10.1023/A:1025623111033",
}
@inproceedings{FunctionsOf,
title = "Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey",
author = "Andrei Krokhin and Andrei Bulatov and Peter Jeavons",
year = "2003",
booktitle = "Proceedings of 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL'03)",
pages = "343--351",
url = "http://www.cs.ox.ac.uk/activities/constraints/publications/ISMVL03survey.ps",
}
@inproceedings{SoftConstraints,
title = "Soft constraints: complexity and multimorphsims",
author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",
year = "2003",
booktitle = "Proceedings of CP'03",
number = "2833",
pages = "244--258",
series = "Lecture Notes in Computer Science",
url = "http://www.comlab.ox.ac.uk/activities/constraints/publications/CP03multimorphisms.pdf",
}
@inproceedings{AlgebraicApproach,
title = "An algebraic approach to multi-sorted constraints",
author = "Andrei Bulatov and Peter Jeavons",
year = "2003",
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",
url = "http://www.cs.ox.ac.uk/activities/constraints/publications/CP03multisorted.pdf",
}
@inproceedings{QuantifiedConstraints,
title = "Quantified constraints: algorithms and complexity",
author = "Ferdinand B{\"o}rner and Andrei Bulatov and Peter Jeavons and Andrei Krokhin",
year = "2003",
booktitle = "Proceedings of CSL'03",
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",
url = "http://springerlink.metapress.com/content/2gmm51wv6xjx1u3e/fulltext.pdf",
doi = "10.1007/b13224",
}
@inproceedings{ComplexityConstraintSatisfaction,
title = "Structural Theory of Automata, Semigroups, and Universal Algebra",
author = "Andrei Krokhin and Andrei Bulatov and Peter Jeavons",
year = "2003",
address = "University of Montreal",
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",
url = "http://www.springer.com/sgw/cda/frontpage/0,11855,4-10043-22-52121384-0,00.html",
}
@inproceedings{FiniteSemigroups,
title = "Finite semigroups imposing tractable constraints",
author = "Andrei Bulatov and Peter Jeavons and Mikhail Volkov",
year = "2002",
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",
}
@article{AgaroseGelImage,
title = "Automatic analysis of agarose gel images",
author = "P. S. Umesh Adiga, A. Bhomra, M. G. Turri, A. Nicod, S. R. Datta, Peter Jeavons, Richard Mott, Jonathan Flint",
year = "2001",
journal = "Bioinformatics",
number = "11",
pages = "1084-1089",
url = "http://bioinformatics.oxfordjournals.org/cgi/content/abstract/17/11/1084",
volume = "17",
}
@inproceedings{CompleteClassification,
title = "A complete classification of complexity in Allen's algebra in the presence of a non-trivial basic relation",
author = "Andrei Krokhin and Peter Jeavons and Peter Jonsson",
year = "2001",
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",
}
@inproceedings{ComplexityMaximal,
title = "The complexity of maximal constraint languages",
author = "Andrei Bulatov and Andrei Krokhin and Peter Jeavons",
year = "2001",
booktitle = "Proceedings of STOC'01, Crete, Greece",
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",
doi = "10.1145/380752.380868",
}
@techreport{AlgebraicStructures,
title = "Algebraic structures in combinatorial problems",
author = "Andrei Bulatov and Peter Jeavons",
year = "2001",
institution = "Technische Universitat Dresden",
number = "MATH-AL-4-2001",
pages = "32",
url = "http://www.cs.sfu.ca/~abulatov/papers/varieties.ps",
}
@article{BuildingTractable,
title = "Building tractable disjunctive constraints",
author = "David Cohen and Peter Jeavons and Peter Jonsson and Manolis Koubarakis",
year = "2000",
journal = "Journal of the ACM",
number = "47",
pages = "826--853",
url = "http://portal.acm.org/citation.cfm?id=355483.355485",
doi = "10.1145/355483.355485",
}
@inproceedings{ConstraintSatisfactionProblems,
title = "Constraint satisfaction problems and finite algebras",
author = "Andrei Bulatov and Andrei Krokhin, and Peter Jeavons",
year = "2000",
booktitle = "Proceedings of ICALP'00",
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",
url = "http://link.springer.de/link/service/series/0558/bibs/1853/18530272.htm",
doi = "10.1007/3-540-45022-X_24",
}
@techreport{TractableConstraints,
title = "Tractable constraints closed under a binary operation",
author = "Andrei Bulatov and Peter Jeavons",
year = "2000",
institution = "Oxford University Computing Laboratory",
number = "PRG-TR-12-00",
pages = "27",
url = "http://www.cs.ox.ac.uk/techreports/oucl/TR-12-00.ps.gz",
}
@inproceedings{HowToDetermine,
title = "How to determine the expressive power of constraints",
author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
year = "1999",
booktitle = "Constraints",
number = "4",
pages = "113--131",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/how_to_determine.ps",
}
@inproceedings{ConstraintTractability,
title = "Constraint Tractability Theory And Its Application to the Product Development Process for a Constraint-Based Scheduler",
author = "Lisa Purvis and Peter Jeavons",
year = "1999",
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",
url = "http://cse.unl.edu/~choueiry/F03-421-821/Documents/LP-PACLP.doc",
}
@techreport{TowardsHighOrder,
title = "Towards High Order Constraint Representations for the Frequency Assignment Problem",
author = "N.W.Dunkin and J.E.Bater and P.G.Jeavons and D.A.Cohen",
year = "1998",
institution = "Royal Holloway, University of London",
month = "June",
number = "CSD-TR-98-05",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/CSD-TR-98-05.ps",
}
@techreport{AreThere,
title = "Are there optimal reuse distance constraints for FAPs with random Tx placements?",
author = "J.E.Bater and P.G.Jeavons and D.A.Cohen",
year = "1998",
institution = "Royal Holloway, University of London",
month = "February",
number = "CSD-TR-98-01",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/CSD-TR-98-01.ps",
}
@article{OnTheAlgebraicStructure,
title = "On The Algebraic Structure Of Combinatorial Problems",
author = "P.G.Jeavons",
year = "1998",
journal = "Theoretical Computer Science",
number = "200",
pages = "185--204",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/algebraic.ps",
}
@article{ConstraintsConsistencyClosure,
title = "Constraints, Consistency and Closure",
author = "P.G.Jeavons and D.A.Cohen and M.Cooper",
year = "1998",
journal = "Artificial Intelligence",
number = "101 (1-2)",
pages = "251--265",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/conconclo.ps",
}
@article{ConstraintsAndUniversalAlgebra,
title = "Constraints and Universal Algebra",
author = "P.G.Jeavons and D.A.Cohen and J.K.Pearson",
year = "1998",
journal = "Annals of Mathematics and Artificial Intelligence",
number = "24",
pages = "51--67",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/con_and_universal.ps",
}
@inproceedings{WhyHigher,
title = "Why higher order constraints are necessary to model frequency assignment problems",
author = "P.G.Jeavons and N.W.Dunkin and J.E.Bater",
year = "1998",
booktitle = "ECAI'98 Workshop on Non-binary constraints",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/ecaiversion.ps",
}
@inproceedings{ConstructingConstraints,
title = "Constructing constraints",
author = "P.G.Jeavons",
year = "1998",
booktitle = "Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP98)",
pages = "2-16",
series = "Lecture Notes in Computer Science",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/constructing.ps",
volume = "1520",
doi = "10.1007/3-540-49481-2_2",
}
@techreport{SurveyTractable,
title = "A Survey of Tractable Constraint Satisfaction Problems",
author = "J.K.Pearson and P.G.Jeavons",
year = "1997",
institution = "Royal Holloway, University of London",
month = "July",
number = "CSD-TR-97-15",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/survey.ps",
}
@article{ClosreProperties,
title = "Closure Properties of Constraints",
author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
year = "1997",
journal = "Journal of the ACM",
number = "44",
pages = "527--548",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/closure.ps",
}
@inproceedings{Expressiveness,
title = "Expressiveness of Binary Constraints for the Frequency Assignment Problem",
author = "N.W.Dunkin and P.G.Jeavons",
year = "1997",
booktitle = "DIAL-M Workshop, 3rd Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM'97)",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/dunk97.ps",
}
@inproceedings{TractableDisjunctive,
title = "Tractable Disjunctive Constraints",
author = "D.A.Cohen and P.G.Jeavons and M.Kourabarakis",
year = "1997",
booktitle = "Proceedings 3rd International Conference on Principles and Practice of Constraint Programming (CP97)",
number = "1330",
pages = "478--490",
series = "Lecture Notes in Computer Science",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/tractable.ps",
volume = "1330",
doi = "10.1007/BFb0017461",
}
@inproceedings{TestForTractability,
title = "A Test for Tractability",
author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
year = "1996",
booktitle = "Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP96)",
pages = "267-281",
series = "Lecture Notes in Computer Science",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/tractability.ps",
volume = "1118",
doi = "10.1007/3-540-61551-2_80",
}
@inproceedings{DerivationOfConstraint,
title = "Derivation of Constraints and Database Relations",
author = "D.A.Cohen and M.Gyssens and P.G.Jeavons",
year = "1996",
booktitle = "Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP96)",
pages = "134--148",
series = "Lecture Notes in Computer Science",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/derivation.ps",
volume = "1118",
doi = "10.1007/3-540-61551-2_71",
}
@article{TractableConstraintsOrdered,
title = "Tractable Constraints on Ordered Domains",
author = "P.G.Jeavons and M.C.Cooper",
year = "1995",
journal = "Artificial Intelligence",
number = "79(2)",
pages = "327--339",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/maxclos.ps",
}
@inproceedings{SubstitutionOperation,
title = "A Substitution Operation for Constraints",
author = "P.G.Jeavons and D.A.Cohen and M.C.Cooper",
year = "1995",
booktitle = "Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP95)",
pages = "161-177",
series = "Lecture Notes in Computer Science",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/substitution.ps",
volume = "874",
doi = "10.1007/3-540-58601-6_85",
}
@inproceedings{UnifyingFramework,
title = "A Unifying Framework for Tractable Constraints",
author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
year = "1995",
booktitle = "Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP95)",
pages = "276-291",
series = "Lecture Notes in Computer Science",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/unifying.ps",
volume = "976",
doi = "10.1007/3-540-60299-2_17",
}
@article{RecoveringRelation,
title = "Recovering a Relation from a Decomposition using Constraint Satisfaction Techniques",
author = "P.G.Jeavons",
year = "1994",
journal = "Information Sciences",
number = "78",
pages = "229--256",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/recovering.ps",
}
@article{CharacterisingTractable,
title = "Characterising Tractable Constraints",
author = "M.C.Cooper and D.A.Cohen and P.G.Jeavons",
year = "1994",
journal = "Artificial Intelligence",
number = "65(2)",
pages = "347--361",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/characterising.ps",
}
@article{DecomposingConstraint,
title = "Decomposing Constraint Satisfaction Problems Using Database Techniques",
author = "M.Gyssens and P.G.Jeavons and D.A.Cohen",
year = "1994",
journal = "Artificial Intelligence",
number = "66(1)",
pages = "57-89",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/decomposing.ps",
}
@article{StructuralDecomposition,
title = "A Structural Decomposition for Hypergraphs",
author = "P.G.Jeavons and D.A.Cohen and M.Gyssens",
year = "1994",
journal = "Contemporary Mathematics",
number = "178",
pages = "161--177",
url = "ftp://ftp.cs.rhul.ac.uk/pub/constraints/contmath.ps",
}