Documentation

PetriNet.Nets

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 α β,

Standard variable for types #

structure Nets.Net (α β : Type) :

A net is a structure with places α, transitions β, functions pre, post and the condition ∀ t , pre t ≠ ∅ ∧ post t ≠ ∅.

Instances For
    theorem Nets.Net.ext {α β : Type} {x y : Net α β} (pre : x.pre = y.pre) (post : x.post = y.post) :
    x = y
    theorem Nets.Net.ext_iff {α β : Type} {x y : Net α β} :
    x = y ↔ x.pre = y.pre ∧ x.post = y.post
    inductive Nets.Tr :
    Instances For
      inductive Nets.Pl :
      Instances For
        @[implicit_reducible]
        Equations
        Equations
        Instances For
          def Nets.presetₚ {α β : Type} (N : Net α β) (p : α) :
          Set β
          Equations
          Instances For
            def Nets.presetₜ {α β : Type} (N : Net α β) (t : β) :
            Equations
            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
                  def Nets.postsetₚ {α β : Type} (N : Net α β) (p : α) :
                  Set β
                  Equations
                  Instances For
                    def Nets.postsetₜ {α β : Type} (N : Net α β) (t : β) :
                    Equations
                    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
                          def Nets.minimal {α β : Type} (N : Net α β) :
                          Set α
                          Equations
                          Instances For
                            def Nets.is_initial {α β : Type} (N : Net α β) (s : Set α) :
                            Equations
                            Instances For
                              def Nets.maximal {α β : Type} (N : Net α β) :
                              Set α
                              Equations
                              Instances For
                                def Nets.is_maximal {α β : Type} (N : Net α β) (s : Set α) :
                                Equations
                                Instances For
                                  def Nets.is_enabled {α β : Type} (N : Net α β) (m : Multiset α) (t : β) :

                                  Enabled transitions

                                  Given a multiset m, enable m returns the set of transitions that are enabled at m.

                                  Equations
                                  Instances For
                                    Equations
                                    • One or more equations did not get rendered due to their size.
                                    Instances For
                                      def Nets.enabled {α β : Type} (N : Net α β) (m : Multiset α) :
                                      Set β
                                      Equations
                                      Instances For
                                        def Nets.is_enabled_from {α β : Type} {N : Net α β} {m : Multiset α} {t : β} (e : presetₜ N t ≤ m) :
                                        Equations
                                        • ⋯ = e
                                        Instances For
                                          def Nets.deadlock {α β : Type} (N : Net α β) (m : Multiset α) :

                                          Deadlock A deadlock is a marking from which no transition can be fired.

                                          Equations
                                          Instances For
                                            def Nets.marking_after_firing {α : Type} [DecidableEq α] {β : Type} {t : β} (N : Net α β) (m : Multiset α) :
                                            is_enabled N m t → Multiset α

                                            Firing

                                            Equations
                                            Instances For
                                              def Nets.is_firing {α : Type} [DecidableEq α] {β : Type} {t : β} (N : Net α β) (m : Multiset α) (h : is_enabled N m t) (m' : Multiset α) :
                                              Equations
                                              Instances For
                                                theorem Nets.is_firing_of_enabled {α : Type} [DecidableEq α] {β : Type} {N : Net α β} {m : Multiset α} {t : β} (e : is_enabled N m t) :
                                                is_firing N m e (m - presetₜ N t + postsetₜ N t)
                                                Equations
                                                • One or more equations did not get rendered due to their size.
                                                Instances For
                                                  inductive Nets.firing_sequence {α : Type} [DecidableEq α] {β : Type} :
                                                  Net α β → Multiset α → List β → Multiset α → Prop
                                                  Instances For
                                                    def Nets.is_firing_sequence {α : Type} [DecidableEq α] {β : Type} (N : Net α β) (m : Multiset α) (ts : List β) (m' : Multiset α) :
                                                    Equations
                                                    Instances For
                                                      Equations
                                                      • One or more equations did not get rendered due to their size.
                                                      Instances For
                                                        inductive Nets.Tr₂ :

                                                        Applying firing sequence to the net N₁ is not interesting, because all its secuences have at most length one. So, let’s considering the net N₂.

                                                        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'') :
                                                            m' = m''
                                                            theorem Nets.target_of_empty_fs {α : Type} [DecidableEq α] {β : Type} {N : Net α β} {m m' : Multiset α} (fs : is_firing_sequence N m [] m') :
                                                            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'') :
                                                            m' = 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'
                                                            def Nets.is_reachable {α : Type} [DecidableEq α] {β : Type} (N : Net α β) (m m' : Multiset α) :
                                                            Equations
                                                            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''
                                                              structure Nets.MarkedNet (α β : Type) extends Nets.Net α β :
                                                              Instances For
                                                                theorem Nets.MarkedNet.ext_iff {α β : Type} {x y : ↑α β} :
                                                                x = y ↔ x.pre = y.pre ∧ x.post = y.post ∧ x.m₀ = y.m₀
                                                                theorem Nets.MarkedNet.ext {α β : Type} {x y : ↑α β} (pre : x.pre = y.pre) (post : x.post = y.post) (m₀ : x.m₀ = y.m₀) :
                                                                x = y
                                                                @[implicit_reducible]
                                                                instance Nets.instCoeMarkedNetNet {α β : Type} :
                                                                Coe (↑α β) (Net α β)
                                                                Equations
                                                                def Nets.reachable {α : Type} [DecidableEq α] {β : Type} (M : ↑α β) :
                                                                Equations
                                                                Instances For
                                                                  def Nets.safe {α : Type} [DecidableEq α] {β : Type} (M : ↑α β) :

                                                                  Reachable markings are sets.

                                                                  Equations
                                                                  Instances For
                                                                    def Nets.M₁ :
                                                                    ↑Pl Tr
                                                                    Equations
                                                                    Instances For
                                                                      Equations
                                                                      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₂} :
                                                                        is_firing N m e₁ m1 → is_firing N m e₂ m2 → ∀ (d : Disjoint (presetₜ N t₁) (presetₜ N t₂)), ∃ (e1 : is_enabled N m1 t₂) (e2 : is_enabled N m2 t₁) (m' : Multiset α), is_firing N m1 e1 m' ∧ is_firing N m2 e2 m'