Iterative plan construction for the workflow satisfiability problem

Cohen, David, Crampton, Jason, Gagarin, Andrei ORCID: https://orcid.org/0000-0001-9749-9706, Gutin, Gregory and Jones, Mark 2014. Iterative plan construction for the workflow satisfiability problem. Journal of Artificial Intelligence Research 51 , pp. 555-577. 10.1613/jair.4435

Preview

PDF - Published Version Download (327kB) | Preview

Abstract

The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan - an assignment of tasks to authorized users - such that all constraints are satisfied. It is natural to see the WSP as a subclass of the Constraint Satisfaction Problem (CSP) in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive is that the number of tasks is usually very small compared to the number of users, so it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks. This novel approach to the WSP, using techniques from CSP, has enabled us to design a generic algorithm which is FPT for several families of workflow constraints considered in the literature. Furthermore, we prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. Lastly, we identify a new FPT constraint language, user-independent constraints, that includes many of the constraints of interest in business processing systems. We demonstrate that our generic algorithm has provably optimal running time O*(2^(klog k)), for this language, where k is the number of tasks.

Item Type:	Article
Date Type:	Published Online
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Publisher:	AI Access Foundation
ISSN:	1076-9757
Date of First Compliant Deposit:	1 June 2016
Last Modified:	05 May 2023 03:36
URI:	https://orca.cardiff.ac.uk/id/eprint/91299

Citation Data

Cited 39 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item