University of Oxford Logo University of OxfordDepartment of Computer Science - Home

Peter Jeavons : Publications

By dateBy titleBy typeBibtex

[1]

Tractable valued constraints

Peter G. Jeavons and Stanislav Živný

In Lucas Bordeaux‚ Youssef Hamadi‚ Pushmeet Kohli and Robert Mateescu, editors, Tractability: Practical Approaches to Hard Problems. Cambridge University Press. 2012.

This work is in copyright. The draft is for personal use only. No further distribution without permission.

[2]

An algebraic theory of complexity for valued constraints: Establishing a Galois connection

David A. Cohen‚ Páidí Creed‚ Peter G. Jeavons and Stanislav Živný

In Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS'11). Vol. 6907 of Lecture Notes in Computer Science. Pages 231–242. Springer. 2011.

[3]

Tackling the Partner Units Configuration Problem

Markus Aschinger‚ Conrad Drescher‚ Georg Gottlob‚ Peter Jeavons and Evgenij Thorstensen

In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011). Barcelona‚ Spain. 2011.

[4]

Optimization Methods for the Partner Units Problem

Markus Aschinger‚ Conrad Drescher‚ Gerhard Friedrich‚ Georg Gottlob‚ Peter Jeavons‚ Anna Ryabokon and Evgenij Thorstensen

In Proceedings of the 8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2011). Berlin‚ Germany. 2011.

[5]

The order encoding: from tractable CSP to tractable SAT

Justyna Petke and Peter Jeavons

No. RR−11−04. DCS‚ University of Oxford. 2011.

[6]

Structural Decomposition Methods‚ and What They are Good For

Markus Aschinger‚ Conrad Drescher‚ Georg Gottlob‚ Peter Jeavons and Evgenij Thorstensen

2011.

Invited Paper at STACS 2011

[7]

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection

David A. Cohen‚ Paidi Creed‚ Peter G. Jeavons and Stanislav Zivny

No. RR−10−16. OUCL. November, 2010.

[8]

Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination

Martin C. Cooper‚ Peter G. Jeavons and András Z. Salamon

In Artif. Intell.. Vol. 174. No. 9−10. Pages 570−584. 2010.

[9]

Classes of submodular constraints expressible by graph cuts

Stanislav Živný and Peter G. Jeavons

In Constraints. Vol. 15. No. 3. Pages 430−452. 2010.

[10]

Local consistency and SAT−solvers

Peter Jeavons and Justyna Petke

In Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming − CP 2010. Vol. 6308 of Lecture Notes in Computer Science. Pages 398−413. Springer. 2010.

[11]

Tackling the Partner Units Configuration Problem

Markus Aschinger‚ Conrad Drescher‚ Gerhard Friedrich‚ Georg Gottlob‚ Peter Jeavons‚ Anna Ryabokon and Evgenij Thorstensen

No. CS−RR−10−28. Computing Laboratory‚ University of Oxford. 2010.

[12]

The complexity of constraint satisfaction games and QCSP

Ferdinand Börner‚ Andrei A. Bulatov‚ Hubie Chen‚ Peter Jeavons and Andrei A. Krokhin

In Inf. Comput.. Vol. 207. No. 9. Pages 923−944. 2009.

[13]

The expressive power of binary submodular functions

Stanislav Živný‚ David A. Cohen and Peter G. Jeavons

In Discrete Applied Mathematics. Vol. 157. No. 15. Pages 3347–3358. 2009.

[14]

Presenting Constraints

Peter Jeavons

In Martin Giese and Arild Waaler, editors, TABLEAUX. Vol. 5607 of Lecture Notes in Computer Science. Pages 1−15. Springer. 2009.

[15]

The complexity of valued constraint models

Stanislav Živný and Peter G. Jeavons

In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP'09). No. 5732. 2009.

[16]

The expressive power of binary submodular functions

Stanislav ivný‚ David A. Cohen and Peter G. Jeavons

In Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS'09). 2009.

[17]

Tractable Benchmarks For Constraint Programming

Justyna Petke and Peter Jeavons

No. RR−09−07. OUCL. 2009.

[18]

Which submodular functions are expressible using binary submodular functions?

Stanislav Živný and Peter G. Jeavons

No. RR−08−08. OUCL. Oxford‚ UK. June, 2008.

[19]

The expressive power of valued constraints: Hierarchies and collapses

