Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6853042 | Artificial Intelligence | 2018 | 23 Pages |
Abstract
Extending qualitative CSPs with the ability of restricting selected variables to finite sets of possible values has been proposed as an interesting research direction with important applications, cf. “Qualitative constraint satisfaction problems: an extended framework with landmarks” by Li, Liu, and Wang (2013) [48]. Previously presented complexity results for this kind of extended formalisms have typically focused on concrete examples and not on general principles. We propose three general methods. The first two methods are based on analysing the given CSP from a model-theoretical perspective, while the third method is based on directly analysing the growth of the representation of solutions. We exemplify the methods on temporal and spatial formalisms including Allen's algebra and RCC-5.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Peter Jonsson,