中文摘要：

工作流可满足性（WS）研究一定访问控制策略下的资源分配问题,其计数问题有利于判断工作流对资源异常情况的顽健性。本文研究互斥约束下的WS计数问题,通过多项式计数归约为约束可满足性计数问题,将经典的回溯树分解方法用于#WS（≠）求解。实验表明,改进后的算法降低了执行时间,相对于现有#WS（≠）算法,提出的算法对低密度约束下的工作流具有一定的综合性能优势。

英文摘要：

Workflow satisfiability（WS） concerns the issue of resource allocation under some access control policies.Counting all its solutions is advantaged to verify the robustness of a workflow to resource exceptions. The counting problem of WS with only exclusion constraints was addressed. The classic backtracking tree-decomposition method was employed to solve #WS（≠） via a polynomial-time counting reduction to a counting constraint satisfiability problem. Experiments show that, the proposed optimized algorithm declined in running time, and has well synthetical performance for workflows with low-density constraints compared to the existing #WS（≠） algorithms.