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.

On the Complexity of Temporal Controllabilities for Workflow Schemata

COMBI, Carlo;POSENATO, Roberto
2012

Abstract

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.
9781450308571
temporal workflow analysis; computational complexity; temporal controllability; temporal constraint networks
File in questo prodotto:
File Dimensione Formato  
p60-combi.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Dominio pubblico
Dimensione 449.17 kB
Formato Adobe PDF
449.17 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/394338
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact