On the Satisfiability of Workflows with Release Points

There has been a considerable amount of interest in recent years in the problem of workflow satisfiability, which asks whether the existence of constraints in a workflow specification means that it is impossible to allocate authorized users to each step in the workflow. Recent developments have seen the workflow satisfiability problem (WSP) studied in the context of workflow specifications in which the set of steps may vary from one instance of the workflow to another. This, in turn, means that some constraints may only apply to certain workflow instances. Inevitably, WSP becomes more complex for such workflow specifications. In this paper, we present the first fixed parameter algorithms to solve WSP for workflow specifications of this type. Moreover, we significantly extend the range of constraints that can be used in workflow specifications of this type.