Counting Workflow Satisfiability(≠,=) and Its #P Completeness

ZHAI Zhi-nian; LU Ya-hui; YU Fa-hong; ZHOU Wu-jie; XIANG Jian; WU Ming-wei

doi:10.3969/j.issn.0372-2112.2017.03.015

您当前的位置：

首页 >

文章列表页 >

Counting Workflow Satisfiability(≠,=) and Its #P Completeness

更新时间：2025-07-16

- Counting Workflow Satisfiability(≠,=) and Its #P Completeness
- Acta Electronica Sinica Vol. 45, Issue 3, Pages: 605-611(2017)
- 作者机构：
  
  1. 浙江科技学院信息与电子工程学院,浙江,杭州,310023
  2. 深圳大学计算机学院,广东,深圳,518060
  3. 嘉兴学院数理与信息学院,浙江,嘉兴,314001
  4. 浙江科技学院信息与电子工程学院,浙江,杭州,310023
  5. 深圳大学计算机学院,广东,深圳,518060
  6. 嘉兴学院数理与信息学院,浙江,嘉兴,314001
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2017.03.015
  CLC： TP309
- Published Online：25 March 2017，
  
  Published：2017
- 稿件说明：
移动端阅览
ZHAI Zhi-nian, LU Ya-hui, YU Fa-hong, et al. Counting Workflow Satisfiability(≠,=) and Its #P Completeness[J]. Acta Electronica Sinica, 2017, 45(3): 605-611.
DOI：

ZHAI Zhi-nian, LU Ya-hui, YU Fa-hong, et al. Counting Workflow Satisfiability(≠,=) and Its #P Completeness[J]. Acta Electronica Sinica, 2017, 45(3): 605-611. DOI： 10.3969/j.issn.0372-2112.2017.03.015.

摘要

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

Abstract

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 #3SAT to it

and then gets a theoretical basis to be solved appropriately.

关键词

Keywords

references

Views

366

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Verification of(≠,=)Constrained Workflow Robustness Based on Satisfiability Counting

Joint Optimization of Distributed Intelligent Content Caching and User Association for CF-mMIMO

Robust Resource Allocation Algorithm for Secure Communication in LEO-Based Satellite Communication Systems

Random User Characteristics-Oriented Joint UAV Deployment and Resource Allocation Algorithm

Formalization and Verification of Privacy Preserving Protocol Based on User Consent

Related Author

ZHAI Zhi-nian

WANG Gang

ZHENG Zhi-jun

PENG Yan-bing

PAN Zhi-gang

WANG Zhong-peng

LI Yun

ZHANG Cheng-yu

Related Institution

浙江科技学院信息与电子工程学院

中国核电工程有限公司河北分公司民用工程研究设计所

School of Communications and Information Engineering, Chongqing University of Posts and Telecommunications

⁰