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

Direct link
Cite
Citation style
  • apa
  • 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
Complexity classification in qualitative temporal constraint reasoning
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
Department of Computer Science, University of Warwick, United Kingdom, Department of Computer Science, University of Durham, Durham DH1 3LE, United Kingdom.
2004 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 160, no 1-2, p. 35-51Article in journal (Refereed) Published
Abstract [en]

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that every other fragment is NP-complete. © 2004 Elsevier B.V. All rights reserved.
Place, publisher, year, edition, pages
2004. Vol. 160, no 1-2, p. 35-51
Keywords [en]
Computational complexity, Constraint satisfaction, Temporal reasoning
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-45559DOI: 10.1016/j.artint.2004.05.010OAI: oai:DiVA.org:liu-45559DiVA, id: diva2:266455
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-13

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Jonsson, Peter

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
The Institute of TechnologyTCSLAB - Theoretical Computer Science Laboratory
In the same journal
Artificial Intelligence
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • 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
v. 2.46.0
|
Accessibility
|
DiVA portal
|
DiVA Log in
|
Contact us
|
LiU University Library
|
SwePub
|
Uppsök