ペトリネット
ペトリネットは、視覚的、数学的な離散事象システムをモデル化するツールの一つであり、 名前は創始者のカール・アダム・ペトリに由来する。
有向2部グラフ N = ( P , T , A ) {\displaystyle N=(P,T,A)} で表現され、 頂点集合の2分割 ( P , T ) {\displaystyle (P,T)} がそれぞれ、 プレース(丸で表記)、トランジション(棒または箱で表記) という2種類のノードに対応する。 アーク (矢印で表記) は、プレースから出てトランジションに入るか、 トランジションから出てプレースに入る。
あるプレース p ∈ P {\displaystyle p\in P} に対し、非負整数 k {\displaystyle k} が割り当てられたとき、 プレース p {\displaystyle p} は k {\displaystyle k} 個のトークンでマーキングされていると言い、 このときトークンはプレース p {\displaystyle p} 内の k {\displaystyle k} 個の点として図示される。 ペトリネットは、マーキングによりシステムの状態を表現し、 特に、マーキングの初期状態のことを初期マーキングと呼ぶ。 マーキングはトランジションの発火により遷移する。
ペトリネットのサブクラスとして、ステートマシンやマークグラフ等がある。 ステートマシンはそれぞれのトランジションから多くとも1本のアークが出るか、 それぞれのトランジションに多くとも1本のアークが入る。 マークグラフはそれぞれのプレースから多くとも1本のアークが出るか、 それぞれのプレースに多くとも1本のアークが入る。
また、モノイドの性質も持つ。