Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
复制标题
存在资历约束时工作流可满足性的固定参数可处理性
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Ramanujan
中科院分区：
文献类型：
--
作者：
J. Crampton;R. Crowston;G. Gutin;Mark Jones;M. Ramanujan
工作流可满足性问题涉及确定是否有可能找到授权用户的分配到工作流中的步骤，以满足所有约束。该问题是NP-困难的一般，但已知是固定参数的某些类的约束听话。已知的固定参数易处理性的结果依赖于对称性（在某种意义上）的约束。在本文中，我们提供的第一个结果，建立固定参数的可满足性问题时，约束是不对称的。特别是，我们引入了资历约束的概念，其中步骤的执行部分地由执行它们的用户的相对资历来确定。我们的研究结果需要新的技术，它利用树分解的二元关系定义的约束图。最后，我们建立了一个下界的工作流可满足性问题的硬度。
The workflow satisfiability problem is concerned with determining whether it is possible to find an allocation of authorized users to the steps in a workflow in such a way that all constraints are satisfied. The problem is NP-hard in general, but is known to be fixed-parameter tractable for certain classes of constraints. The known results on fixed-parameter tractability rely on the symmetry (in some sense) of the constraints. In this paper, we provide the first results that establish fixed-parameter tractability of the satisfiability problem when the constraints are asymmetric. In particular, we introduce the notion of seniority constraints, in which the execution of steps is determined, in part, by the relative seniority of the users that perform them. Our results require new techniques, which make use of tree decompositions of the graph of the binary relation defining the constraint. Finally, we establish a lower bound for the hardness of the workflow satisfiability problem.
DOI：
10.1145/2487222.2487226
发表时间：
2012-05
期刊：
ACM Trans. Inf. Syst. Secur.
影响因子：
--
作者：
J. Crampton;G. Gutin;Anders Yeo
通讯作者：
J. Crampton;G. Gutin;Anders Yeo
约束表达式和工作流可满足性
DOI：
10.1145/2462410.2462419
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Crampton J
通讯作者：
Crampton J