中文摘要：

工作流可满足性（WS）是资源分配对访问控制（AC）策略提出的基本要求.相关工作主要围绕WS决策问题展开,通过找到一个具体的解来说明AC策略的正确性.然而为了进一步验证AC策略在资源异常情况下的合理性,统计所有解的数量将更有帮助.本文对互斥和绑定约束下的WS计数问题进行研究,通过构造从典范性#P完全问题#3SAT到该问题的多项式计数归约,证明其属于#P完全问题,为其恰当地求解奠定了理论基础.

英文摘要：

Workflow satisfiability （WS） is an essential claim to access control （AC） policies from the view of resource allocation. So far,the related researches are concentrated on the decision problem of WS, which finds a single solution to show the correctness of an AC policy. However, to further verify its rationality under resource exception, and to count all the solutions will be more useful. In this paper, the counting problem of WS with exclusion and binding constraints is addressed. The problem is proved to be #P complete by constructing a polynomial time counting reduction from the well-known #P complete problem of #3 SAT to it, and then gets a theoretical basis to be solved appropriately.