Title

An Interval-Based Temporal Algebra Based On Binary Encoding Of Point Relations

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 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(n3), worst case, where n is the number of temporal intervals within the system. Empirical observations indicate that the closure algorithm completes in O(n2) 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. © 2000 John Wiley & Sons, Inc.

Publication Date

1-1-2000

Publication Title

International Journal of Intelligent Systems

Volume

15

Issue

6

Number of Pages

495-523

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1002/(SICI)1098-111X(200006)15:6<495::AID-INT2>3.0.CO;2-C

Socpus ID

0347107329 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0347107329

This document is currently not available here.

Share

COinS