An Efficient Method for Representing and Computing Transitive Closure over Temporal Relations

Author

Vincent J. Kovarik, University of Central Florida

Abstract

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(n³) 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(n³) as the worst case rather than the average. Data gathered shows the closure algorithm to run in O(n²) 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 n², 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.

Notes

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

Graduation Date

1994

Semester

Summer

Advisor

González, Avelino J.

Degree

Doctor of Philosophy (Ph.D.)

College

College of Engineering

Department

Department of Electrical and Computer Engineering

Degree Program

Engineering

Format

PDF

Language

English

Rights

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

None

Access Status

Doctoral Dissertation (Open Access)

Identifier

DP0001859

STARS Citation

Kovarik, Vincent J., "An Efficient Method for Representing and Computing Transitive Closure over Temporal Relations" (1994). Retrospective Theses and Dissertations. 3471.
https://stars.library.ucf.edu/rtd/3471

Contributor (Linked data)

Gonzalez, Avelino J. [VIAF]

Gonzalez, Avelino J. [LC]

University of Central Florida. College of Engineering [VIAF]

University of Central Florida. College of Engineering [LC]

Accessibility Status

Searchable text