Backtracking Tree-Decomposition Method with Complete Independence for Workflow Satisfiability Decision (≠)

ZHAI Zhinian, LU Yahui, YU Fahong, GAO Huimin

1. 1. School of Information and Electronic Engineering, Zhejiang University of Science and Technology, Hangzhou 310023, China
2. School of Computer and Software, Shenzhen University, Shenzhen, Guangdong 518060, China
3. College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing, Zhejiang 314001, China
4. College of Mechanical and Electrical Engineering, Jiaxing University, Jiaxing, Zhejiang 314001, China
• Online:2018-12-01 Published:2018-12-07

工作流可满足决策（≠）的完备独立树分解回溯法

1. 1. 浙江科技学院 信息与电子工程学院，杭州 310023
2. 深圳大学 计算机与软件学院，广东 深圳 518060
3. 嘉兴学院 数理与信息工程学院，浙江 嘉兴 314001
4. 嘉兴学院 机电工程学院，浙江 嘉兴 314001

Abstract:

Exclusion constrained workflow satisfiability decision is an important problem that is concerned with the feasibility of secure business. Its representative algorithms so far are seriously out-of-balance between the theoretical and practical performance, or time and space cost. According to its low density of constraints, Jegou??s backtracking tree decomposition method is used to address the above issue. However, its concept of sub-problem independence is deduced only from the property of constraint irrelevance and has no guarantee to the compatibility between partial solutions. A complete sub-problem independence with a caching principle for partial solutions is set up from the view of both variable non-intersection and constraint irrelevance. A corresponding algorithm is designed and its correctness is proven via a method of alternating induction. Its time complexity is [O*(|S|3×dW+1)] which is conditionally lower than the most optimal time [O*(2|S|(|X|+|U|2))] so far, where S, d, W are the set of steps, the maximum scale of authorization lists for steps and the tree-decomposition width. Experiments show that, under the condition of low constraint density, the algorithm has remarkable time efficiency than the algorithms with the best theoretical or practical performance, while no quite much space cost is paid.