Please use this identifier to cite or link to this item: doi:10.22028/D291-24829
Title: On the computational complexity of temporal projection and some related problems
Author(s): Nebel, Bernhard
Bäckström, Christer
Language: English
Year of Publication: 1991
OPUS Source: Kaiserslautern ; Saarbrücken : DFKI, 1991
SWD key words: Künstliche Intelligenz
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: One kind of temporal reasoning is temporal projection -the computation of the consequences for a set of events. This problem is related to a number of other temporal reasoning tasks such as story understanding, plan validation, and planning. We show that one particular simple case of temporal projection on partially ordered events turns out to be harder than previously conjectured. However, given the restrictions of this problem, planning and story understanding are easy. Additionally, we show that plan validation, one of the intended applications of temporal projection, is tractable for an even larger class of plans. The incomplete decision procedure for the temporal projection problem that has been proposed by other authors, however, fails to be complete in the case where we have shown plan validation to be tractable.
Link to this record: urn:nbn:de:bsz:291-scidok-35779
Series name: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Series volume: 91-34
Date of registration: 16-May-2011
Faculty: SE - Sonstige Einrichtungen
Department: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
RR_91_34.pdf18,26 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.