Reasoning about partially ordered events
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.
- scientific article; zbMATH DE number 3599517 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- On the representation and querying of sets of possible worlds
- Planning for conjunctive goals
- STRIPS: A new approach to the application of theorem proving to problem solving
- A unifying approach to temporal constraint reasoning
- Modeling a dynamic and uncertain world. I: Symbolic and probabilistic reasoning about change
- On the computational complexity of temporal projection, planning, and plan validation
- The computational complexity of propositional STRIPS planning
- Qualitative and quantitative simulation: bridging the gap
- Reasoning about causality between distributed nonatomic events
- Querying temporal and spatial constraint networks in PTIME
- Complexity, decidability and undecidability results for domain-independent planning
- On the nature and role of modal truth criteria in planning
- Temporal reasoning based on semi-intervals
- Partial Orders, Event Structures and Linear Strategies
- scientific article; zbMATH DE number 1538060 (Why is no real title available?)
- An initial study of time complexity in infinite-domain constraint satisfaction
- Solving infinite-domain CSPs using the patchwork property
- Complexity classification transfer for CSPs via algebraic products
- Point algebras for temporal reasoning: Algorithms and complexity
This page was built for publication: Reasoning about partially ordered events
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1263999)
