拡張自由選択ワークフローネットとそのサブネット間のProtocol継承の多項式時間判定について

摘要

A workflow may be changed to adapt to market growth, legal reform, and so on. In that case, the new workflow has to preserve the behavior of the old workflow for business continuity. This property is called behavioral inheritance. It is known that the verification problem on behavioral inheritance is decidable but is intractable. In this paper, limiting the change to workflows to extension on structure, we proposed a necessary and sufficient condition and a polynomial-time algorithm for solving the verification problem on behavioral inheritance (strictly speaking, protocol inheritance).%ワークフローは法律の改正や市場の拡大などに適合するよう変更されることがある.その際，事業の継続性の観点から，変更後のワークフローは変更前のワークフローの振舞いを保持しなければならない.この性質は振舞い継承と呼ばれる.振舞い継承を判定する問題は決定可能であるが，手に負えないことが知られている.本稿では，ワークフローの変更を構造上の拡張に限定することによって，振舞い継承の一つであるProtocol継承を多項式時間で判定するための必要十分条件とアルゴリズムを明らかにした.