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

摘要

ワークフローは法律の改正や市場の拡大などに適合するよう変更されることがある．その際，事業の継続性の観点から，変更後のワークフローは変更前のワークフローの振舞いを保持しなければならない．この性質は振舞い継承と呼ばれる．振舞い継承を判定する問題は決定可能であるが，手に負えないことが知られている．本稿では，ワークフローの変更を構造上の拡張に限定することによって，振舞い継承の一つであるProtocol継承を多項式時間で判定するための必要十分条件とアルゴリズムを明らかにした．