On the Satisfiability of Workflows with Release Points

Jason Crampton, Gregory Gutin, Remi Watrigant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

82 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationSACMAT '17 Abstracts
Subtitle of host publicationProceedings of the 22nd ACM on Symposium on Access Control Models and Technologies
Number of pages11
ISBN (Print)978-1-4503-4702-0
Publication statusPublished - Jun 2017

Cite this