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
Computational complexity of linear constraints over the integers
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
2013 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 195, 44-62 p.Article in journal (Refereed) Published
Abstract [en]

Temporal reasoning problems arise in many areas of Al, including planning, natural language understanding, and reasoning about physical systems. The computational complexity of continuous-time temporal constraint reasoning is fairly well understood. There are, however, many different cases where discrete time must be considered; various scheduling problems and reasoning about sampled physical systems are two examples. Here, the complexity of temporal reasoning is not as well-studied nor as well-understood. In order to get a better understanding, we consider the powerful Horn disjunctive linear relations (Horn DLR) formalism adapted for discrete time and study its computational complexity. We show that the full formalism is NP-hard and identify several maximal tractable subclasses. We also lift the maximality results to obtain hardness results for other families of constraints. Finally, we discuss how the results and techniques presented in this paper can be used for studying even more expressive classes of temporal constraints.

Place, publisher, year, edition, pages
Elsevier , 2013. Vol. 195, 44-62 p.
Keyword [en]
Temporal reasoning, Discrete time, Computational complexity
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-91019DOI: 10.1016/j.artint.2012.10.001ISI: 000315839600002OAI: oai:DiVA.org:liu-91019DiVA: diva2:615658
Note

Funding Agencies|Swedish Research Council (VR)|621-2009-4431|Swedish National Graduate School in Computer Science (CUGS)||

Available from: 2013-04-19 Created: 2013-04-11 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

fulltext(388 kB)181 downloads
File information
File name FULLTEXT01.pdfFile size 388 kBChecksum SHA-512
5771eaab851452249ef3f63a382237bfcff805e80bc7c62f3d28d63a0cd7aeaa82ee53493e47ffa6226712e8fd499901b9d0e7542fb338c69f1eb98d2a30b59b
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Jonsson, PeterLööw, Tomas

Search in DiVA

By author/editor
Jonsson, PeterLööw, Tomas
By organisation
Software and SystemsThe Institute of Technology
In the same journal
Artificial Intelligence
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 181 downloads
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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 77 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