Basic definitions of Petri Net #
A Net is a structure that is build from two types: α for places and β for transitions.
N = (α, β, pre, post) is a place/transition Petri net (or only 'net') and (N,m₀) is a marked
net, where m₀ is the initial multiset.
Main definitions #
Notation used here:
For a Petri net N : Net α β,
- Enabled transition: A transition
tenabled in a multisetmis written bym〚t〛⦃N⦄[〚 using\llb, 〛using\rrb, ⦃⦄ using\{{}}or\{{\}}] - Execution (firing): Given a multiset
m₁and a transitiont, returns the multisetm₂. Ifm₁ ⟦en⟩⦃N⦄ = m₂is true, we can denote asm₁〚en⟩⦃N⦄ m₂, whereen : (m₁〚t〛⦃N⦄). [⟩ using\ran..\rangle] m₁〚ts⟩⟩⦃N⦄ m₂ : Propis an abreviature if there are sequences of multisetsm₀,m₁,...,mₙand a list of transitionsts = [t₁,t₂,...,tₙ]whichmᵢ₋₁〚enᵢ⟩⦃N⦄ mᵢfor each i = 1,...,n.
Standard variable for types #
@[implicit_reducible]
Equations
Instances For
Equations
- Nets.presetₜ N t = N.pre t
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- Nets.postsetₚ N p = {t : β | p ∈ Nets.presetₜ N t}
Instances For
Equations
- Nets.postsetₜ N t = N.post t
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- Nets.minimal N = {p : α | Nets.presetₚ N p = ∅}
Instances For
Equations
- Nets.is_initial N s = (s ⊆ Nets.minimal N)
Instances For
Equations
- Nets.maximal N = {p : α | Nets.postsetₚ N p = ∅}
Instances For
Equations
- Nets.is_maximal N s = (s ⊆ Nets.maximal N)
Instances For
Enabled transitions
Given a multiset m, enable m returns the set of transitions that are enabled at m.
Equations
- Nets.is_enabled N m t = (Nets.presetₜ N t ≤ m)
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- Nets.enabled N m = {t : β | Nets.is_enabled N m t}
Instances For
def
Nets.is_enabled_from
{α β : Type}
{N : Net α β}
{m : Multiset α}
{t : β}
(e : presetₜ N t ≤ m)
:
is_enabled N m t
Equations
- ⋯ = e
Instances For
Deadlock A deadlock is a marking from which no transition can be fired.
Equations
- Nets.deadlock N m = IsEmpty ↑(Nets.enabled N m)
Instances For
def
Nets.marking_after_firing
{α : Type}
[DecidableEq α]
{β : Type}
{t : β}
(N : Net α β)
(m : Multiset α)
:
is_enabled N m t → Multiset α
Firing
Equations
- Nets.marking_after_firing N m x✝ = m - Nets.presetₜ N t + Nets.postsetₜ N t
Instances For
Equations
Instances For
Equations
Instances For
def
Nets.is_firing
{α : Type}
[DecidableEq α]
{β : Type}
{t : β}
(N : Net α β)
(m : Multiset α)
(h : is_enabled N m t)
(m' : Multiset α)
:
Equations
- Nets.is_firing N m h m' = (Nets.marking_after_firing N m h = m')
Instances For
theorem
Nets.is_firing_of_enabled
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m : Multiset α}
{t : β}
(e : is_enabled N m t)
:
Equations
- One or more equations did not get rendered due to their size.
Instances For
- empty {α : Type} [DecidableEq α] {β : Type} {a✝ : Net α β} (m : Multiset α) : firing_sequence a✝ m [] m
- step {α : Type} [DecidableEq α] {β : Type} {N : Net α β} {t : β} {ts : List β} {m m' m'' : Multiset α} (et : is_enabled N m t) (f : is_firing N m et m') (fs : firing_sequence N m' ts m'') : firing_sequence N m (t :: ts) m''
Instances For
def
Nets.is_firing_sequence
{α : Type}
[DecidableEq α]
{β : Type}
(N : Net α β)
(m : Multiset α)
(ts : List β)
(m' : Multiset α)
:
Equations
- Nets.is_firing_sequence N m ts m' = Nets.firing_sequence N m ts m'
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
Instances For
Equations
Instances For
theorem
Nets.firing_deterministic
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m' m'' : Multiset α}
{t : β}
{e : is_enabled N m t}
(ft : is_firing N m e m')
(ft' : is_firing N m e m'')
:
theorem
Nets.target_of_empty_fs
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m' : Multiset α}
(fs : is_firing_sequence N m [] m')
:
theorem
Nets.tail_of_fs
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m' : Multiset α}
{t : β}
{ts : List β}
(fs : is_firing_sequence N m (t :: ts) m')
:
∃ (m'' : Multiset α), is_firing_sequence N m'' ts m'
theorem
Nets.head_of_fs
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m' : Multiset α}
{t : β}
{ts : List β}
(fs : is_firing_sequence N m (t :: ts) m')
:
∃ (e : is_enabled N m t) (m'' : Multiset α), is_firing N m e m''
theorem
Nets.concat_fs
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m' m'' : Multiset α}
{ts₁ ts₂ : List β}
(h1 : is_firing_sequence N m ts₁ m')
(h2 : is_firing_sequence N m' ts₂ m'')
:
is_firing_sequence N m (ts₁ ++ ts₂) m''
theorem
Nets.append_split_of_fs
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m' : Multiset α}
{ts₁ ts₂ : List β}
(fs : is_firing_sequence N m (ts₁ ++ ts₂) m')
:
∃ (m'' : Multiset α), is_firing_sequence N m ts₁ m'' ∧ is_firing_sequence N m'' ts₂ m'
theorem
Nets.fs_deterministic
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m' m'' : Multiset α}
{ts : List β}
(fs : is_firing_sequence N m ts m')
(fs' : is_firing_sequence N m ts m'')
:
theorem
Nets.non_disjoint_pre_post_if_enabled_after
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m' : Multiset α}
{t t' : β}
(noe : ¬is_enabled N m t')
(fs : is_firing_sequence N m [t, t'] m')
:
theorem
Nets.can_swap_if_disjoint_pre_post
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m' : Multiset α}
{t t' : β}
(fs : is_firing_sequence N m [t, t'] m')
(d : Disjoint (postsetₜ N t) (presetₜ N t'))
:
is_enabled N m t'
Equations
- Nets.is_reachable N m m' = ∃ (fs : List β), Nets.firing_sequence N m fs m'
Instances For
theorem
Nets.reach_after_firing_from_reach
{α : Type}
[DecidableEq α]
{β : Type}
{N : Net α β}
{m m'' m₀ : Multiset α}
{t : β}
{e : is_enabled N m t}
(r : is_reachable N m₀ m)
(fs : is_firing N m e m'')
:
is_reachable N m₀ m''
@[implicit_reducible]
Equations
- Nets.instCoeMarkedNetNet = { coe := fun (M : ↑α β) => M.toNet }
Equations
- Nets.reachable M = {m' : Multiset α | Nets.is_reachable M.toNet M.m₀ m'}
Instances For
Equations
- Nets.«term_↝_» = Lean.ParserDescr.trailingNode `Nets.«term_↝_» 50 51 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ↝ ") (Lean.ParserDescr.cat `term 51))
Instances For
theorem
Nets.square
{α : Type}
[DecidableEq α]
{β : Type}
{m : Multiset α}
{t₁ t₂ : β}
{m1 m2 : Multiset α}
(N : Net α β)
{e₁ : is_enabled N m t₁}
{e₂ : is_enabled N m t₂}
: