Proceedings:
Knowledge Representation and Reasoning
Volume
Issue:
Proceedings of the AAAI Conference on Artificial Intelligence, 17
Track:
Reasoning about Actions and Time
Downloads:
Abstract:
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.
AAAI
Proceedings of the AAAI Conference on Artificial Intelligence, 17