LIPIcs.TIME.2018.14.pdf
- Filesize: 0.59 MB
- 17 pages
Document
Sound-and-Complete Algorithms for Checking the Dynamic Controllability of Conditional Simple Temporal Networks with Uncertainty
Authors
Roberto Posenato 
-
Part of:
Volume:
25th International Symposium on Temporal Representation and Reasoning (TIME 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Temporal Representation and Reasoning (TIME) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-10-08
File
Document Identifiers
Author Details
Cite AsGet BibTex
Luke Hunsberger and Roberto Posenato. Sound-and-Complete Algorithms for Checking the Dynamic Controllability of Conditional Simple Temporal Networks with Uncertainty. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.TIME.2018.14
https://doi.org/10.4230/LIPIcs.TIME.2018.14
Abstract
A Conditional Simple Temporal Network with Uncertainty (CSTNU) is a data structure for representing and reasoning about time. CSTNUs incorporate observation time-points from Conditional Simple Temporal Networks (CSTNs) and contingent links from Simple Temporal Networks with Uncertainty (STNUs). A CSTNU is dynamically controllable (DC) if there exists a strategy for executing its time-points that guarantees the satisfaction of all relevant constraints no matter how the uncertainty associated with its observation time-points and contingent links is resolved in real time. This paper presents the first sound-and-complete DC-checking algorithms for CSTNUs that are based on the propagation of labeled constraints and demonstrates their practicality.
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
- Temporal Networks
- Conditional Simple Temporal Problem with Uncertainty
- Dynamic Controllability
- Checking Algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads