| 講演抄録／キーワード |
| 講演名 |
2006-01-27 10:10
ワークフローネットの健全性と並列度について
○金子侑史・山口真悟・葛 崎偉・田中 稔（山口大） |
| 抄録 |
（和） |
本稿ではワークフロー(WF)ネットの健全性と並列度について議論する。
まずWFネットの並列性を評価する尺度として並列度を定義する。
次に並列度は健全なWFネットにおいて重要な意味をもつことから、
WFネットの各サブクラスの健全性について議論する。
そして健全なサブクラスに対して並列度を計算する問題に取り組み、
その問題がNP完全であるクラスを示す。
そしてそれより小さいサブクラスには並列度を多項式時間で計算するアルゴリズムを与える。 |
| （英） |
This paper discusses soundness and parallel degree of workflow nets (WF-nets).
We first define parallel degree that is a measure for evaluating parallelism in a WF-net.
Parallel degree is significant for sound WF-nets, so we discuss soundness for each subclass of WF-nets.
Next for each sound subclass, we tackle a problem of computing parallel degree.
We show that the problem is NP-complete for a certain subclass.
Then we give a polynomial time algorithm of computing parallel degree for smaller subclasses. |
| キーワード |
（和） |
ワークフローネット / 並列度 / 健全性 / 計算複雑さ / NP完全性 / / / |
| （英） |
workflow net / parallel degree / soundness / computation complexity / NP-completeness / / / |
| 文献情報 |
信学技報, vol. 105, 2006年1月. |
| 資料番号 |
|
| 発行日 |
2006-01-20 (CST) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|