中文摘要：

工作流可满足性（Workflow Satisfiability,WS） （≠） 判定给定授权和互斥约束下的资源分配是否存在,是工作流访问控制中的基本问题.目前可以通过寻找一个具体的解来完成该判定,相应问题称为WS（ ≠ ） 决策,现有的最低时间复杂度为0^#（2｜s｜（｜C｜ ＋ ｜U｜2））（S ,C ,L/分别为步骤集、约束集、用户集）.然而,仅WS（ ≠） 有解时,工作流授权规划未必合理,对资源异常可能缺乏鲁棒性.若能统计所有解的个数,不仅可判定WS（ ≠） 有解与否,还能为授权规划提供重要的参考,相应的问题称为WS（ ≠ ） 计数.该文提出WS（ ≠ ） 计数问题,并根据Bjorclund关于集合划分权重和的结果证明其时间复杂度为O^#（2｜s｜ ｜U｜）,即其以｜S｜为固定参数,关于｜L/｜线性时间可解,由此降低了当前的WS（ ≠ ） 判定时间复杂度.进而,该文提出了-种快速的动态规划递推式,并全面优化Bjordund方法的空间利用方式,使该文算法的实际性能随之提高,而时间复杂度不变.随机合成数据集上的实验表明,该文最终的计数算法相对前述决策算法,执行时间平均降低了93% ,峰值空间平均降低了87% ,而求解规模提高了44%.