Finite Unary Relations and Qualitative Constraint Satisfaction
2016 (English)In: ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, IOS PRESS , 2016, Vol. 285, 37-45 p.Conference paper (Refereed)
Extending qualitative CSPs with the ability of restricting selected variables to finite sets of possible values has been proposed as an important research direction with important applications. Complexity results for this kind of formalisms have appeared in the literature but they focus 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 our methods on temporal and spatial formalisms including Allens algebra and RCC5.
Place, publisher, year, edition, pages
IOS PRESS , 2016. Vol. 285, 37-45 p.
, Frontiers in Artificial Intelligence and Applications, ISSN 0922-6389
Probability Theory and Statistics
IdentifiersURN: urn:nbn:se:liu:diva-132565DOI: 10.3233/978-1-61499-672-9-37ISI: 000385793700006ISBN: 978-1-61499-672-9; 978-1-61499-671-2OAI: oai:DiVA.org:liu-132565DiVA: diva2:1046665
22nd European Conference on Artificial Intelligence (ECAI)