liu.seSearch for publications in DiVA
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
Reasoning about Action in Polynomial Time
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
1997 (English)In: Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI), 1997Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
1997.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-74308OAI: oai:DiVA.org:liu-74308DiVA, id: diva2:482635
Available from: 2012-01-24 Created: 2012-01-24 Last updated: 2022-01-26
In thesis
1. Algorithms and Complexity for Temporal and Spatial Formalisms
Open this publication in new window or tab >>Algorithms and Complexity for Temporal and Spatial Formalisms
1997 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The problem of computing with temporal information was early recognised within the area of artificial intelligence, most notably the temporal interval algebra by Allen has become a widely used formalism for representing and computing with qualitative knowledge about relations between temporal intervals. However, the computational properties of the algebra and related-formalisms are known to be bad: most problems (like satisfiability) are NP-hard. This thesis contributes to finding restrictions (as weak as possible) on Allen's algebra and related temporal formalisms (the point-interval algebra and extensions of Allen's algebra for metric time) for which the satisfiability problem can be computed in polynomial time. Another research area utilising temporal information is that of reasoning about action, which treats the problem of drawing conclusions based on the knowledge about actions having been performed at certain time points (this amounts to solving the infamous frame problem). One paper of this thesis attacks the computational side of this problem; one that has not been treated in the literature (research in the area has focused on modelling only). A nontrivial class of problems for which satisfiability is a polynomial-time problem is isolated, being able to express phenomena such as concurrency, conditional actions and continuous time.

Similar to temporal reasoning is the field of spatial reasoning, where spatial instead of temporal objects are the field of study. In two papers, the formalism RCC-5 for spatial reasoning, very similar to Allen's algebra, is analysed with respect to tractable subclasses, using techniques from temporal reasoning.

Finally, as a spin-off effect from the papers on spatial reasoning, a technique employed therein is used for finding a class of intuitionistic logic for which computing inference is tractable.

Place, publisher, year, edition, pages
Linköping: Linköping University, 1997. p. 22
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 498
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-182547 (URN)9172190191 (ISBN)
Public defence
1997-10-28, Planck, Hus F, Linköpings universitet, Linköping, 16:00
Note

All or some of the partial works included in the dissertation are not registered in DIVA and therefore not linked in this post.

This work was partially supported by the Swedish Research Council for the Engineering Sciences (TFR), grant 93-270.

Available from: 2022-01-26 Created: 2022-01-26 Last updated: 2022-01-26Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records

Bjäreland, Marcus

Search in DiVA

By author/editor
Bjäreland, Marcus
By organisation
Department of Computer and Information ScienceThe Institute of TechnologyKPLAB - Knowledge Processing Lab
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

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