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 socalled epsilonDCchecking problem. This paper proves that the epsilonDCchecking problem for CSTNs can be reduced to the standard DCchecking problem for CSTNs  without incurring any computational cost. Given any CSTN S with k observation timepoints, the paper defines a new CSTN S_0 that is the same as S, except that for each observation timepoint P? in S: (i) P? is demoted to a nonobservation timepoint in S_0; and (ii) a new observation timepoint P_0?, constrained to occur exactly epsilon units after P?, is inserted into S_0. The paper proves that S is epsilonDC if and only if S_0 is (standard) DC, and that the application of the epsilonDCchecking constraintpropagation rules to S is equivalent to the application of the corresponding (standard) DCchecking constraintpropagation 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 DCchecking it incurs no computational cost as the sizes of the instances increase.
BibTeX  Entry
@InProceedings{hunsberger_et_al:LIPIcs:2018:9780,
author = {Luke Hunsberger and Roberto Posenato},
title = {{Reducing epsilonDC Checking for Conditional Simple Temporal Networks to DC Checking}},
booktitle = {25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
pages = {15:115:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770897},
ISSN = {18688969},
year = {2018},
volume = {120},
editor = {Natasha Alechina and Kjetil N{\o}rv{\aa}g and Wojciech Penczek},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9780},
URN = {urn:nbn:de:0030drops97808},
doi = {10.4230/LIPIcs.TIME.2018.15},
annote = {Keywords: Conditional Simple Temporal Networks, Dynamic Consistency, Temporal Constraints}
}
Keywords: 

Conditional Simple Temporal Networks, Dynamic Consistency, Temporal Constraints 
Collection: 

25th International Symposium on Temporal Representation and Reasoning (TIME 2018) 
Issue Date: 

2018 
Date of publication: 

08.10.2018 