Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Constructing Constraints

Peter JeavonsContact Information

(6)  Department of Computer Science, Royal Holloway, University of London, UK
Abstract
It is well-known that there is a trade-off between the expressive power of a constraint language and the tractability of the problems it can express. But how can you determine the expressive power of a given constraint language, and how can you tell if problems expressed in that language are tractable? In this paper we discuss some general approaches to these questions
We show that for languages over a finite domain the concept of an ‘indicator Problem’ gives a universal construction for any constraint within the expressive power of a language. We also discuss the fact that all known tractable languages over finite domains are characterised by the presence of a particular solution to a corresponding indicator problem, and raise the question of whether this is a universal property of tractable languages

Contact Information Peter Jeavons
Email: p.jeavons@dcs.rhbnc.ac.uk
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb04
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)