ERA

Download the full-sized PDF of The Design and an Experimental Analysis of Algorithms for Temporal ReasoningDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3KS6J811

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

The Design and an Experimental Analysis of Algorithms for Temporal Reasoning Open Access

Descriptions

Author or creator
van Beek, Peter
Manchak, Dennis W.
Additional contributors
Subject/Keyword
Temporal reasoning
interval-based
Type of item
Report
Language
English
Place
Time
Description
Technical report TR93-16. Many applications -- from planning and scheduling to problems in molecular biology -- rely heavily on a temporal reasoning component. In this paper, we discuss the design and an empirical analysis of algorithms for a temporal reasoning system based on Allen's influential interval-based framework for representing temporal information. At the core of the system are algorithms for determining whether the temporal information is consistent, and, if so, finding one or more scenarios that are consistent with the temporal information. Two important algorithms for these tasks are a path consistency algorithm and a backtracking algorithm. For the path consistency algorithm, we develop techniques that can result in up to a ten-fold speedup over an already highly optimized implementation. For the backtracking algorithm, we develop variable and value ordering heuristics that are shown empirically to dramatically improve the performance of the algorithm. As well, we show how the backtracking search problem can be reformulated to reduce the time and space requirements of the backtracking search. Taken together, the techniques we develop allow a temporal reasoning component to solve problems that are of practical size.
Date created
1993
DOI
doi:10.7939/R3KS6J811
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-30T22:24:29.879+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 369851
Last modified: 2015:10:12 20:25:47-06:00
Filename: TR93-16.pdf
Original checksum: 62b6fdcc2c1a6e5daf2945d6e06878bf
Well formed: true
Valid: true
Page count: 20
Activity of users you follow
User Activity Date