David A. Cohen‚ Peter G. Jeavons and Stanislav Živný

In Theoretical Computer Science. Vol. 409. No. 1. Pages 137–153. 2008.

[20]

Generalising submodularity and Horn clauses: tractable optimization problems defined by tournament pair multimorphisms

David Cohen‚ Martin Cooper and Peter Jeavons

In Theoretical Computer Science. Vol. 401. No. 1−3. Pages 36−51. 2008.

[21]

A unified theory of structural tractability for constraint satisfaction problems

David Cohen‚ Peter Jeavons and Marc Gyssens

In Journal of Computer and System Sciences. Vol. 74. Pages 721−743. 2008.

Earlier‚ uncorrected‚ version appears in Proceedings of IJCAI'05‚ pp. 72–77: http://www.ijcai.org/papers/0521.pdf

[22]

Classes of submodular constraints expressible by graph cuts

Stanislav Živný and Peter G. Jeavons

In Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP'08). Vol. 5202 of Lecture Notes in Computer Science. Pages 112−127. 2008.

[23]

Hybrid tractable CSPs which generalize tree structure

Martin C. Cooper‚ Peter G. Jeavons and András Z. Salamon

In Nikos Avouris Malik Ghallab Constantine D. Spyropoulos Nikos Fakotakis, editor, ECAI 2008‚ Proceedings of the 18th European Conference on Artificial Intelligence‚ July 21–25‚ Patras‚ Greece. Vol. 178 of Frontiers in Artificial Intelligence and Applications. Pages 530–534. IOS Press. 2008.

Best paper award.

[24]

Perfect Constraints Are Tractable

András Z. Salamon and Peter G. Jeavons

In Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming‚ CP 2008‚ Sydney‚ Australia‚ 14–18 September. Vol. 5202 of Lecture Notes in Computer Science. Pages 524−528. Springer. 2008.

[25]

The Expressive Power of Binary Submodular Functions

Stanislav Živný‚ David A. Cohen and Peter G. Jeavons

2008.

arXiv:0811.1885 [cs.DM]

[26]

The expressive power of valued constraints: hierarchies and collapses

David A. Cohen‚ Peter G. Jeavons and Stanislav Živný

No. RR−07−03. Computing Laboratory‚ University of Oxford. Oxford‚ UK. April, 2007.

[27]

Representing and Solving Finite−Domain Constraint Problems Using Systems of Polynomials

Chris Jefferson‚ Peter Jeavons‚ Martin J. Green and M.R.C. van Dongen

No. RR−07−07. Oxford University Computing Laboratory. October, 2007.

[28]

A Geometrical Model for the SNP Motif Identification Problem

Gaofeng Huang and Peter Jeavons

In Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering‚ BIBE 2007. Pages 395−402. 2007.

[29]

Exact and Heuristic Approaches for Identifying Disease−Associated SNP Motifs

Gaofeng Huang‚ Peter Jeavons and Dominic Kwiatkowski

In Proceedings of 5th Asia−Pacific Bioinformatics Conference‚ APBC 2007. Vol. 5 of Advances in Bioinformatics and Computational Biology. Pages 175−184. Imperial College Press. 2007.

[30]

The expressive power of valued constraints: Hierarchies and collapses

David A. Cohen‚ Peter G. Jeavons and Stanislav Živný

In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP'07). Vol. 4741 of Lecture Notes in Computer Science. Pages 798−805. 2007.

[31]

Generalising Submodularity and Horn Clauses: Tractable optimization problems defined by tournament pair multimorphisms

Peter Jeavons‚ Martin C Cooper and David A Cohen

No. RR−06−06. Oxford University Computing Laboratory. December, 2006.

[32]

The complexity of constraint languages

David Cohen and Peter Jeavons

In Handbook of Constraint Programming. Chapter 8. Elsevier. 2006.

[33]

Enhancing the prediction of transcription factor binding sites by incorporating structural properties and nucleotide covariations

Z. Zhang S. Gunewardena P. Jeavons

In Journal of Computational Biology. Vol. 13. No. 4. Pages 929−945. 2006.

[34]

Characterization of the putative operon containing arylamine N−acetyltransferase (nat) in Mycobacterium bovis BCG

E. Sim M. Anderton S. Bhakta G. Besra P. Jeavons L. Eltis

In Molecular Microbiology. Vol. 59. No. 1. Pages 181−192. 2006.

[35]

Symmetry definitions for constraint satisfaction problems

David Cohen‚ Peter Jeavons‚ Christopher Jefferson‚ Karen Petrie and Barbara Smith

In Constraints. Vol. 11. Pages 115−137. 2006.

Received a Best Paper award.

[36]

The complexity of soft constraint satisfaction

David Cohen‚ Martin Cooper‚ Peter Jeavons and Andrei Krokhin

In Artificial Intelligence. Vol. 170. Pages 983−1016. 2006.

[37]

An algebraic characterisation of complexity for valued constraints

David Cohen‚ Martin Cooper and Peter Jeavons

In Proceedings of the 12th International Conference on Principles and Practice of Contraint Programming (CP'06). Vol. 4204 of Lecture Notes in Computer Science. Pages 107−121. 2006.

[38]

Exact and Heuristic Approaches for Identifying Disease−Associated SNP Motifs

Gaofeng Huang‚ Peter Jeavons and Dominic Kwiatkowski

No. RR−05−03. Oxford University Computing Laboratory. July, 2005.

[39]

Classifying the complexity of constraints using finite algebras

Andrei Bulatov‚ Peter Jeavons and Andrei Krokhin

In SIAM Journal on Computing. No. 34. Pages 720−742. 2005.

[40]

Supermodular functions and the complexity of MAX CSP

David Cohen‚ Martin Cooper‚ Peter Jeavons and Andrei Krokhin

In Discrete Applied Mathematics. Vol. 149. Pages 53−72. 2005.

Earlier version appeared as Identifying efficiently solvable cases of Max CSP 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)

[41]

The Complexity of Constraint Satisfaction: An Algebraic Approach

Andrei Krokhin‚ Andrei Bulatov and Peter Jeavons

No. RR−04−08. Oxford University Computing Laboratory. May, 2004.

[42]

Information categorisation in biological sequence alignments

Sumedha Gunewardena and Peter Jeavons

No. RR−04−24. Oxford University Computing Laboratory. November, 2004.

[43]

Supermodular Functions and the Complexity of MAX CSP

David Cohen‚ Martin Cooper‚ Peter Jeavons and Andrei Krokhin

No. RR−04−01. Oxford University Computing Laboratory. January, 2004.

[44]

Constraint satisfaction problems on intervals and lengths

Andrei Krokhin‚ Peter Jeavons and Peter Jonsson

In SIAM Journal on Discrete Mathematics. No. 17. Pages 453–477. 2004.

Earlier version appears in Proceedings of STACS'02‚ Lecture Notes in Computer Science‚ 2285‚ (2002)‚ pp. 443–454: 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: http://eccc.hpi-web.de/report/2001/077/

[45]

Implementing a test for tractability

Richard Gault and Peter Jeavons

In Constraints. Vol. 9. Pages 139–160. 2004.

[46]

A maximal tractable class of soft constraints

David Cohen‚ Martin Cooper‚ Peter Jeavons and Andrei Krokhin

In Journal of Artificial Intelligence Research. No. 22. Pages 01/01/22. 2004.

Earlier version appeared in: Proceedings of IJCAI'03‚ pp. 209−214: http://www.comlab.ox.ac.uk/activities/constraints/publications/IJCAI03submodular.pdf

[47]

A complete characterization of complexity for Boolean constraint optimization problems

David Cohen‚ Martin Cooper and Peter Jeavons

In Proceedings of CP'04. No. 3258. Pages 212–226. 2004.

[48]

Finding transcription factor binding sites in DNA Sequences: A template based approach

Sumedha Gunewardena and Peter Jeavons

No. RR−03−21. Oxford University Computing Laboratory. October, 2003.

[49]

Learnability of quantified formulas

Victor Dalmau and Peter Jeavons

In Theoretical Computer Science. No. 306. Pages 485–511. 2003.

Earlier version appeared in Proceedings of EuroCOLT 99‚ Nordkirchen‚ Germany‚ (1999)‚ pp. 63−78 : http://link.springer.de/link/service/series/0558/bibs/1572/15720063.htm

[50]

Reasoning about temporal relations : the tractable subalgebras of Allen's interval algebra

Andrei Krokhin‚ Peter Jeavons and Peter Jonsson

In Journal of the ACM. No. 50. Pages 591–640. 2003.

Earlier version available as an OUCL Research Report : http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-01-12.html

[51]

New Tractable Classes From Old

