Constraints Research Group - Publications

Recent Papers

• A unified theory of structural tractability for constraint satisfaction problems
  David Cohen, Peter Jeavons and Marc Gyssens
  To appear in: Journal of Computer and System Sciences
  (Earlier, uncorrected, version appears in Proceedings of IJCAI'05, (2005), pp. 72-77 )
• The expressive power of valued constraints: hierarchies and collapses
  David Cohen, Peter Jeavons and Stanislav Zivny
  To appear in: Proceedings of CP'07, Lecture Notes in Computer Science, (2007),
  (Longer version available as an OUCL Research Report)
• An algebraic characterisation of complexity for valued constraints,
  David Cohen, Martin Cooper and Peter Jeavons
  Appears in: Proceedings of CP'06, Lecture Notes in Computer Science 4204, (2006), pp. 107-121 
• The complexity of soft constraint satisfaction
  David Cohen, Martin Cooper, Peter Jeavons and Andrei Krokhin
  Appears in: Artificial Intelligence 170, (2006), pp. 983-1016 
• The complexity of constraint languages
  David Cohen and Peter Jeavons
  Appears in: Handbook of Constraint Programming, Elsevier, (2006), Chapter 8
• Symmetry definitions for constraint satisfaction problems
  David Cohen, Peter Jeavons, Christopher Jefferson, Karen Petrie and Barbara Smith
  Appears in: Constraints 11, (2006), pp.115-137
  (Shorter version appears in: Proceedings of CP'05, Lecture Notes in Computer Science 3709, (2005), pp. 17-31 
  (Received a Best Paper award))
• Supermodular functions and the complexity of MAX CSP
  David Cohen, Martin Cooper, Peter Jeavons and Andrei Krokhin
  Appears in: Discrete Applied Mathematics 149, (2005), pp. 53-72 
  (Earlier version appeared as Identifying efficiently solvable cases of Max CSP
  in: Proceedings of STACS'04, Lecture Notes in Computer Science 2996, (2004), pp.152-163)
• Classifying the complexity of constraints using finite algebras
  Andrei Bulatov, Peter Jeavons and Andrei Krokhin
  Appears in: SIAM Journal on Computing 34, (2005), pp. 720-742 
• A complete characterization of complexity for Boolean constraint optimization problems,
  David Cohen, Martin Cooper and Peter Jeavons
  Appears in: Proceedings of CP'04, Lecture Notes in Computer Science 3258, (2004), pp. 212-226 
• A maximal tractable class of soft constraints
  David Cohen, Martin Cooper, Peter Jeavons and Andrei Krokhin
  Appears in: Journal of Artificial Intelligence Research 22, (2004), pp.1-22
  (Earlier version appeared in: Proceedings of IJCAI'03, (2003), pp. 209-214)
• Tractable decision for a constraint language implies tractable search
  David Cohen
  Appears in: Constraints 9, (2004), pp.219-229
• The complexity of partition functions
  Andrei Bulatov and Martin Grohe
  Appears in: Proceedings of ICALP'04, Lecture Notes in Computer Science 3142, (2004), pp.294-306
• The complexity of constraint satisfaction: an algebraic approach
  Andrei Krokhin, Andrei Bulatov and Peter Jeavons
  Appears in: Structural Theory of Automata, Semigroups, and Universal Algebra
  Proceedings of SMS-NATO ASI, University of Montreal, (2003), pp.181-213
  (Earlier version available as an OUCL Research Report)
• A graph of a relational structure and constraint satisfaction problems
  Andrei Bulatov
  Appears in: Proceedings of LICS'04, IEEE Press, (2004), pp.448-457
• Implementing a test for tractability
  Richard Gault and Peter Jeavons
  Appears in: Constraints 9, (2004), pp.139-160
• Constraint satisfaction problems on intervals and lengths
  Andrei Krokhin, Peter Jeavons and Peter Jonsson
  Appears in: SIAM Journal on Discrete Mathematics 17, (2004), pp. 453-477
  (Earlier version appears in Proceedings of STACS'02, Lecture Notes in Computer Science 2285, (2002), pp. 443-454)
  (Preprint version available from Electronic Colloquium on Computational Complexity, as Report TR01-077)
• Quantified constraints: algorithms and complexity
  Ferdinand Börner, Andrei Bulatov, Peter Jeavons and Andrei Krokhin
  Appears in: Proceedings of CSL'03, Lecture Notes in Computer Science 2803, (2003), pp. 58-70
  (Longer version available as an OUCL Research Report)
• Reasoning about temporal relations : the tractable subalgebras of Allen's interval algebra
  Andrei Krokhin, Peter Jeavons and Peter Jonsson
  Appears in: Journal of the ACM, 50, (2003), pp. 591-640
  (Earlier version available as an OUCL Research Report)
• Towards a dichotomy theorem for the counting constraint satisfaction problem
  Andrei Bulatov and Victor Dalmau
  Appears in: Proceedings of FOCS'03, Cambridge, USA, (2003), pp. 562-572
• Learnability of quantified formulas
  Victor Dalmau and Peter Jeavons
  Appears in: Theoretical Computer Science 306 (2003), pp. 485-511
  (Earlier version appeared in Proceedings of EuroCOLT 99, Nordkirchen, Germany, (1999), pp. 63-78)
• An algebraic approach to multi-sorted constraints
  Andrei Bulatov and Peter Jeavons
  Appears in: Proceedings of CP'03, Lecture Notes in Computer Science 2833, (2003), pp. 183-198
  (Earlier version available as an OUCL Research Report)
• Soft constraints: complexity and multimorphsims
  David Cohen, Martin Cooper, Peter Jeavons and Andrei Krokhin
  Appears in: Proceedings of CP'03, Lecture Notes in Computer Science 2833, (2003), pp. 244-258
• Tractability by approximating constraint languages
  Martin Green, David Cohen
  Appears in: Proceedings of CP'03, Lecture Notes in Computer Science 2833, (2003), pp. 392-406
• A new classs of binary CSPs for which arc-consistency is a decision procedure
  David Cohen
  Appears in: Proceedings of CP'03, Lecture Notes in Computer Science 2833, (2003), pp. 807-811
• Amalgams of constraint satisfaction problems
  Andrei Bulatov and Eugeny Skvortsov
  Appears in: Proceedings of IJCAI'03, (2003), pp. 197-202
• Tractable conservative constraint satisfaction problems
  Andrei Bulatov
  Appears in: Proceedings of 18th IEEE Symposium on Logic in Computer Science (LICS'03), (2003), pp. 321-330
  (Longer version available as an OUCL Research Report)
• Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
  Andrei Krokhin, Andrei Bulatov and Peter Jeavons
  Appears in: Proceedings of 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL'03), (2003), pp. 343-351
• A dichotomy theorem for constraints on a three-element set
  Andrei Bulatov
  Proceedings of FOCS'02, Vancouver, Canada, (2002), pp. 649-658 (Received a Best Paper award)
  (Longer version available as an OUCL Research Report)
• Malt'sev constraints are tractable
  Andrei Bulatov
  Research Report PRG-RR-02-05, Oxford University Computing Laboratory, (2002), 36pp.
• Finite semigroups imposing tractable constraints
  Andrei Bulatov, Peter Jeavons and Mikhail Volkov
  Proceedings of the School on Algorithmic Aspects of the Theory of Semigroups and its Applications, Coimbra, Portugal, 2001, World Scientific, Singapore, (2002), pp. 313-329.
• The complexity of maximal constraint languages
  Andrei Bulatov, Andrei Krokhin, and Peter Jeavons
  In Proceedings of STOC'01, Crete, Greece, (2001), pp. 667-674
  (Earlier version available as an OUCL Research Report)
• Algebraic structures in combinatorial problems
  Andrei Bulatov and Peter Jeavons
  Technical Report MATH-AL-4-2001, Technische Universitat Dresden, (2001), 32pp.
• 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, (2001), pp. 83-88.
  (Longer version available as an OUCL Research Report)
• Constraint satisfaction problems and finite algebras,
  Andrei Bulatov, Andrei Krokhin, and Peter Jeavons
  in Proceedings of ICALP'00, Lecture Notes in Computer Science 1853, (2000), pp. 272-282
  (Longer version available as an OUCL Technical Report)
• Tractable constraints closed under a binary operation
  Andrei Bulatov and Peter Jeavons
  OUCL Technical Report PRG-TR-12-00, Oxford University Computing Laboratory, (2000), 27pp.
• Building tractable disjunctive constraints
  David Cohen, Peter Jeavons, Peter Jonsson, and Manolis Koubarakis
  Appears in: Journal of the ACM, 47, (2000), pp. 826-853
• New Tractable Classes From Old
  David Cohen, Peter Jeavons, and Richard Gault
  Appears in: Constraints, 8, (2003), pp. 263-282
  (Earlier version appears in Proceedings of CP2000, Lecture Notes In Computer Science, 1894, (2000), pp. 160-171)

Papers written while Peter Jeavons was at Royal Holloway

• Constraints and Universal Algebra
  P.G.Jeavons, D.A.Cohen and J.K.Pearson
  Appears in: Annals of Mathematics and Artificial Intelligence, 1998, 24, pp.51-67
  
• Constraint Tractability Theory And Its Application to the Product Development Process for a Constraint-Based Scheduler
  Lisa Purvis and Peter Jeavons
  Appears in: Proceedings of the 1st International Conference on The Practical Application of Constraint Technologies and Logic Programming, 1999, pages 63-79
  D (This paper was awarded First Prize in the Constraints Technologies area of PACLP'99)
  
• How to determine the expressive power of constraints
  P.G.Jeavons, D.A.Cohen and M.Gyssens
  Appears in: Constraints, 1999, 4, pages 113-131
  
• Constructing constraints
  P.G.Jeavons
  Appears in: Lecture Notes in Computer Science, 1998, (Proceedings CP'98),1520, pages 2-17
  
• Why higher order constraints are necessary to model frequency assignment problems
  P.G.Jeavons, N.W.Dunkin and J.E.Bater
  Appears in: ECAI'98 Workshop on Non-binary constraints
• Constraints, Consistency and Closure
  P.G.Jeavons, D.A.Cohen and M.Cooper
  Appears in: Artificial Intelligence, 1998, 101(1-2), pages 251-265
  
• Tractable Disjunctive Constraints
  D.A.Cohen, P.G.Jeavons and M.Kourabarakis
  Appears in: Lecture Notes in Computer Science, 1997, 1330, pages 478-490
  
• Expressiveness of Binary Constraints for the Frequency Assignment Problem
  N.W.Dunkin and P.G.Jeavons.
  Appears in: DIAL-M Workshop, 3rd Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM'97)
• On The Algebraic Structure Of Combinatorial Problems
  P.G.Jeavons.
  Appears in: Theoretical Computer Science, 1998, 200, pages 185-204.
• Closure Properties of Constraints,
  P.G.Jeavons, D.A.Cohen and M.Gyssens.
  Appears in: The Journal of the ACM, 1997, 44, pages 527-548.
• Derivation of Constraint and Database Relations
  D.A.Cohen, M.Gyssens, and P.G.Jeavons.
  Appears in: Lecture Notes in Computer Science, 1996, 1118, pages 134-148.
• A Test for Tractability
  P.G.Jeavons, D.A.Cohen and M.Gyssens.
  Appears in: Lecture Notes in Computer Science, 1996, 1118, pages 267-281
• Tractable Constraints on Ordered Domains
  P.G.Jeavons and M.C.Cooper.
  Appears in: Artificial Intelligence, 1995, 79(2), pages 327-339.
• A Unifying Framework for Tractable Constraints
  P.G.Jeavons, D.A.Cohen and M.Gyssens.
  Appears in: Lecture Notes in Computer Science, 1995, 976, pages 276-291.
• A Substitution Operation for Constraints
  P.G.Jeavons, D.A.Cohen and M.C.Cooper.
  Appears in: Lecture Notes in Computer Science, 1995, 874, pages 161-177.
• A Structural Decomposition for Hypergraphs
  P.G.Jeavons, D.A.Cohen and M.Gyssens.
  Appears in: Contemporary Mathematics, 1994, 178, pages 161-177.
• Decomposing Constraint Satisfaction Problems Using Database Techniques
  M.Gyssens, P.G.Jeavons and D.A.Cohen.
  Appears in: Artificial Intelligence, 1994, 66(1), pages 57-89.
• Characterising Tractable Constraints
  M.C.Cooper, D.A.Cohen and P.G.Jeavons.
  Appears in: Artificial Intelligence, 1994, 65(2), pages 347-361.
• Recovering a Relation from a Decomposition using Constraint Satisfaction Techniques
  P.G.Jeavons.
  Appears in: Information Sciences, 1994, 78, pages 229-256.

Other Documents

• Towards High Order Constraint Representations for the Frequency Assignment Problem,
  N.W.Dunkin, J.E.Bater, P.G.Jeavons and D.A.Cohen
  Technical Report CSD-TR-98-05, June, 1998.
• Are there optimal reuse distance constraints for FAPs with random Tx placements?,
  J.E.Bater, P.G.Jeavons and D.A.Cohen
  Technical Report CSD-TR-98-01, February, 1998.
• A Survey of Tractable Constraint Satisfaction Problems,
  J.K.Pearson and P.G.Jeavons
  Technical Report CSD-TR-97-15, July, 1997.
• A BibTeX Bibliography file on constraints