Publikation
On the Computational Complexity of Temporal Projection and some related Problems
Bernhard Nebel; Christer Bäckström
DFKI, DFKI Research Reports (RR), Vol. 91-34, 1991.
Zusammenfassung
One kind of temporal reasoning ist temporal projection--the computation of the consequences for a set of events. This problem is related to a number of other temporal reasoning trasks 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 imcomplete decision procedure for the temporal projection problem that has been proposed by other authers, however, fails to be complete in the case where we have shown plan validation to be tractable.