Disjunctive Temporal Reasoning in Partially Ordered Models of Time

Certain problems in connection with, for example, cooperating agents and distributed systems require reasoning about time which is measured on incomparable or unsynchronized time scales. In such situations, it is sometimes approporiate to use a temporal model that only provides a partial order on time points. We study the computational complexity of partially ordered temporal reasoning in expressive formalisms consisting of point algebras extended with disjunctions. We show that the resulting algebra for partially ordered time contains four maximal tractable subclasses while the equivalent algebra for total-ordered time contains two.

Authors

• Mathias Broxvall and Peter Jonsson Linköpings Universitet

Keywords

No keywords are indexed for this paper.