Reversible Occurrence Nets

4 Parabolic

4.1 Swapping lemma

Definition 68
✓
#

Let \(t ∈ β\) a transition and \(s\) a sequence of transitions of \(β\). We define

\[ t ∉ ^r := \forall t' ∈ s, ¬ (t ↽⇀ t'). \]
Definition 69
✓
#

Let \(t ∈ β\) a transition and \(s\) a sequence of transitions of \(β\). We define

\[ t ∃^r := \exists t' ∈ s, (t ↽⇀ t'). \]

Let \(M = (N, m₀)\) a marked reversible occurrence net, \(m\) a marking, \(t\) and \('t\) two transitions with \(t• ∩ •t' = ∅ \) and \(¬(t ↽⇀ t')\). If \(M ↝ m\) and \(m [t;t'⟫ m'\), then \(m [[t';t⟫ m'\).

Let \(M = (N, m₀)\) a marked reversible occurrence net, \(m\) a marking, \(t\) and \('t\) two transitions with \(▷t\) (is forward transition) and \(◁ t'\) (is backward transition). If \(M ↝ m₀\), \(¬ (t ↽⇀ t')\) and \(m[[t;t'⟫ m'\) is a firing sequence, then we can have the swapped firing sequence between the transitions: \(m [[t';t⟫ m'\).

Let \(M = (N, m₀)\) a marked reversible occurrence net, \(m\) a marking, \(s\) a sequence and \(t\) a transition with the condition \(◁ ◁ s\) and \(▷t\). If \(M ↝ m₀\), \(t ∉ s\) and \(m[[t;s⟫ m'\) is a firing sequence, then we can have the swapped between the transition and all the backward sequence: \(m [[s;t⟫ m'\).

4.2 Parabolic lemma

Let \(R\) be a reversible occurrence net, \(m\) a reachable marking, and \(m [[\omega ⟫ m'\) a firing sequence. Then there exist two sequences of transitions, \(\omega '\) and \(\omega ''\), such that \(\omega '\) consists only of backward transitions, \(\omega ''\) consists only of forward transitions, \(\omega ≍ \omega ';\omega ''\), and \(m [[\omega '; \omega ''⟫ m'\).

Proof ▶

By applying induction on the firing sequence. The base case when \(m' = m\) is immediate. The inductive step applies the property of \(≍ \) and the Lemma 73.

Appendix - Auxiliar lemmas for multisets

Lemma 75
✓
#

If \(t ≤ s\) then \(t + (s-t) = s\).

Proof ▶
Lemma 76
✓
#

\(s + t -u = s - u + t\).

Proof ▶