Constraints Group: Publications

[1]	Tractable Benchmarks For Constraint Programming Justyna Petke, Peter Jeavons No. RR-09-07, Technical Report, OUCL. 2009. Details \| BibTeX \| Download (pdf)

[2]	Classes of submodular constraints expressible by graph cuts Stanislav Živný, Peter G. Jeavons Constraints, 2009. Details \| BibTeX \| Link (pdf) \| DOI (10.1007/s10601-009-9078-z)

[3]	Structural properties of oracle classes Stanislav Živný Information Processing Letters, Vol. 109, No. 19, pages 1131—1135. 2009. Details \| BibTeX \| Link (pdf) \| DOI (10.1016/j.ipl.2009.07.009)

[4]	The expressive power of binary submodular functions Stanislav Živný, David A. Cohen and Peter G. Jeavons Discrete Applied Mathematics, Vol. 157, No. 15, pages 3347—3358. 2009. Details \| BibTeX \| Link (pdf) \| DOI (10.1016/j.dam.2009.07.001)

[5]	The complexity of valued constraint models Stanislav Živný, Peter G. Jeavons In Proceedings of the 15th International Conference on Principles and Practice of Contraint Programming (CP'09) No. 5732, 2009. Details \| BibTeX \| Link (pdf) \| DOI (10.1007/978-3-642-04244-7_64)

[6]	Same-relation constraints Christopher Jefferson et al. In Proceedings of the 15th International Conference on Principles and Practice of Contraint Programming (CP'09) No. 5732, 2009. Details \| BibTeX \| Link (pdf) \| DOI (10.1007/978-3-642-04244-7_38)

[7]	A note on some collapse results of valued constraints Bruno Zanuttini, Stanislav Živný Information Processing Letters, Vol. 109, No. 11, pages 534—538. 2009. Details \| BibTeX \| Link (pdf) \| DOI (10.1016/j.ipl.2009.01.018)

[8]	Domain permutation reduction for constraint satisfaction problems Martin J. Green, David A. Cohen Artificial Intelligence, Vol. 172, No. 8-9, pages 1094-1118. 2008. Details \| BibTeX \| DOI (10.1016/j.artint.2007.12.001)

[9]	The Expressive Power of Binary Submodular Functions Stanislav Živný, David A. Cohen and Peter G. Jeavons Technical Report, 2008. arXiv:0811.1885 [cs.DM]. Details \| BibTeX \| Link

[10]	The expressive power of valued constraints: Hierarchies and collapses David A. Cohen, Peter G. Jeavons and Stanislav Živný Theoretical Computer Science, Vol. 409, No. 1, pages 137—153. 2008. Details \| BibTeX \| Link (pdf) \| DOI (10.1016/j.tcs.2008.08.036)

[11]	Which submodular functions are expressible using binary submodular functions? Stanislav Živný, Peter G. Jeavons No. RR-08-08, Technical Report, OUCLOxford, UK. June 2008. Details \| BibTeX \| Download (pdf)

[12]	Generalising submodularity and Horn clauses: tractable optimization problems defined by tournament pair multimorphisms David Cohen, Martin Cooper, Peter Jeavons Theoretical Computer Science, Vol. 401, No. 1-3, pages 36-51. 2008. Details \| BibTeX \| DOI (doi:10.1016/j.tcs.2008.03.015)

[13]

Perfect Constraints Are Tractable

András Z. Salamon, 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.

Details | BibTeX | Link (pdf) | DOI (10.1007/978-3-540-85958-1_35)

[14]

Hybrid tractable CSPs which generalize tree structure

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

In Malik Ghallab, Constantine D. Spyropoulos, Nikos Fakotakis, Nikos Avouris, 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.

Details | BibTeX | Link (pdf)

[15]

Classes of submodular constraints expressible by graph cuts

Stanislav Živný, Peter G. Jeavons

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

Details | BibTeX | Link (pdf) | DOI (10.1007/978-3-540-85958-1_8)

[16]

A unified theory of structural tractability for constraint satisfaction problems

David Cohen, Peter Jeavons and Marc Gyssens

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

Details | BibTeX | Link (pdf) | DOI (10.1016/j.jcss.2007.08.001)

[17]	Representing and Solving Finite-Domain Constraint Problems Using Systems of Polynomials Chris Jefferson et al. No. RR-07-08, Technical Report, Oxford University Computing Laboratory. October 2007. Details \| BibTeX \| Download (pdf)

[18]	The expressive power of valued constraints: hierarchies and collapses David A. Cohen, Peter G. Jeavons and Stanislav Živný No. RR-07-03, Technical Report, Computing Laboratory, University of OxfordOxford, UK. 2007. Details \| BibTeX \| Download (pdf)

[19]

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 Contraint Programming (CP'07) Vol. 4741 of Lecture Notes in Computer Science, pages 798-805. 2007.

Details | BibTeX | Link (pdf) | DOI (10.1007/978-3-540-74970-7_57)

[20]

Typed Guarded Decompositions for Constraint Satisfaction

David A. Cohen, Martin J. Green

In Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP'06) Vol. 4204 of Lecture Notes in Computer Science, pages 122-136. 2006.

Details | BibTeX | DOI (10.1007/11889205_11)

[21]

The Effect of Constraint Representation on Structural Tractability

Chris Houghton, David A. Cohen and Martin J. Green

In Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP'06) Vol. 4204 of Lecture Notes in Computer Science, pages 726-730. 2006.

Details | BibTeX | DOI (10.1007/11889205_59)

[22]	Symmetry definitions for constraint satisfaction problems David Cohen et al. Constraints, Vol. 11, pages 115-137. 2006. Received a Best Paper award. Details \| BibTeX \| Link (pdf) \| DOI (10.1007/s10601-006-8059-8)

[23]	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, Technical Report, Oxford University Computing Laboratory. December 2006. Details \| BibTeX \| Download (pdf)

[24]

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.

Details | BibTeX | Link (pdf) | DOI (10.1007/11889205_10)

[25]	The complexity of constraint languages David Cohen, Peter Jeavons In Handbook of Constraint Programming chapter 8, Elsevier. 2006. Details \| BibTeX \| Link (pdf)

[26]	The complexity of soft constraint satisfaction David Cohen et al. Artificial Intelligence, Vol. 170, pages 983-1016. 2006. Details \| BibTeX \| Link (pdf) \| DOI (10.1016/j.artint.2006.04.002)

[27]

Solution Equivalent Subquadrangle Reformulations of Constraint Satisfaction Problems

Chris Houghton, David A. Cohen

In Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming (CP'05) Vol. 3709 of Lecture Notes in Computer Science, pages 851. 2005.

Details | BibTeX | DOI (10.1007/11564751_89)

[28]

Supermodular functions and the complexity of MAX CSP

David Cohen et al.

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).

Details | BibTeX | Link (pdf) | DOI (10.1016/j.dam.2005.03.003)

[29]	Classifying the complexity of constraints using finite algebras Andrei Bulatov, Peter Jeavons and Andrei Krokhin SIAM Journal on Computing, No. 34, pages 720-742. 2005. Details \| BibTeX \| Link (pdf) \| DOI (10.1137/S0097539700376676)

[30]	A Graph of a Relational Structure and Constraint Satisfaction Problems Andrei A. Bulatov In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04) pages 448-45. 2004. Details \| BibTeX \| Link

[31]	The complexity of partition functions Andrei A. Bulatov, Martin Grohe In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04) Vol. 3142 of Lecture Notes in Computer Science, pages 294-306. 2004. Details \| BibTeX \| Link

[32]	Tractable Decision for a Constraint Language Implies Tractable Search David A. Cohen Constraints, Vol. 9, No. 3, pages 219—229. 2004. Details \| BibTeX \| Link

[33]	The Complexity of Constraint Satisfaction: An Algebraic Approach Andrei Krokhin, Andrei Bulatov and Peter Jeavons No. RR-04-08, Technical Report, Oxford University Computing Laboratory. May 2004. Details \| BibTeX \| Download (pdf)

[34]	Supermodular Functions and the Complexity of MAX CSP David Cohen et al. No. RR-04-01, Technical Report, Oxford University Computing Laboratory. January 2004. Details \| BibTeX \| Download (ps)

[35]	A complete characterization of complexity for Boolean constraint optimization problems David Cohen, Martin Cooper, Peter Jeavons In Proceedings of CP'04 No. 3258, pages 212—226. 2004. Details \| BibTeX \| Link (ps)

[36]	Implementing a test for tractability Richard Gault, Peter Jeavons Constraints, Vol. 9, pages 139—160. 2004. Details \| BibTeX \| Link

[37]

A maximal tractable class of soft constraints

David Cohen et al.

Journal of Artificial Intelligence Research, No. 22, pages 01/01/22. 2004.

Earlier version appeared in: Proceedings of IJCAI'03, pp. 209-214: http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/IJCAI03submodular.pdf

Details | BibTeX | Link (html)

[38]

Constraint satisfaction problems on intervals and lengths

Andrei Krokhin, Peter Jeavons and Peter Jonsson

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: ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2001/TR01-077/index.html

Details | BibTeX | Link

[39]	Tractable conservative Constraint Satisfaction Problems Andrei A. Bulatov In Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS'03) 2003. Details \| BibTeX \| Link

[40]	Amalgams of Constraint Satisfaction Problem Andrei A. Bulatov, Evgeny S. Skvortsov In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03) pages 197-202. 2003. Details \| BibTeX

