Dynamic Controllability of Conditional Simple Temporal Networks Is PSPACE-complete

Even after the proposal of various solution algorithms, the precise computational complexity of checking whether a Conditional Temporal Network is Dynamically Controllable had still remained widely open. This issue gets settled in this paper which provides constructions, algorithms, and bridging lemmas and arguments to formally prove that: (1) the problem is PSPACE-hard, and (2) the problem lies in PSPACE.

• Publication year

  2016

• Venue

  Time

• Publication date

  2016-08-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIME.2016.17arXiv 1608.08545
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Sound-and-Complete Propagation-Based Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks

  2015influential reference
• Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: A Singly-Exponential Time DC-checking

  2015cited by this paper
• Sound and Complete Algorithms for Checking the Dynamic Controllability of Temporal Networks with Uncertainty, Disjunction and Observation

  2014cited by this paper
• An Algorithm for Checking the Dynamic Controllability of a Conditional Simple Temporal Network with Uncertainty

  2013cited by this paper
• The Dynamic Controllability of Conditional STNs with Uncertainty

  2012cited by this paper
• CTP: A New Constraint-Based Formalism for Conditional, Temporal Planning

  2003influential reference
• Dynamic Control Of Plans With Temporal Uncertainty

  2001cited by this paper
• Handling contingency in temporal constraint networks: from consistency to controllabilities

  1999cited by this paper
• Temporal Constraint Networks

  1989cited by this paper

• Dynamic Controllability of Parameterized CSTNUs

  2023cites this paper
• CSTNU Tool: A Java library for checking temporal networks

  2022cites this paper
• Faster Dynamic-Consistency Checking for Conditional Simple Temporal Networks

  2020cites this paper
• Temporal and Resource Controllability of Workflows Under Uncertainty

  2019cites this paper
• Complexity Bounds for the Controllability of Temporal Networks with Conditions, Disjunctions, and Uncertainty

  2019influential citation
• Conditional Simple Temporal Networks with Uncertainty and Decisions

  2019cites this paper
• Conditional Simple Temporal Networks with Uncertainty and Resources

  2019influential citation
• Propagating Piecewise-Linear Weights in Temporal Networks

  2019influential citation
• Extending Conditional Simple Temporal Networks with Partially Shrinkable Uncertainty

  2018cites this paper
• Incorporating Decision Nodes into Conditional Simple Temporal Networks

  2017cites this paper
• A Streamlined Model of Conditional Simple Temporal Networks - Semantics and Equivalence Results

  2017cites this paper
• 10 : 2 A Streamlined Model of Conditional Simple Temporal Networks 1 Introduction

  2017cites this paper