|
Published Articles >> Table of Contents >> Abstract
10th International Symposium on Temporal Representation and Reasoning and Fourth International Conference on Temporal Logic
p. 147
Deciding consistency of a point-duration network with metric constraints
Isabel Navarrete, Universidad de Murcia
Abdul Sattar, Griffith University
Roque Marin, Universidad de Murcia
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TIME.2003.1214890
Send link to a friend
| Abstract |
|
We introduce a new model, MPDN, for quantitative temporal reasoning with points and durations, that supposes an extension of the TCSP formalism and previous point-duration network models. The problem of deciding consistency for a MPDN is shown to be NP-complete. So, we identify a tractable fragment, named simple MPDN, that subsumes the STP model and allows for duration reasoning. Necessary and sufficient conditions for deciding consistency of a simple MPDN are used to design an algorithm for consistency checking, whose time complexity is cubic in the number of variables. This is a significant improvement, not only in computational complexity but also in simplicity, over previous non-specific algorithms that can be applied to solve the consistency problem.
|
 Additional Information
|
Index Terms- Temporal representation and reasoning
in AI, temporal constraint reasoning, point and duration
reasoning
Citation:
Isabel Navarrete, Abdul Sattar, Roque Marin,
"Deciding consistency of a point-duration network with metric constraints,"
time-ictl,
p. 147,
10th International Symposium on Temporal Representation and Reasoning and Fourth International Conference on Temporal Logic,
2003
|
|