[41]	Tractability by Approximating Constraint Languages Martin J. Green, David A. Cohen In Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming (CP'03) Vol. 2833 of Lecture Notes in Computer Science. 2003. Details \| BibTeX \| Link

[42]

A New Classs of Binary CSPs for which Arc-Constistency Is a Decision Procedure

David A. Cohen

In Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming (CP'03) Vol. 2833 of Lecture Notes in Computer Science, pages 807-811. 2003.

Details | BibTeX | Link

[43]	Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem Andrei A. Bulatov, Victor Dalmau In Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS'03) 2003. Details \| BibTeX \| Link

[44]

Learnability of quantified formulas

Victor Dalmau, Peter Jeavons

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

Details | BibTeX | Link

[45]

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

Details | BibTeX | DOI (10.1023/A:1025623111033)

[46]

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

Details | BibTeX | Link (html)

[47]	Soft constraints: complexity and multimorphsims David Cohen et al. In Proceedings of CP'03 No. 2833, pages 244—258. 2003. Details \| BibTeX \| Link (pdf)

[48]

Quantified constraints: algorithms and complexity

Ferdinand Börner et al.

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

Details | BibTeX | Link (pdf) | DOI (10.1007/b13224)

[49]	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. Details \| BibTeX \| Link (ps)

[50]	An algebraic approach to multi-sorted constraints Andrei Bulatov, 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 Details \| BibTeX \| Link (pdf)

[51]

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

Andrei Krokhin, Peter Jeavons and Peter Jonsson

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

Details | BibTeX | DOI (10.1145/876639)

[52]	A Dichotomy Theorem for Constraints on a Three-Element Set Andrei A. Bulatov In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS'02) 2002. Details \| BibTeX \| Link

[53]	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. Details \| BibTeX

[54]

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

Details | BibTeX | DOI (10.1145/380752.380868)

[55]	Algebraic structures in combinatorial problems Andrei Bulatov, Peter Jeavons No. MATH-AL-4-2001, Technical Report, Technische Universitat Dresden. 2001. Details \| BibTeX \| Link (ps)

[56]

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

Details | BibTeX

[57]	Building tractable disjunctive constraints David Cohen et al. Journal of the ACM, No. 47, pages 826—853. 2000. Details \| BibTeX \| Link \| DOI (http://doi.acm.org/10.1145/355483.355485)

[58]	Tractable constraints closed under a binary operation Andrei Bulatov, Peter Jeavons No. PRG-TR-12-00, Technical Report, Oxford University Computing Laboratory. 2000. Details \| BibTeX \| Link (html)

[59]

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

Details | BibTeX | Link | DOI (10.1007/3-540-45022-X_24)

[60]	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. Details \| BibTeX \| Link (ps)

[61]

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

Lisa Purvis, 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.

Details | BibTeX | Link (doc)

[62]	On The Algebraic Structure Of Combinatorial Problems P.G.Jeavons Theoretical Computer Science, No. 200, pages 185—204. 1998. Details \| BibTeX \| Link (ps)

[63]	Constraints, Consistency and Closure P.G.Jeavons, D.A.Cohen and M.Cooper Artificial Intelligence, No. 101 (1-2), pages 251—265. 1998. Details \| BibTeX \| Link (ps)

[64]	Constraints and Universal Algebra P.G.Jeavons, D.A.Cohen and J.K.Pearson Annals of Mathematics and Artificial Intelligence, No. 24, pages 51—67. 1998. Details \| BibTeX \| Link (ps)

[65]	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. Details \| BibTeX \| Link (ps)

[66]	Towards High Order Constraint Representations for the Frequency Assignment Problem N.W.Dunkin et al. No. CSD-TR-98-05, Technical Report, Royal Holloway, University of London. June 1998. Details \| BibTeX \| Link (ps)

[67]	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. Details \| BibTeX \| Link (ps) \| DOI (10.1007/3-540-49481-2_2)

[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, Technical Report, Royal Holloway, University of London. February 1998. Details \| BibTeX \| Link (ps)

[69]	Closure Properties of Constraints P.G.Jeavons, D.A.Cohen and M.Gyssens Journal of the ACM, No. 44, pages 527—548. 1997. Details \| BibTeX \| Link (ps)

[70]

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.

Details | BibTeX | Link (ps) | DOI (10.1007/BFb0017461)

[71]	Expressiveness of Binary Constraints for the Frequency Assignment Problem N.W.Dunkin, P.G.Jeavons In DIAL-M Workshop, 3rd Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM'97) 1997. Details \| BibTeX \| Link (ps)

[72]	A Survey of Tractable Constraint Satisfaction Problems J.K.Pearson, P.G.Jeavons No. CSD-TR-97-15, Technical Report, Royal Holloway, University of London. July 1997. Details \| BibTeX \| Link (ps)

[73]

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.

Details | BibTeX | Link (ps) | DOI (10.1007/3-540-61551-2_71)

[74]

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.

Details | BibTeX | Link (ps) | DOI (10.1007/3-540-61551-2_80)

[75]	Tractable Constraints on Ordered Domains P.G.Jeavons, M.C.Cooper Artificial Intelligence, No. 79(2), pages 327—339. 1995. Details \| BibTeX \| Link (ps)

[76]

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.

Details | BibTeX | Link (ps) | DOI (10.1007/3-540-60299-2_17)

[77]

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.

Details | BibTeX | Link (ps) | DOI (10.1007/3-540-58601-6_85)

[78]	Recovering a Relation from a Decomposition using Constraint Satisfaction Techniques P.G.Jeavons Information Sciences, No. 78, pages 229—256. 1994. Details \| BibTeX \| Link (ps)

[79]	A Structural Decomposition for Hypergraphs P.G.Jeavons, D.A.Cohen and M.Gyssens Contemporary Mathematics, No. 178, pages 161—177. 1994. Details \| BibTeX \| Link (ps)

[80]	Decomposing Constraint Satisfaction Problems Using Database Techniques M.Gyssens, P.G.Jeavons and D.A.Cohen Artificial Intelligence, No. 66(1), pages 57-89. 1994. Details \| BibTeX \| Link (ps)

[81]	Characterising Tractable Constraints M.C.Cooper, D.A.Cohen and P.G.Jeavons Artificial Intelligence, No. 65(2), pages 347—361. 1994. Details \| BibTeX \| Link (ps)