1 Petri nets
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 preset for places is a function that take a net \(N\), a place \(p\) and return the set \(\{ t \mid p ∈ t•\} \), where the postset function is defined in Definition 1.
A preset for transitions is a function that take a net \(N\), a transition \(t\) and return the multiset \(•t\).
A postset for places is a function that take a net \(N\), a place \(p\) and return the set \(\{ t | p ∈ •t \} \), where the preset function is defined in Definition 1.
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\).
This definition say if the multiset doesn’t have any transition before.
A set \(s\) is initial in a net \(N\) if \(s ⊆ minimal(N)\).
This definition say if the multiset doesn’t have any transition after.
A set \(s\) is maximal in a net \(N\) if \(s ⊆ maximal(N)\).
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
Given a net \(N\), a transition \(t\) and a prove that \(t\) is enabled at \(m\), the function marking_after_firing N m e returns the multiset applied at \(m\) on \(t\), which is \(m - •t + t•\).
Given a net \(N\), is_firing : N → Multiset \(\alpha \) → h → Multiset \(\alpha \) → Prop checks if a firing on a multiset \(m\) by \(t\) is equal to another multiset \(m'\), i.e., if \(m[[t⟩ = m'\). We denote this only by \(m[[t⟩m'\)
Let \(N\) be a net, \(t\) a transition and \(m\) a multiset, then \(m [[t⟫ (m - •t + t•)\).
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.
For a net \(N\) and a transition \(t\) enabled at \(m\) (where \(e\) is a proof that it is enabled), if \(m [[t⟩ m'\) and \(m [[t⟩ m''\) then \(m' = m''\).
Immediate by unfolding Definition 12.
For every net \(N\) and multisets \(m,m'\), \(m[[ε⟫m'\) implies \(m = m'\).
By structural induction on the firing sequence.
Let \(t\) be a transition and \(s\) a sequence (note that \(t;s\) is a sequence), \(m,m'\) two multisets and \(m[[ t;s ⟫ m'\), then there exist a multiset \(m''\) such that \(m'' [[ s⟫ m\).
Let \(t\) be a transition, \(s\) a sequence of transitions, \(m,m'\) two multisets, and \(m[[t;s ⟫ m'\). Then, there exist a multiset \(m''\) such that \(m[[t⟩ m''\).
Let be \(m[[s_1⟫ m'\) and \(m'[[s_2⟫ m''\) two firing sequences. Then \(m[[s_1;s_2⟫ m''\).
Let \(m[[s_1;s_2⟫ m'\) be a firing sequences, then there is a multiset \(m''\) such that \(m[[s_1⟫ m''\) and \(m''[[s_2⟫ m'\).
By induction on the length of \(s_1\), and by structural induction on the firing sequence for \(s_2\).
Let be \(m [[ s ⟫ m'\) and \(m [[ s ⟫ m''\) two firing sequences, then \(m' = m''\).
A marked net is a tuple \(M = (N,m₀)\), where \(N\) is a net (Definition 1) and \(m₀\) is the initial marking.
Given a marked net \(M\) and a multiset \(m\), reachable N m return all the multisets that can be executed by sequences of firing enabled. We denote a reachable for a marking \(m\) of a net \(N\) by \(N \leadsto m\).
A marked net \(M = (N, m₀)\) is safe if for every multiset \(m\), \(M ↝ m\) implies that \(m\) has no duplicate.
Let \(N\) a net, \(m[[t_1⟩m_1\) and \(m[[t_2⟩m_2\) two firings, and \(•t₁ ∩ •t₂ = ∅ \). Then, there is a multiset \(m'\) such that \(m₁[[t₁⟩m'\) and \(m₂ [[t₂⟩ m'\).
It is suffices to take \(m' = m - •t₁ + t₁• - •t₂ + t₂•\). To prove that \(m₁[[t₁]]\) note that we can have \(m₁ = m - •t₁ + t₁•\) after firing, and \(•t₂ ≤ m - •t₁\). Analousgly with the enabled \(m₂[[t₂]]\).