IDA Technical Reports: abstract

Nebel, B. and Bäckström, C. (1991). On the Computational Complexity of Temporal Projection and some Related Problems. Technical Report LiTH-IDA-R-91-34, Department of Computer and Information Science, Linköping University, Sweden. Also published as DFKI Research Report RR-91-34, German Research Center for Artificial Intelligence (DFKI), Saarbrucken, Germany. The results in this report has been divided into conference papers that will appear in proceedings of the AAAI-92, conference, San Jose, Ca USA, jul 12-17, 1992 and in proceedings of the ECAI-92 conference, Vienna, Austria, Aug 3-7, 1992 respectively and has been accepted for publication in Artificial Intelligence (ie.AI Journal). (bibtex),

Abstract: 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 applicationsof temporal projection, is tractable for an even larger class of plans. The incomplete decision procedure for the temporal projectionproblem that has been proposed by other authors, however, fails to becomplete in the case where we have shown plan validation to be tractable