liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Constants and finite unary relations in qualitative constraint reasoning
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
2018 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 257Article in journal (Refereed) Published
Abstract [en]

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 Allens algebra and RCC-5. (C) 2017 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
ELSEVIER SCIENCE BV , 2018. Vol. 257
Keywords [en]
Constraint satisfaction; Qualitative reasoning; Computational complexity
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-147088DOI: 10.1016/j.artint.2017.12.003ISI: 000427335000001OAI: oai:DiVA.org:liu-147088DiVA, id: diva2:1199571
Available from: 2018-04-20 Created: 2018-04-20 Last updated: 2018-04-20

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Artificial Intelligence
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 164 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf