Point Algebras for Temporal Reasoning: Algorithms and Complexity
2003 (English)In: Artificial Intelligence, ISSN 0004-3702, Vol. 149, no 2, 179-220 p.Article in journal (Refereed) Published
We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.
Place, publisher, year, edition, pages
2003. Vol. 149, no 2, 179-220 p.
Temporal reasoning, Point algebras, Constraint satisfaction
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-13500DOI: 10.1016/S0004-3702(03)00075-4OAI: oai:DiVA.org:liu-13500DiVA: diva2:20870