Temporal Reasoning with Constraints on Fluents and Events

Abstract

We propose a propositional language for temporal reasoning that is computationally effective yet expressive enough to describe information about fluents, events and temporal constraints. Although the complete inference algorithm is exponential, we characterize a tractable core with limited expressibility and inferential power. Our results render a variety of constraint propagation techniques applicable for reasoning with constraints on fluents. 1 Introduction Consider the issues raised by the following "story". At 8:00 the microfilm was deposited in the safe and at 11:00 the microfilm was gone. John was at the bar between 8:10 - 8:30 and between 9:10-12:00. He was also at the poker table between 8:35 - 9:00. Fred was at the bar between 8:30 - 10:00 and between 10:45 - 12:00. The bar opened at 7:30 and closed at 12:00. We know that at least 15 minutes are required to take the microfilm and return to the bar. Given the story above, we are interested in answering queries such ...