- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
firing_sequence N m ls m’ is the concatenation of sequences, where \(ls\) is the sequence of transitions, \(m\) is the initial marking (Definition 7) and \(m'\) the final marking of the sequence. We denote for \(s=ε\) for a empty sequence, in Lean this is an empty list, we denote for ’;’ the concatenation of lists. Therefore, a firing sequence is defined inductively as
Empty. \(m [[ε⟫ m\)
Inductive step. For a sequence \(t;s\) where \(t\) is a transition and \(s\) is a transition sequence, \(m[[t;s⟫ m'\) is a firing sequence if there is \(m''\) such that \(m[[t⟩m''\) is firing and \(m''[[s⟫ m'\) is a firing sequence.
Given a net \(N\) and a multiset \(m\), a verificator of enabled transition is a function \(\textsf{is\_ enabled}:N → \textsf{Multiset} → β → \textsf{Prop}\) that verifies if \(m ≤ •t\). We denote \(\textsf{is\_ enabled N m t}\) as \(m[[t]]_{ \{ \! \{ N\} \! \} }\). 1
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 net \(N\) is a tuple \(N=(\alpha , \beta , \bullet {\_ }, \bullet {\_ })\), where \(\alpha \) is a nonempty set of places, \(\beta \) is the set of transitions, and \(•{\_ }, {\_ }•: \beta → ℕ ^{\alpha }\) assign source and target to each transition. We consider only nets in which every transition both consumes and produces, i.e., \(•t ≠ ∅\) and \(t• ≠ ∅\) for all \(t∈ β\).
A postset for transitions is a function that take a net \(N\), a transition \(t\) and return the multiset \(t•\).
The notation for preset of places or transition are written as \(\bullet _{ \{ \! \{ N \} \! \} }t\), but in this file we’ll use only the short notation \(•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)\).
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 ∈ β \).
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 ≍ ε\).
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'\).
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'\).