Reasoning about partially ordered events

摘要

This paper describes a class of temporal reasoning problems involving events whose order is not completely known. We examine the complexity of such problems and show 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, we provide a partial decision procedure that reports useful results and runs in polynomial time.