文献

J-GLOBAL ID：201702237394030621   整理番号：17A0158322

ワークフロー可到達性(≠)カウントの固定パラメータ線形アルゴリズム【JST・京大機械翻訳】

Fixed-Parameter Linear Algorithm for Counting Workflow Satisfiability (≠)

著者 (6件)： Zhai Zhinian (School of Information and Electronics Engineering, Zhejiang University of Science and Technology) ,  Lu Yahui (School of Computer and Software, Shenzhen University) ,  Zhou Wujie (School of Information and Electronics Engineering, Zhejiang University of Science and Technology) ,  Chen Zhihao (Center for Systems and Software Engineering, University of Southern California) ,  Wang Zhongpeng (School of Information and Electronics Engineering, Zhejiang University of Science and Technology) ,  Lin Jiang (School of Information and Electronics Engineering, Zhejiang University of Science and Technology)
資料名： Jisuanji Xuebao  (Jisuanji Xuebao)
巻： 39  号： 11  ページ： 2291-2306  発行年： 2016年 
JST資料番号： C2531A  ISSN： 0254-4164  CODEN： JIXUDT  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： ワークフローアクセス可能性(WS SATISFIABILITY,WS)(≠)は与えられた認可と排他制約の下での資源割当てが存在するかどうかを判定し、ワークフローアクセス制御における基本的な問題である。現在、具体的な解を探すことによって、この判定を完成させ、相応の問題をWS(≠)意思決定と呼び、既存の最低時間複雑度はO*(2(|)(|C|+|U|2))(S,C,Uはそれぞれステップ集合、セットセット、ユーザー集合)である。しかし、WS(≠)が解を持つ場合、ワークフロー認可計画は必ずしも合理的ではなく、資源異常に対してロバスト性が欠けている可能性がある。すべての解の個数を統計することができれば、WS(≠)が解を持つかどうかを判定できるだけではなく、また、計画のために重要な参考を提供することができ、相応の問題をWS(≠)計数と呼ぶ。本論文では,WS(≠)数の問題を提案し,BJORCLUNDの集合に対する重みづけとその結果により,その時間複雑度はO*(2(|S|)|U|),すなわち|は固定パラメータであり,|の線形時間分解能について)であることを証明した。これにより,現在のWS(≠)判定時間の複雑さを低減した。さらに,本論文では,高速動的計画法を提案し,BJORCLUNDの空間的利用を最適化し,このアルゴリズムの性能を改善したが,O*時間の複雑さは変化しなかった。ランダム合成データセットに関する実験結果は,提案したアルゴリズムが,以前の決定アルゴリズムと比較して,実行時間が平均93%減少し,ピーク空間が87%減少し,解の規模が44%増加することを示した。Data from the ScienceChina, LCAS. Translated by JST【JST・京大機械翻訳】

シソーラス用語： ロバスト性 ,  アクセシビリティ ,  意思決定 ,  *ワークフロー ,  制約条件 ,  動的計画法 ,  *線形性 ,  重みづけ ,  資源割付 ,  最適化 ,  許認可 ,  *アルゴリズム ,  アクセス制御
準シソーラス用語： 実行時間 ,  複雑度 , 【Automatic Indexing@JST】

著者キーワード (5件)： workflow ,  access control ,  resource allocation ,  satisfiability ,  separation of duty

分類 (3件)： 人工知能  (JE08000Z) ,  移動通信  (ND08030H) ,  計算機網  (JC03000K)

タイトルに関連する用語 (6件)： ワークフロー ,  可到達性 ,  カウント ,  パラメータ ,  線形 ,  アルゴリズム