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.