The need for temporal reasoning is found throughout the engineering disciplines. James Allen introduced a representation for temporal reasoning based upon the concept of intervals. This approach provides a rich set of temporal relations for reasoning over events and changes in state. The full temporal algebra is NP-complete however. The algorithm developed by Allen executes in 0(n3) time but only ensures consistency between any three intervals.
This research presents an approach to representing interval relations as a bit-encoded form which captures the relationships between the end-points of the intervals. A bit-algebra is then defined which provides an algorithmic method for computing transitive relations without requiring the table lookup of Allen's algorithm. By reducing the set of ambiguous interval representations to the set of relationships which have unknown temporal extent, a robust subset of the full algebra is defined which maintains the direct computation of transitive relationships.
A transitive closure algorithm is then developed which has the property of being 0(n3) as the worst case rather than the average. Data gathered shows the closure algorithm to run in O(n2) time for most cases. The bit code for a relationship is a single byte. Thus, the storage requirements for a temporal system of n intervals is n2, a relatively small memory demand. The small memory footprint, coupled with the efficient transitive relation calculation and closure algorithm together form an efficient method for providing temporal reasoning capabilities to a wide range of applications.
If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu
González, Avelino J.
Doctor of Philosophy (Ph.D.)
College of Engineering
Department of Electrical and Computer Engineering
Written permission granted by copyright holder to the University of Central Florida Libraries to digitize and distribute for nonprofit, educational purposes.
Length of Campus-only Access
Doctoral Dissertation (Open Access)
Kovarik, Vincent J., "An Efficient Method for Representing and Computing Transitive Closure over Temporal Relations" (1994). Retrospective Theses and Dissertations. 3471.
Contributor (Linked data)
Gonzalez, Avelino J. [VIAF]
Gonzalez, Avelino J. [LC]