Reasoning about partially ordered events (Q1263999)

The paper won the best paper award in the subfield ``Automated reasoning and planning'' at AAAI-87. The motivation for this research in temporal reasoning was pragmatic: to build a general temporal database facility for applications in planning, robotics, and decision support. But the problem of answering queries involving partially ordered events originated a deep theoretical investigation. The problem of reasoning with incomplete knowledge is in the background - the exact order in which events occur is not known. The basic reasoning problem authors are concerned with is as follows: starting with general knowledge about the cause-and-effect relationships of a given domain, and specific knowledge about a particular set of circumstances, infer what is true over certain intervals of time. Total orders consistent with the given partially ordered events are considered. The complexity of two basic decision problems involving quantification over total orders is examined. The problems consist in determining if a condition (formula) holds immediately following a specified event in some (eventually all) totally ordered extension of the given partial order. It is shown that for all but trivial cases these problems are likely to be intractable. As an alternative to a complete, but potentially exponential-time decision procedure, a partial decision procedure is presented that runs in polynomial time. Probabilistic decision procedures for the problem as a fruitful direction for further research are sketched, too. It may be possible to exploit the statistical regularities of certain restricted classes of temporal projection in order to provide good approximate solutions.