Abstract
Workflow is a formal description of a process or processes. There exist tools for interactive and visual editing of workflows such as the FlowOpt Workflow Editor.
During manual editing of workflows, it is common to introduce flaws such as cycles of activities. Hence one of the required features of workflow management tools is verification of workflows, which is a problem of deciding whether the workflow describes processes that can be realized in practice.
In this paper we deal with the theoretical complexity of verifying workflows with a nested structure and with extra constraints. The nested structure forces users to create valid workflows but as we shall show, introduction of extra causal, precedence, and temporal synchronization constraints makes the problem of deciding whether the workflow represents a realizable process hard.
In particular, we will show that this problem is NP-complete.