3 Reversible occurrence nets
3.1 Transition type and reversible nets
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 ∈ β \).
For a transition with type \(\mathsf{Transition}\) we define the opposite of \(t_t\) as
For \(b∈ β\), we’ll say that a transition \(t=(b,\mathsf{fwd})\) is forward and let’s denote it as \(▷t\).
For \(b∈ β\), we’ll say that a transition \(t=(b,\mathsf{bwd})\) is backward and let’s denote it as \(◁t\).
For a transition with type \(t=⟨t_{β}, t_t⟩ ∈ β × \mathsf{Transition}\), its reverse is defined as \(↽ t := ⟨t_β, opposite(t_t)⟩\).
Let \(s\) a sequence of transitions with types \(β × \mathsf{Transition}\). We denote \(▷\! ▷ s\) if forall \(t∈ s\), \(▷t\); or if \(s=ε\).
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₂\).
(\(⇒ \)) 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₂\).
Analousgly to Thm. 52.
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'\).
Immediatly by Def. 54.
For \(t,t'∈ β × \mathsf{TransitionType}\), \(t↽ ⇀ t'\) if and only if \(t↽ ⇀ t'\).
A reversible occurrence net is a net \( N=(α, β \uplus \{ ↽ t \mid t∈ β\} ,•{\_ },{\_ }•) \) defined by the following conditions:
\((α, β, (•{\_ })_{|β}, ({\_ }•)_{|β}\) is an occurrence net, where \(f_{|β}\) denotes the restriction of the function \(f\) to the domain \(β\).
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\).
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,
If \((∃ s, m[[s⟫ m')\) then \((∃ s, m'[[s⟫ m).\)
3.2 Trace 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 ≍ ε\).
\(s ≍ s\).
\(s₁ ≍ s₂ \Longrightarrow s₂ ≍ s₁\).
\(s₁ ≍ s₂ ∧ s₂ ≍ s₃ \Longrightarrow s₁ ≍ s₃\).
\( s₁ ≍ s₂ ∧ s₃ ≍ s₄ \Longrightarrow s₁; s₃ ≍ s₂ ; s₄ \).
By cases over the structural definition 63.