David Cohen‚ Peter Jeavons and Richard Gault

No. 8. Pages 263–282. 2003.

Earlier version appears in Proceedings of CP2000‚ Lecture Notes In Computer Science‚ 1894‚ 2000‚ pp. 160–171 : http://link.springer.de/link/service/series/0558/bibs/1894/18940160.htm

[52]

Functions of multiple−valued logic and the complexity of constraint satisfaction: A short survey

Andrei Krokhin‚ Andrei Bulatov and Peter Jeavons

In Proceedings of 33rd IEEE International Symposium on Multiple−Valued Logic (ISMVL'03). Pages 343–351. 2003.

[53]

Soft constraints: complexity and multimorphsims

David Cohen‚ Martin Cooper‚ Peter Jeavons and Andrei Krokhin

In Proceedings of CP'03. No. 2833. Pages 244–258. 2003.

[54]

An algebraic approach to multi−sorted constraints

Andrei Bulatov and Peter Jeavons

In Proceedings of CP'03. No. 2833. Pages 183–198. 2003.

Earlier version available as an OUCL Research Report : http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-01-18.html

[55]

Quantified constraints: algorithms and complexity

Ferdinand Börner‚ Andrei Bulatov‚ Peter Jeavons and Andrei Krokhin

In Proceedings of CSL'03. No. 2803. Pages 58–70. 2003.

Longer version available as an OUCL Research Report: http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-02-11.html

[56]

Structural Theory of Automata‚ Semigroups‚ and Universal Algebra

Andrei Krokhin‚ Andrei Bulatov and Peter Jeavons

In Proceedings of SMS−NATO ASI. Pages 181−213. University of Montreal. 2003.

Earlier version available as an OUCL Research Report: http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-04-08.html

[57]

Finite semigroups imposing tractable constraints

Andrei Bulatov‚ Peter Jeavons and Mikhail Volkov

In Proceedings of the School on Algorithmic Aspects of the Theory of Semigroups and its Applications‚ Coimbra‚ Portugal‚ 2001. Pages 313–329. World Scientific‚ Singapore. 2002.

[58]

Automatic analysis of agarose gel images

Jonathan Flint P. S. Umesh Adiga A. Bhomra M. G. Turri A. Nicod S. R. Datta Peter Jeavons Richard Mott

In Bioinformatics. Vol. 17. No. 11. Pages 1084−1089. 2001.

[59]

A complete classification of complexity in Allen's algebra in the presence of a non−trivial basic relation

Andrei Krokhin‚ Peter Jeavons and Peter Jonsson

In Proceedings of IJCAI'01‚ Seattle‚ USA. Pages 83–88. 2001.

Longer version available as an OUCL Research Report : http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-01-02.html

[60]

The complexity of maximal constraint languages

Andrei Bulatov‚ Andrei Krokhin and Peter Jeavons

In Proceedings of STOC'01‚ Crete‚ Greece. Pages 667–674. 2001.

Earlier version available as an OUCL Research Report : http://web.comlab.ox.ac.uk/oucl/publications/tr/rr-01-03.html

[61]

Algebraic structures in combinatorial problems

Andrei Bulatov and Peter Jeavons

No. MATH−AL−4−2001. Technische Universitat Dresden. 2001.

[62]

Building tractable disjunctive constraints

David Cohen‚ Peter Jeavons‚ Peter Jonsson and Manolis Koubarakis

In Journal of the ACM. No. 47. Pages 826–853. 2000.

[63]

Constraint satisfaction problems and finite algebras

Andrei Bulatov‚ Andrei Krokhin and Peter Jeavons

In Proceedings of ICALP'00. No. 1853. Pages 272–282. 2000.

Longer version available as an OUCL Technical Report : http://web.comlab.ox.ac.uk/oucl/publications/tr/tr-4-99.html

[64]

Tractable constraints closed under a binary operation

Andrei Bulatov and Peter Jeavons

No. PRG−TR−12−00. Oxford University Computing Laboratory. 2000.

[65]

How to determine the expressive power of constraints

P.G.Jeavons‚ D.A.Cohen and M.Gyssens

In Constraints. No. 4. Pages 113–131. 1999.

[66]

Constraint Tractability Theory And Its Application to the Product Development Process for a Constraint−Based Scheduler

Lisa Purvis and Peter Jeavons

In Proceedings of the 1st International Conference on The Practical Application of Constraint Technologies and Logic Programming. Pages 63–79. 1999.

This paper was awarded First Prize in the Constraints Technologies area of PACLP'99

[67]

Towards High Order Constraint Representations for the Frequency Assignment Problem

N.W.Dunkin‚ J.E.Bater‚ P.G.Jeavons and D.A.Cohen

No. CSD−TR−98−05. Royal Holloway‚ University of London. June, 1998.

[68]

Are there optimal reuse distance constraints for FAPs with random Tx placements?

J.E.Bater‚ P.G.Jeavons and D.A.Cohen

No. CSD−TR−98−01. Royal Holloway‚ University of London. February, 1998.

[69]

On The Algebraic Structure Of Combinatorial Problems

P.G.Jeavons

In Theoretical Computer Science. No. 200. Pages 185–204. 1998.

[70]

Constraints‚ Consistency and Closure

P.G.Jeavons‚ D.A.Cohen and M.Cooper

In Artificial Intelligence. No. 101 (1−2). Pages 251–265. 1998.

[71]

Constraints and Universal Algebra

P.G.Jeavons‚ D.A.Cohen and J.K.Pearson

In Annals of Mathematics and Artificial Intelligence. No. 24. Pages 51–67. 1998.

[72]

Why higher order constraints are necessary to model frequency assignment problems

P.G.Jeavons‚ N.W.Dunkin and J.E.Bater

In ECAI'98 Workshop on Non−binary constraints. 1998.

[73]

Constructing constraints

P.G.Jeavons

In Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP98). Vol. 1520 of Lecture Notes in Computer Science. Pages 2−16. 1998.

[74]

A Survey of Tractable Constraint Satisfaction Problems

J.K.Pearson and P.G.Jeavons

No. CSD−TR−97−15. Royal Holloway‚ University of London. July, 1997.

[75]

Closure Properties of Constraints

P.G.Jeavons‚ D.A.Cohen and M.Gyssens

In Journal of the ACM. No. 44. Pages 527–548. 1997.

[76]

Expressiveness of Binary Constraints for the Frequency Assignment Problem

N.W.Dunkin and P.G.Jeavons

In DIAL−M Workshop‚ 3rd Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM'97). 1997.

[77]

Tractable Disjunctive Constraints

D.A.Cohen‚ P.G.Jeavons and M.Kourabarakis

In Proceedings 3rd International Conference on Principles and Practice of Constraint Programming (CP97). Vol. 1330 of Lecture Notes in Computer Science. No. 1330. Pages 478–490. 1997.

[78]

A Test for Tractability

P.G.Jeavons‚ D.A.Cohen and M.Gyssens

In Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP96). Vol. 1118 of Lecture Notes in Computer Science. Pages 267−281. 1996.

[79]

Derivation of Constraints and Database Relations

D.A.Cohen‚ M.Gyssens and P.G.Jeavons

In Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP96). Vol. 1118 of Lecture Notes in Computer Science. Pages 134–148. 1996.

[80]

Tractable Constraints on Ordered Domains

P.G.Jeavons and M.C.Cooper

In Artificial Intelligence. No. 79(2). Pages 327–339. 1995.

[81]

A Substitution Operation for Constraints

P.G.Jeavons‚ D.A.Cohen and M.C.Cooper

In Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP95). Vol. 874 of Lecture Notes in Computer Science. Pages 161−177. 1995.

[82]

A Unifying Framework for Tractable Constraints

P.G.Jeavons‚ D.A.Cohen and M.Gyssens

In Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP95). Vol. 976 of Lecture Notes in Computer Science. Pages 276−291. 1995.

[83]

Recovering a Relation from a Decomposition using Constraint Satisfaction Techniques

P.G.Jeavons

In Information Sciences. No. 78. Pages 229–256. 1994.

[84]

Characterising Tractable Constraints

M.C.Cooper‚ D.A.Cohen and P.G.Jeavons

In Artificial Intelligence. No. 65(2). Pages 347–361. 1994.

[85]

Decomposing Constraint Satisfaction Problems Using Database Techniques

M.Gyssens‚ P.G.Jeavons and D.A.Cohen

In Artificial Intelligence. No. 66(1). Pages 57−89. 1994.

[86]

A Structural Decomposition for Hypergraphs

P.G.Jeavons‚ D.A.Cohen and M.Gyssens

In Contemporary Mathematics. No. 178. Pages 161–177. 1994.