Disjunctive Temporal Reasoning in Partially Ordered Models of Time

Mathias Broxvall and Peter Jonsson, Linköpings Universitet

Certain problems concerning 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 appropriate 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 algebra for total-ordered time contains two.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.