You are here

An efficient method for representing and computing transitive closure over temporal relations

Download pdf | Full Screen View

Date Issued:
1994
Abstract/Description:
University of Central Florida College of Engineering Thesis; 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.
Title: An efficient method for representing and computing transitive closure over temporal relations.
20 views
5 downloads
Name(s): Kovarik, Vincent J., Author
Gonzalez, Avelino, Committee Chair
Engineering, Degree Grantor
Type of Resource: text
Date Issued: 1994
Publisher: University of Central Florida
Language(s): English
Abstract/Description: University of Central Florida College of Engineering Thesis; 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.
Identifier: CFR0001859 (IID), ucf:52919 (fedora)
Note(s): 1994-08-01
Ph.D.
Electrical and Computer Engineering
Doctorate
This record was generated from author submitted information.
Electronically reproduced by the University of Central Florida from a book held in the John C. Hitt Library at the University of Central Florida, Orlando.
Subject(s): Dissertations
Academic -- Engineering
Engineering -- Dissertations
Academic
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFR0001859
Restrictions on Access: public
Host Institution: UCF

In Collections