ペトリネット

ペトリネットは、1962年にカール・アダム・ペトリによって発表された、離散分散システムを数学的に表現するための手法です。分散システムをモデリングする際に、注釈付きの有向2部グラフとして視覚的に表現できる点が特徴です。

ペトリネットの基本構造

ペトリネットは、以下の要素で構成される有向2部グラフ N = (P, T, A) によって表現されます。

プレース (Place, P): 円で表現されるノードで、システムの状態を表します。
トランジション (Transition, T): 棒または箱で表現されるノードで、システムのイベントを表します。
アーク (Arc, A): プレースからトランジションへ、またはトランジションからプレースへと向かう矢印で、ノード間の関係を表します。

トークンとマーキング

プレースにはトークンと呼ばれるものを置くことができます。プレース p ∈ P に非負整数 k が割り当てられている場合、プレース p は k 個のトークンでマーキングされていると言います。トークンは、プレース内に k 個の点で図示されます。マーキングは、ペトリネットにおけるシステムの状態を表しており、特に初期状態のマーキングを初期マーキングと呼びます。

トランジションの発火と状態遷移

ペトリネットの状態は、トランジションの発火によって変化します。トランジションが発火すると、入力側のプレースからトークンが消費され、出力側のプレースにトークンが生成されます。このプロセスを通じて、システムの状態が遷移していきます。

ペトリネットのサブクラス

ペトリネットには、特定の制約を持つサブクラスが存在します。

ステートマシン: 各トランジションから出るアーク、または各トランジションに入るアークが最大1本であるペトリネット。
マークグラフ: 各プレースから出るアーク、または各プレースに入るアークが最大1本であるペトリネット。

ペトリネットの応用分野

ペトリネットは、並行計算や性能評価、通信プロトコル、バイオインフォマティクスなど、幅広い分野で応用されています。特に、複雑なシステムの挙動をモデル化し、解析するのに適しています。

一般化されたペトリネット

ペトリネットは、カラーペトリネットなどのより一般的な形式に拡張されることもあります。カラーペトリネットでは、トークンに色や属性を持たせることができ、より複雑なシステムのモデリングが可能です。

ペトリネットと関連する概念

ペトリネットは、有限オートマトンやアクターモデル、プロセス計算、アクティビティ図、YAWL、BPELなど、様々なモデリング手法や概念と関連があります。これらの手法と組み合わせることで、より強力なシステム解析が可能になります。

ペトリネットの解析

ペトリネットは、到達可能性解析やライブネス解析などの手法を用いて解析することができます。これらの解析により、システムのデッドロックや無限ループなどの問題を検出できます。

参考文献

Petri Nets World: 国際的なペトリネットのポータルサイト。メーリングリストや参考文献が含まれています。
Petri Net Markup Language: XMLに基づくペトリネット交換用マークアップ言語。
exchangeable Routing Language: CiteSeerからの引用。
* Petri net: スカラーペディア百科事典のペトリネットの項目（英語）。

もう一度検索