Reducing epsilon-DC Checking for Conditional Simple Temporal Networks to DC Checking

Authors Luke Hunsberger, Roberto Posenato



PDF
Thumbnail PDF

File

LIPIcs.TIME.2018.15.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Luke Hunsberger
  • Department of Computer Science, Vassar College, NY, USA
Roberto Posenato
  • Department of Computer Science, University of Verona, Verona, Italy

Cite As Get BibTex

Luke Hunsberger and Roberto Posenato. Reducing epsilon-DC Checking for Conditional Simple Temporal Networks to DC Checking. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.TIME.2018.15

Abstract

Recent work on Conditional Simple Temporal Networks (CSTNs) has introduced the problem of checking the dynamic consistency (DC) property for the case where the reaction time of an execution strategy to observations is bounded below by some fixed epsilon > 0, the so-called epsilon-DC-checking problem. This paper proves that the epsilon-DC-checking problem for CSTNs can be reduced to the standard DC-checking problem for CSTNs - without incurring any computational cost. Given any CSTN S with k observation time-points, the paper defines a new CSTN S_0 that is the same as S, except that for each observation time-point P? in S: (i) P? is demoted to a non-observation time-point in S_0; and (ii) a new observation time-point P_0?, constrained to occur exactly epsilon units after P?, is inserted into S_0. The paper proves that S is epsilon-DC if and only if S_0 is (standard) DC, and that the application of the epsilon-DC-checking constraint-propagation rules to S is equivalent to the application of the corresponding (standard) DC-checking constraint-propagation rules to S_0. Two versions of these results are presented that differ only in whether a dynamic strategy for S_0 can react instantaneously to observations, or only after some arbitrarily small, positive delay. Finally, the paper demonstrates empirically that building S_0 and DC-checking it incurs no computational cost as the sizes of the instances increase.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Temporal reasoning
  • Theory of computation → Network optimization
  • Theory of computation → Dynamic graph algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • Conditional Simple Temporal Networks
  • Dynamic Consistency
  • Temporal Constraints

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail