An interval-based temporal algebra based on binary encoding of point relations

    Authors

    V. J. Kovarik;A. J. Gonzalez

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Int. J. Intell. Syst.

    Keywords

    Computer Science, Artificial Intelligence

    Abstract

    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 end points of mig 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. (C) 2000 John Wiley & Sons, Inc.

    Journal Title

    International Journal of Intelligent Systems

    Volume

    15

    Issue/Number

    6

    Publication Date

    1-1-2000

    Document Type

    Article

    Language

    English

    First Page

    495

    Last Page

    523

    WOS Identifier

    WOS:000087165100002

    ISSN

    0884-8173

    Share

    COinS