Reversible Occurrence Nets

1 Petri nets

Definition 1 Net
✓
#

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∈ β\).

Definition 2 Preset for places.
✓
#

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.

Definition 3 Preset for transitions.
✓
#

A preset for transitions is a function that take a net \(N\), a transition \(t\) and return the multiset \(•t\).

Definition 4 Postset for places.
✓
#

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.

Definition 5 Postset for transitions.
✓
#

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\).

Definition 6 Minimal
✓
#

This definition say if the multiset doesn’t have any transition before.

Definition 7 Is minimal
✓
#

A set \(s\) is initial in a net \(N\) if \(s ⊆ minimal(N)\).

Definition 8 Maximal
✓
#

This definition say if the multiset doesn’t have any transition after.

Definition 9 Is maximal
✓
#

A set \(s\) is maximal in a net \(N\) if \(s ⊆ maximal(N)\).

Definition 10 Enabled transition
✓
#

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

Definition 11
✓

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•\).

Definition 12 Firing
✓
#

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•)\).

Proof ▶

It is immediate by Definition 12 and Definition 11.

Definition 14 Firing sequence
✓

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.

Lemma 15 Firing deterministic
✓

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''\).

Proof ▶

Immediate by unfolding Definition 12.

For every net \(N\) and multisets \(m,m'\), \(m[[ε⟫m'\) implies \(m = m'\).

Proof ▶

By structural induction on the firing sequence.

Lemma 17
✓

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\).

Lemma 18
✓

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''\).

Lemma 19 Concat firing sequence
✓

Let be \(m[[s_1⟫ m'\) and \(m'[[s_2⟫ m''\) two firing sequences. Then \(m[[s_1;s_2⟫ m''\).

Lemma 20 Append split of firing sequence
✓

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'\).

Proof ▶

By induction on the length of \(s_1\), and by structural induction on the firing sequence for \(s_2\).

Lemma 21 Firing sequence deterministic
✓

Let be \(m [[ s ⟫ m'\) and \(m [[ s ⟫ m''\) two firing sequences, then \(m' = m''\).

Definition 22
✓
#

A marked net is a tuple \(M = (N,m₀)\), where \(N\) is a net (Definition 1) and \(m₀\) is the initial marking.

Definition 23 Reachable
✓
#

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\).

Definition 24 Safe
✓
#

A marked net \(M = (N, m₀)\) is safe if for every multiset \(m\), \(M ↝ m\) implies that \(m\) has no duplicate.

Theorem 25 Square lemma
✓

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'\).

Proof ▶

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₂]]\).

  1. In this documentation we avoid the subscript notation, and instead we write only \(m[[t]]\).