Reversible Occurrence Nets

3 Reversible occurrence nets

3.1 Transition type and reversible nets

Definition 45 Transition Type
✓
#

Lets define the type Transition \(::=\) fwd | bwd, where their elements are the forward direction for \(\mathsf{fwd}\) and backward direction for \(\mathsf{bwd}\). Given a type for transition \(\beta \), we define the set of reversible transitions as pairs \(t_r ::= ⟨t,\mathsf{fwd}⟩ \mid ⟨t,\mathsf{bwd}⟩\) with \(t ∈ β \).

Definition 46 Opposite
✓
#

For a transition with type \(\mathsf{Transition}\) we define the opposite of \(t_t\) as

\[ opposite(t_t) = \begin{cases} \mathsf{fwd} & \text{ if } t_t = \mathsf{bwd}\\ \mathsf{bwd} & \text{ if } t_t = \mathsf{fwd} \end{cases} \]
Definition 47
✓
#

For \(b∈ β\), we’ll say that a transition \(t=(b,\mathsf{fwd})\) is forward and let’s denote it as \(▷t\).

Definition 48
✓
#

For \(b∈ β\), we’ll say that a transition \(t=(b,\mathsf{bwd})\) is backward and let’s denote it as \(◁t\).

Definition 49 Reverse
✓
#

For a transition with type \(t=⟨t_{β}, t_t⟩ ∈ β × \mathsf{Transition}\), its reverse is defined as \(↽ t := ⟨t_β, opposite(t_t)⟩\).

Definition 50
✓
#

Let \(s\) a sequence of transitions with types \(β × \mathsf{Transition}\). We denote \(▷\! ▷ s\) if forall \(t∈ s\), \(▷t\); or if \(s=ε\).

Definition 51
✓
#

Let \(s\) a sequence of transitions with types \(β × \mathsf{Transition}\). We denote \(◁ \! ◁ s\) if forall \(t∈ s\), \(◁ t\); or if \(s=ε\).

Let \(s₁, s₂\) two transition sequences. Then, \(◁ ◁ s₁;s₂\) if and only if \(◁ ◁ s₁ ∧ ◁ ◁ s₂\).

Proof ▶

(\(⇒ \)) Suppose that \(s = s₁;s₂\) is a transition sequence with all the transitions backward. By induction over the length of the sequence \(s₁\):

  • Empty. If \(s₁ = ε\) we have that \(s = ε ; s₂ = s₂\), and by hypothesis \(◁ ◁ s\), then \(◁ ◁ s₂\) and by Def. 51 \(◁ ◁ ε\) is truth. Therefore, \(◁ ◁ s₁ ∧ ◁ ◁ s₂\).

  • Inductive step. If \(s₁ = t;s'\) with \(◁ ◁ (s';s₂)\) implies \(◁ ◁ s'∧ ◁ ◁ s₂\), then \(◁ ◁ (t;s;s₂)\) implies that \(◁ t\) and therefore \(◁ ◁ (t;s') ∧ ◁ ◁ s₂\).

(\(\Leftarrow \)) By induction over the length on the sequence \(s₁\).

Let \(s₁, s₂\) two transition sequences. Then, \(▷▷ s₁;s₂\) if and only if \(▷ ▷ s₁ ∧ ▷ ▷ s₂\).

Proof ▶

Analousgly to Thm. 52.

Definition 54 Inverse
✓
#

Let be \(t,t' ∈ β × \mathsf{Transition}\). The transition \(t\) is inverse of \(t'\) if \(t = ↽ t'\). We denote the inverse of two transitions \(t,t'\) –in this order– by \(t ↽ ⇀ t'\).

Let \(t,t'\) be two transitions in \(β × \mathsf{Transition}\). Then, \(t = t'\) if and only if \(↽ t = ↽ t'\).

Proof ▶

Immediatly by Def. 54.

Definition 56 Inverse symmetric
✓
#

For \(t,t'∈ β × \mathsf{TransitionType}\), \(t↽ ⇀ t'\) if and only if \(t↽ ⇀ t'\).

Definition 57 Reversing occurrence nets
✓

A reversible occurrence net is a net \( N=(α, β \uplus \{ ↽ t \mid t∈ β\} ,•{\_ },{\_ }•) \) defined by the following conditions:

  1. \((α, β, (•{\_ })_{|β}, ({\_ }•)_{|β}\) is an occurrence net, where \(f_{|β}\) denotes the restriction of the function \(f\) to the domain \(β\).

  2. For every \(t \in β\), \(• t = (↽{t})•\) and \(t• = •(↽ t)\).

For a reversible net \(R\), if \(m [[t]]\) and \(m [[t⟩ m'\) then there is a transition \(t'\), which \(t' ↽⇀ t\) and \(m'[[t']]\).

If \(t ↽⇀ t'\), \(m [[t⟩ m'\) and \(m' [[t']]\) then \(m'[[t'⟩ m\).

Proof ▶
Definition 60 Marked reversible occurrence net
✓

A tuple \(MO = (R,m₀)\) is marked reversible occurrence if \(R\) is a reversible net and (fwd_subnet \(R,m₀\)) is marked occurrence, where fwd_subnet returns the forward subnet of a reversing net.

Let \(t,t' ∈ β × Transition\) two reversing transitions, i.e., \(t↽ ⇀ t'\). Then,

\[ (∃ e, m[[e⟩ m') \Longleftrightarrow (∃ e, m'[[e⟩ m) \]

If \((∃ s, m[[s⟫ m')\) then \((∃ s, m'[[s⟫ m).\)

Proof ▶

By induction over the length of a sequence \(s\). By applying the Lemma 61 to the step case \(t;s\) on \(s\), we can obtain a witness \(s;↽ t\) and apply the respective concatenation (Lemma 19) and we have the firing sequence as expected.

3.2 Trace equivalence

Definition 63 Transition equivalence
✓

The statement of the lemma requires a formal notion of equivalent firing sequences, which is the smallest congruence 1 \(\asymp \) on transition sequences closed under the following rules:

  • \(t;t' ≍ t';t\) if \(t \textsf{ co } t'\),

  • \(t;↽ t ≍ ε\), and

  • \(↽ t;t ≍ ε\).

Definition 64
✓
#

\(s ≍ s\).

\(s₁ ≍ s₂ \Longrightarrow s₂ ≍ s₁\).

Definition 66
✓
#

\(s₁ ≍ s₂ ∧ s₂ ≍ s₃ \Longrightarrow s₁ ≍ s₃\).

\( s₁ ≍ s₂ ∧ s₃ ≍ s₄ \Longrightarrow s₁; s₃ ≍ s₂ ; s₄ \).

Proof ▶

By cases over the structural definition 63.

  1. A relation \(R\) over sequences is a congruence if it is an equivalence relation closed by concatenation, i.e., \(s_1 R s_2\) and \(s_3 R s_4\) implies \(s_1;s_3 R s_2;s_4\) for all \(s_1, s_2, s_3\) and \(s_4\).