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

Direct link
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, Vol. 160, no 1-2, 35-51 p.Article 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, 35-51 p.
Keyword [en]
Computational complexity, Constraint satisfaction, Temporal reasoning
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-45559DOI: 10.1016/j.artint.2004.05.010OAI: diva2:266455
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2011-01-12

Open Access in DiVA

No full text

Other links

Publisher's full text

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
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 24 hits
ReferencesLink to record
Permanent link

Direct link