Reversible Occurrence Nets

2 Occurrence nets

Definition 26 Immediate dependency
✓
#

Let \(N\) be a net. The immediate dependency relation \({\lt}_N ⊆ (α ∪ β) × (α ∪ β)\) is defined by the set

\begin{equation} \label{eq:immediate_dependency} \{ (x,y) \mid (y ∈ β ∧ x ∈ •y) ∨ (x ∈ β ∧ y ∈ x•)\} \end{equation}
1

Definition 27 Causal relation
✓
#

We denote the transitive closure of \({\lt}_N\) as the causal relation \(≺_N\).

Definition 28
✓
#

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)\).

Definition 30
✓
#

Two different transtions \(t,t'\) are in immediate conflict if \(•t ∩ •t ≠ ∅\). Let’s denote this relation as \(t ♯₀ t'\).

Definition 31 Conflict
✓
#

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\).

Definition 32 Backward conflict
✓
#

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₂•)\).

Definition 33 Acyclicity
✓
#

A net is acyclic if its causal relation is irreflexive, i.e., there is no \(x ∈ α ∪ β\) such that \(x ≺_N x\).

Definition 34 Occurrence net
✓

A marked net \((N,m_0)\) is an occurrence net if it satisfies the following statements:

  1. \(N\) is acyclic;

  2. there is no self-conflict, i.e., \(¬(t ♯ t)\) for all transition \(t\);

  3. there is no backward conflict;

  4. \(N\) is 1-safe, i.e., marking is a set;

  5. the initial marking is the set of initial places, i.e., \(m₀\) is minimal (Definition 6).

Definition 35 Marked occurrence net
✓

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\).

Definition 36 Concurrency
✓
#

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\).

Definition 37 Concurrent multiset
✓
#

A multiset \(m\) is concurrent in \(N\) if it no has duplicate and

\[ ∀ x, y ∈ α, (x ∈ m) ⇒ (y ∈ m) ⇒ x ≠ y ⇒ x\textsf{ co }y. \]

We’ll denote the concurrency of a multiset \(m\) by \(\textsf{Concurrent $m$}\).

Lemma 38
✓
#

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'$}\).

Proof ▶

The proof procedes by applying structural induction over the length of the sequence \(s\).

For the base case apply the Lemma 16 and is obtained that \(m'=m\), so it’s concurrent at \(m'\) by hypothesis.

For the step case, we can apply the inductive hypothesis over Lemma 41.

Every marked occurrence net \((N,m₀)\) is marking concurrent at \(m₀\).

Every marked occurrence net \((N,m₀)\) is safe.

Proof ▶

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.