On the Complexity of Temporal Controllabilities for Workflow Schemata

Recently, different kinds of "controllability" have been proposed for workflow schemata modeling real world processes made of tasks and coordination activities. Temporal controllability is the capability of executing a workflow for all possible durations of all tasks satisfying all temporal constraints. Three different types of controllability are possible -- strong controllability, history-dependent controllability, and weak controllability -- and a general exponential-time algorithm to determine the kind of controllability has been proposed. In this paper we analyze the computational complexity of the temporal controllability problem to verify the quality of proposed algorithms. We show that the weak controllability problem is \coNP-complete, while strong controllability problem is in Σ_2^P and it is coNP-hard. Regarding the history-dependent controllability problem, we are able to show that it is a PSPACE problem but further research is required to determine its hardness characterization.