A Simple Temporal Network with Uncertainty (STNU) is a structure for representing and reasoning about temporal constraints and uncontrollable-but-bounded temporal intervals called contingent links. An STNU is called dynamically controllable (DC) if there exists a strategy for executing its time-points that guarantees that all of the constraints will be satisfied no matter how the durations of the contingent links turn out. Recent work has shown an important connection between the dynamic controllability of STNUs and features of their associated graphs. In particular, an STNU is dynamically controllable if and only if it has no SRN loops---that is, ``semi-reducible'' loops having negative ``reduced path length''. Morris exploited the structure of such loops to yield an O(N4)-time DC-checking algorithm, the fastest yet reported in the literature. (N is the number of time-points in the network.) This talk continues the exploration of the structure of SRN loops in STNU graphs with the aim of further improving the performance of DC-checking algorithms. First, a notion of indivisibility for SRN loops is defined. Next, the number of occurrences of ``lower case'' edges in any indivisible SRN loop is shown to be at most 2^K - 1, where K is the number of contingent links in the network. This upper bound is proved to be tight by providing a recursive procedure for constructing indivisible SRN loops---called magic loops---that contain exactly 2^K - 1 occurrences of ``lower case'' edges. Finally, the upper bound is exploited to generate an O(N3)-time pre-processing step for Morris' algorithm that for certain networks reduces the DC-checking time from O(N4) to O(N3). Thus, the talk includes both theoretical and practical contributions. On the theoretical side, it deepens our understanding of the structure of SRN loops in STNU graphs. On the practical side, it demonstrates new ways in which the structure of such loops can be exploited to speed up existing DC-checking algorithms.
Strada le Grazie 15
VAT number 01541040232
Italian Fiscal Code 93009870234
© 2020 | Verona University | Credits