一在Coloured Petri Nets中的錯誤找尋與校正之方法

Abstract

Coloured Petri nets及其分析技術可應用於協助尋找工作流程的缺陷，而於一coloured Petri net中可能存在一個或多個錯誤，但目前的存在的演算法並無法完全地檢測出這些錯誤。於本論文中，定義了三種尚未被分析過的錯誤，分別為place faults、amount transition faults及colour transition faults。本文所提出之方法為將一coloured Petri net轉為另一separate的coloured Petri net，並且在separate的coloured Petri net上之所有marking將維持某相同的編碼規則相對於原始的coloured Petri net上之所有marking。而後，若coloured Petri net進入錯誤狀態時便可透過parity check之方式將其找尋出來並校正。在加入2k places與其相對應的arcs後，最多可同時在一coloured Petri net上找尋並校正k place faults、x amount transition faults及k - x colour transition faults，其中 0 <= x <= k。此錯誤找尋與校正之方法的時間複雜度為O(kγ(α+β))，其中α、β及γ分別代表於一coloured Petri net中transitions、places及colours的數量。

Coloured Petri nets and related analysis techniques can be applied to help find the defects in workflows. One or more errors may exist in a coloured Petri net, but current algorithms can not detect them completely. In this thesis, three kinds of faults are defined, namely place faults, amount transition faults and colour transition faults, not analyzed before. A methodology provided in this thesis translating a coloured Petri net into a separate one, in which all the markings will keep the same encoding rule with all the markings in the original coloured Petri net. If the coloured Petri net results in faulty states, they can be identified and corrected via parity checks. After adding 2k places and their relative arcs, the coloured Petri net can be identified and corrected at most: k place faults, x amount transition faults and k - x colour transition faults concurrently, where 0 <= x <= k. The time complexity of the fault identification and correction method provided in this thesis is O(kγ(α+β)), where α, β and γ are the number of transitions, places and colour types in a coloured Petri net, respectively.