2 Occurrence nets
Let \(N\) be a net. The immediate dependency relation \({\lt}_N ⊆ (α ∪ β) × (α ∪ β)\) is defined by the set
We denote the transitive closure of \({\lt}_N\) as the causal relation \(≺_N\).
A relation \(≼ _N\) is causal preorder if it is the reflexive-transitive closure of \({\lt}_N\) (from Definition 26).
Let \(N\) be a net and \(a ∈ α\) a place. If \(a ∈ \mathsf{minimal}(a)\) and \(x ≠ a\) then \(¬ (x≼ a)\).
Two different transtions \(t,t'\) are in immediate conflict if \(•t ∩ •t ≠ ∅\). Let’s denote this relation as \(t ♯₀ t'\).
Two elements \(x,y ∈ α ∪ β\) are in conflict if there exist two transtions \(t,t'\) that \(t≼ x\), \(t'≼ y\) and \(t ♯₀ t'\). We denote a conflict relation of \(x,y\) as \(x ♯ y\).
A place \(a\) has a backward conflict if it is produced by two distinct transitions, i.e., \(\exists t₁, t₂, (t₁ ≠ t₂) ∧ (a ∈ t₁• ) ∧ (p ∈ t₂•)\).
A net is acyclic if its causal relation is irreflexive, i.e., there is no \(x ∈ α ∪ β\) such that \(x ≺_N x\).
A marked net \((N,m_0)\) is an occurrence net if it satisfies the following statements:
\(N\) is acyclic;
there is no self-conflict, i.e., \(¬(t ♯ t)\) for all transition \(t\);
there is no backward conflict;
\(N\) is 1-safe, i.e., marking is a set;
the initial marking is the set of initial places, i.e., \(m₀\) is minimal (Definition 6).
A marked net \((N,m₀)\) is called marked ocurrence if \(N\) is occurrence, \(m₀\) has no duplicates and each place \(p ∈ m₀\) implies \(p ∈ \textsf{minimal }N\).
Two different elements \(x,y∈ α ∪ β\) are concurrent in \(N\) if \(¬ (x≼ y)\), \(¬ (y ≼ x)\) and \(¬ (x ♯ y)\). We denote the concurrency between these elements as \(x\textsf{ co }y\).
A multiset \(m\) is concurrent in \(N\) if it no has duplicate and
We’ll denote the concurrency of a multiset \(m\) by \(\textsf{Concurrent $m$}\).
Let be \(N\) an occurrence net, Concurrent \(N\) \(m\) and \(m' ≤ m\), then Concurrent \(N\) \(m'\).
Let be \(N\) an occurrence net and Concurrent \(N\) \((m + t•)\), then Concurrent \(N\) \((m + •t)\).
Let \(N\) be an occurrence net, \(t\) an enabled transition at \(m\) and \(a,b\) two different places. If \(\textsf{Concurrent $N$ $m$}\), \(m [[t⟩ m'\) is a firing, and \(a,b∈ m'\), then \(a \textsf{ co }\)b.
Let \(N\) be an occurrence net and \(t\) a transition enabled at \(m\). If \(\textsf{Concurrent $N$ $m$}\) and \(m [[t⟩ m'\) is a firing, then \(\textsf{Concurrent $N$ $m'$}\).
Let \(N\) be an occurrence net and \(s\) a transition sequence. If \(N\) is concurrent at \(m\) and \(m [[s⟫ m'\) is a firing sequence, then \(\textsf{Concurrent $N$ $m'$}\).
Every marked occurrence net \((N,m₀)\) is marking concurrent at \(m₀\).
Every marked occurrence net \((N,m₀)\) is safe.
A net is safe if for each multiset \(m\) and sequence \(s\), \(m₀ [[s⟫ m\) implies that \(m\) has no duplicate tokens. So, let \(m\) be a multiset and \(s\) a transition sequence.
We’ve proved (Lemma 43) that \(m₀\) is concurrent in \(N\), so it’s enough to apply the Lemma 42 to the occurrence condition in the hypothesis \(s\), firing sequence \(m₀ [[s⟫ m\) and use the Lemma 43.