Temporal Reasoning
-
Kovarik Jr., V. J., and Gonzalez, A.J., "An Interval-based
Temporal Algebra Based on Binary Encoding of Point Relations,"
International Journal of Inteilligent Systems, 2000.
[
ABSTRACT
|
FULL DOCUMENT ] (Full document will be loaded onto a new page.)
This paper presents a method for representing temporal interval relations using a bit-encoded form of the relationships between interval end-points. The set of bit patterns for each interval relationship yields a unique, single-byte signature that forms the basis of a binary temporal algebra. Also presented is a matrix multiplication algorithm for computing transitive relations based on the definition of sum and product operations for the bit-encoded relation signatures. This bit-encoding encompasses the representation of unknown relations between endpoints of two intervals and captures ambiguities within a temporal system while providing an efficient binary algebra. Finally, an algorithm to compute the transitive closure over a set of intervals forming a temporal system is presented. The algorithm’s complexity is analyzed and is O(n 3 ), worst case, where n is the number of temporal intervals within the system. Empirical observations indicate that the closure algorithm completes in O(n 2 ) time, on average. The small memory footprint for the bit-code, the algorithmic transitive relation calculation, and the closure algorithm, together, form an efficient method for providing machine-based temporal reasoning capabilities.