Documentation

PetriNet.Occurrence

This file provides the definitions and properties necessary to construct a flow relationship in a Petri net. Which is necessary to establish occurrence nets.

< is a relationship between places and transitions directly. Their transitive closure ≺ [abr: \pre, \prec] is given by TransGen. Their reflexo-transitive closure ≼ [abr: \prece, \preceq] is given by ReflTransGen.

A marked net (N, m₀) could be think as a tuple (α, β, •_, _•, m₀). This is helpful at time to defined the flow relationship, because we can have x,y ∈ α ⊎ β with x ≼ y (for instance) regardless of whether x and y are the same type or not. This disjoint union we write as α ⊕ β.

Notation #

Standard variable for types/general structures #

def Flow.immediate {α β : Type} (N : Nets.Net α β) :
α ⊕ β → α ⊕ β → Prop
Equations
Instances For
    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      theorem Flow.lt_of_mem_pre {α β : Type} {a : α} {t : β} {N : Nets.Net α β} :
      theorem Flow.lt_of_mem_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} :
      theorem Flow.mem_pre_of_lt {α β : Type} {a : α} {t : β} {N : Nets.Net α β} :
      theorem Flow.mem_post_of_lt {α β : Type} {a : α} {t : β} {N : Nets.Net α β} :
      theorem Flow.not_exists_inl_lt_inl {α β : Type} {N : Nets.Net α β} (a : α) :
      ¬∃ (b : α), immediate N (Sum.inl b) (Sum.inl a)
      theorem Flow.not_exists_inl_gt_inl {α β : Type} {N : Nets.Net α β} (a : α) :
      ¬∃ (b : α), immediate N (Sum.inl a) (Sum.inl b)
      theorem Flow.not_exists_inr_lt_inr {α β : Type} {N : Nets.Net α β} (t : β) :
      ¬∃ (t' : β), immediate N (Sum.inr t) (Sum.inr t')
      theorem Flow.not_exists_inr_gt_inr {α β : Type} {N : Nets.Net α β} (t : β) :
      ¬∃ (t' : β), immediate N (Sum.inr t') (Sum.inr t)
      theorem Flow.exists_eq_inr_of_gt_inr {α β : Type} {a : α} {N : Nets.Net α β} {x : α ⊕ β} :
      immediate N (Sum.inl a) x → ∃ (t : β), x = Sum.inr t
      theorem Flow.exists_eq_inr_of_lt_inl {α β : Type} {a : α} {N : Nets.Net α β} {x : α ⊕ β} :
      immediate N x (Sum.inl a) → ∃ (t : β), x = Sum.inr t
      theorem Flow.exists_eq_inl_of_gt_inr {α β : Type} {t : β} {N : Nets.Net α β} {x : α ⊕ β} :
      immediate N (Sum.inr t) x → ∃ (a : α), x = Sum.inl a
      theorem Flow.exists_inl_lt_of_inr {α β : Type} {N : Nets.Net α β} (t : β) :
      ∃ (a : α), immediate N (Sum.inl a) (Sum.inr t)
      theorem Flow.exists_eq_inl_of_lt_inr {α β : Type} {t : β} {N : Nets.Net α β} {x : α ⊕ β} (h : immediate N x (Sum.inr t)) :
      ∃ (a : α), x = Sum.inl a ∧ a ∈ Nets.presetₜ N t
      theorem Flow.not_mem_pre_of_lt_post {α β : Type} {t : β} {N : Nets.Net α β} {x : α ⊕ β} {b : α} (h : immediate N x (Sum.inl b)) (a : α) (hx : x = Sum.inl a) :
      a ∉ Nets.presetₜ N t
      theorem Flow.not_lt_of_minimal {α β : Type} {a : α} {N : Nets.Net α β} (h : a ∈ Nets.minimal N) (x : α ⊕ β) :
      def Flow.causal {α β : Type} (N : Nets.Net α β) :
      α ⊕ β → α ⊕ β → Prop
      Equations
      Instances For
        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          theorem Flow.causal_of_mem_pre {α β : Type} {a : α} {t : β} {N : Nets.Net α β} (h : a ∈ Nets.presetₜ N t) :
          theorem Flow.causal_of_mem_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} (h : a ∈ Nets.postsetₜ N t) :
          theorem Flow.causal_of_mem_pre_mem_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (ha : a ∈ Nets.presetₜ N t) (hb : b ∈ Nets.postsetₜ N t) :
          theorem Flow.split_causal_of_non_disjoint_pre_post {α β : Type} {t t' : β} {N : Nets.Net α β} (d : ¬Disjoint (Nets.postsetₜ N t) (Nets.presetₜ N t')) :
          ∃ (a : α), causal N (Sum.inr t) (Sum.inl a) ∧ causal N (Sum.inl a) (Sum.inr t')
          theorem Flow.causal_of_lt {α β : Type} {N : Nets.Net α β} {x y : α ⊕ β} (i : immediate N x y) :
          causal N x y
          def Flow.preorder {α β : Type} (N : Nets.Net α β) :
          α ⊕ β → α ⊕ β → Prop
          Equations
          Instances For
            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              theorem Flow.preorder_ref {α β : Type} {N : Nets.Net α β} (x : α ⊕ β) :
              preorder N x x
              theorem Flow.preorder_trans {α β : Type} {N : Nets.Net α β} {x y z : α ⊕ β} (h1 : preorder N x y) (h2 : preorder N y z) :
              preorder N x z
              theorem Flow.preorder_of_lt {α β : Type} {N : Nets.Net α β} {x y : α ⊕ β} :
              immediate N x y → preorder N x y
              @[simp]
              theorem Flow.preorder_of_causal {α β : Type} {N : Nets.Net α β} {x y : α ⊕ β} :
              causal N x y → preorder N x y
              theorem Flow.preorder_of_mem_pre {α β : Type} {a : α} {t : β} {N : Nets.Net α β} (h : a ∈ Nets.presetₜ N t) :
              theorem Flow.preorder_of_mem_pos {α β : Type} {a : α} {t : β} {N : Nets.Net α β} (h : a ∈ Nets.postsetₜ N t) :
              theorem Flow.preorder_of_mem_pre_mem_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (ha : a ∈ Nets.presetₜ N t) (hb : b ∈ Nets.postsetₜ N t) :
              @[simp]
              theorem Flow.preorder_iff_eq_or_causal {α β : Type} {N : Nets.Net α β} {x y : α ⊕ β} :
              preorder N x y ↔ y = x ∨ causal N x y
              theorem Flow.causal_of_preorder_and_lt {α β : Type} {N : Nets.Net α β} {x y z : α ⊕ β} (h1 : preorder N x y) (h2 : immediate N y z) :
              causal N x z
              theorem Flow.flow_of_pre_and_flow {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (ha : preorder N (Sum.inr t) (Sum.inl a)) (hb : b ∈ Nets.presetₜ N t) :
              theorem Flow.not_cause_of_minimal {α β : Type} {a : α} {N : Nets.Net α β} {x : α ⊕ β} (ha : a ∈ Nets.minimal N) (neq : x ≠ Sum.inl a) :
              def immediate_conflict {α β : Type} (N : Nets.Net α β) (t t' : β) :
              Equations
              Instances For
                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  def conflict {α β : Type} (N : Nets.Net α β) (x y : α ⊕ β) :
                  Equations
                  Instances For
                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For
                      @[simp]
                      theorem immediate_conflict_symm {α β : Type} {t t' : β} {N : Nets.Net α β} (h : immediate_conflict N t t') :
                      @[simp]
                      theorem conflict_symm {α β : Type} {N : Nets.Net α β} {x y : α ⊕ β} (h : conflict N x y) :
                      conflict N y x
                      @[simp]
                      theorem not_conflict_symm {α β : Type} (N : Nets.Net α β) (x y : α ⊕ β) (h : ¬conflict N x y) :
                      theorem conflict_of_immediate_conflict {α β : Type} {t t' : β} {N : Nets.Net α β} (h : immediate_conflict N t t') :
                      def immediate_conflict_of_shared_pre {α β : Type} {t t' : β} {N : Nets.Net α β} (ne : ¬t = t') (h : ¬Disjoint (Nets.presetₜ N t) (Nets.presetₜ N t')) :
                      Equations
                      • ⋯ = ⋯
                      Instances For
                        theorem immediate_conflict_of_shared_place {α β : Type} {a : α} {t t' : β} {N : Nets.Net α β} :
                        ¬t = t' → a ∈ Nets.presetₜ N t → a ∈ Nets.presetₜ N t' → immediate_conflict N t t'
                        def conflict_of_shared_pre {α β : Type} {t t' : β} {N : Nets.Net α β} (ne : ¬t = t') (h : ¬Disjoint (Nets.presetₜ N t) (Nets.presetₜ N t')) :
                        Equations
                        • ⋯ = ⋯
                        Instances For
                          theorem conflict_inherits_left {α β : Type} {N : Nets.Net α β} {x y z : α ⊕ β} (c : conflict N x y) (f : Flow.preorder N x z) :
                          conflict N z y
                          theorem conflict_inherits_right {α β : Type} {N : Nets.Net α β} {x y z : α ⊕ β} (c : conflict N x y) (f : Flow.preorder N y z) :
                          conflict N x z
                          def backward_conflict {α β : Type} (N : Nets.Net α β) (a : α) :

                          A place has a backward conflict it has more that one transition in its preset.

                          Equations
                          Instances For
                            def acyclic {α β : Type} (N : Nets.Net α β) :

                            A net is acyclic if the causality relation is so.

                            Equations
                            Instances For
                              theorem cycle_from_shared_pre_post {α β : Type} {t t' : β} {N : Nets.Net α β} (d₁ : ¬Disjoint (Nets.postsetₜ N t) (Nets.presetₜ N t')) (d₂ : ¬Disjoint (Nets.postsetₜ N t') (Nets.presetₜ N t)) :
                              structure is_occurrence {α β : Type} (N : Nets.Net α β) :
                              Instances For
                                structure is_marked_occurrence {α β : Type} (M : ↑α β) :
                                Instances For
                                  theorem causal_irref {α β : Type} {N : Nets.Net α β} {x y : α ⊕ β} (O : is_occurrence N) :
                                  Flow.causal N x y → ¬x = y
                                  theorem causal_asymm {α β : Type} {N : Nets.Net α β} {x y : α ⊕ β} (O : is_occurrence N) (h : Flow.causal N x y) :
                                  theorem disjoint_pre_post {α β : Type} {N : Nets.Net α β} (O : is_occurrence N) (t : β) :
                                  theorem not_mem_post_of_mem_pre {α β : Type} {a : α} {t : β} {N : Nets.Net α β} (O : is_occurrence N) (ha : a ∈ Nets.presetₜ N t) :
                                  a ∉ Nets.postsetₜ N t
                                  theorem not_mem_pre_of_mem_pre {α β : Type} {a : α} {t : β} {N : Nets.Net α β} (O : is_occurrence N) (ha : a ∈ Nets.postsetₜ N t) :
                                  a ∉ Nets.presetₜ N t
                                  theorem ne_of_mem_pre_mem_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (ha : a ∈ Nets.presetₜ N t) (hb : b ∈ Nets.postsetₜ N t) :
                                  a ≠ b
                                  theorem unique_immediate_of_place {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {x : α ⊕ β} (O : is_occurrence N) (ha : a ∈ Nets.postsetₜ N t) (h : Flow.immediate N x (Sum.inl a)) :
                                  theorem unique_pre_from_immediate {α β : Type} {a : α} {t t' : β} {N : Nets.Net α β} (O : is_occurrence N) (h1 : Flow.immediate N (Sum.inr t) (Sum.inl a)) (h2 : Flow.immediate N (Sum.inr t') (Sum.inl a)) :
                                  t = t'
                                  theorem no_causal_of_mem_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} (O : is_occurrence N) (ha : a ∈ Nets.postsetₜ N t) :
                                  theorem no_causal_mem_post_of_mem_pre {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (ha : a ∈ Nets.postsetₜ N t) (hb : b ∈ Nets.presetₜ N t) :
                                  theorem no_causal_on_postset {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (ha : a ∈ Nets.postsetₜ N t) (hb : b ∈ Nets.postsetₜ N t) :
                                  theorem no_preorder_on_postset {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (ne : a ≠ b) (ha : a ∈ Nets.postsetₜ N t) (hb : b ∈ Nets.postsetₜ N t) :
                                  theorem causal_init {α β : Type} {t : β} {N : Nets.Net α β} {x y : α ⊕ β} (O : is_occurrence N) (h : Flow.causal N x y) (ht : Flow.immediate N (Sum.inr t) y) :
                                  theorem causal_inr_inr_split {α β : Type} {t t' : β} {N : Nets.Net α β} (h : Flow.causal N (Sum.inr t) (Sum.inr t')) :
                                  ∃ (a : α), Flow.causal N (Sum.inr t) (Sum.inl a) ∧ Flow.causal N (Sum.inl a) (Sum.inr t')
                                  theorem not_mem_pre_of_pre_cause {α β : Type} {t t' : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (hb : Flow.immediate N (Sum.inl b) (Sum.inr t')) (h : b ∈ Nets.presetₜ N t) :
                                  theorem no_causal_of_mem_prea {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (ha : Flow.causal N (Sum.inl a) (Sum.inl b)) (hb : Flow.causal N (Sum.inl b) (Sum.inr t)) :
                                  a ∉ Nets.presetₜ N t
                                  theorem no_causal_of_mem_pre {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (ha : a ∈ Nets.presetₜ N t) (hb : b ∈ Nets.presetₜ N t) :
                                  theorem no_conflicts_on_postset {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (ha : a ∈ Nets.postsetₜ N t) (hb : b ∈ Nets.postsetₜ N t) :
                                  theorem no_self_conflict {α β : Type} {N : Nets.Net α β} {x : α ⊕ β} (O : is_occurrence N) :

                                  In a concurrent set stands for elements that are able to occur concurrently, i.e., they are not in conflict, and they do not causally depend on each other.

                                  def concurrent {α β : Type} (N : Nets.Net α β) (x y : α ⊕ β) :
                                  Equations
                                  Instances For
                                    Equations
                                    • One or more equations did not get rendered due to their size.
                                    Instances For
                                      @[simp]
                                      theorem co_symm {α β : Type} {N : Nets.Net α β} {x y : α ⊕ β} (h : concurrent N x y) :
                                      theorem concurrent_from_same_preset {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (ne : a ≠ b) (ha : a ∈ Nets.presetₜ N t) (hb : b ∈ Nets.presetₜ N t) :
                                      theorem concurrent_from_same_postset {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (O : is_occurrence N) (ne : a ≠ b) (ha : a ∈ Nets.postsetₜ N t) (hb : b ∈ Nets.postsetₜ N t) :
                                      theorem no_conflict_of_concurrent {α β : Type} {N : Nets.Net α β} {x y : α ⊕ β} (h : concurrent N x y) :
                                      def concurrent_set {α β : Type} (N : Nets.Net α β) (X : Multiset (α ⊕ β)) :
                                      Equations
                                      Instances For
                                        def Concurrent {α β : Type} (N : Nets.Net α β) (m : Multiset α) :
                                        Equations
                                        Instances For
                                          theorem no_concurrent_of_mem_pre_mem_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {m : Multiset α} {b : α} (O : is_occurrence N) (ha : a ∈ m) (hb : b ∈ m) (ha' : a ∈ Nets.presetₜ N t) (hb' : b ∈ Nets.postsetₜ N t) :
                                          theorem post_disjoint_of_contains_pre {α β : Type} {t : β} {N : Nets.Net α β} {m : Multiset α} [DecidableEq α] (O : is_occurrence N) (C : Concurrent N m) (e : Nets.presetₜ N t ≤ m) :
                                          theorem pre_disjoint_of_contains_post {α β : Type} {t : β} {N : Nets.Net α β} {m : Multiset α} [DecidableEq α] (O : is_occurrence N) (C : Concurrent N m) (e : Nets.postsetₜ N t ≤ m) :
                                          theorem no_concurrent_of_contains_cause_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {m : Multiset α} {b : α} [DecidableEq α] (O : is_occurrence N) (en : Nets.presetₜ N t ≤ m) (ha : a ∈ m - Nets.presetₜ N t) (hb : b ∈ Nets.postsetₜ N t) (h : Flow.causal N (Sum.inl a) (Sum.inl b)) :
                                          theorem no_concurrent_of_depends_on_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {m : Multiset α} {b : α} [DecidableEq α] (en : Nets.presetₜ N t ≤ m) (ha : a ∈ m - Nets.presetₜ N t) (hb : b ∈ Nets.postsetₜ N t) (h : Flow.preorder N (Sum.inl b) (Sum.inl a)) :
                                          theorem no_concurrent_of_contains_conflicting_cause {α β : Type} {a : α} {t t' : β} {N : Nets.Net α β} {m : Multiset α} [DecidableEq α] (en : Nets.presetₜ N t ≤ m) (ha : a ∈ m - Nets.presetₜ N t) (h : Flow.causal N (Sum.inr t') (Sum.inl a)) (c : immediate_conflict N t' t) :
                                          theorem no_concurrent_of_conflicting_causes {α β : Type} {a : α} {t t' t'' : β} {N : Nets.Net α β} {m : Multiset α} [DecidableEq α] (en : Nets.presetₜ N t ≤ m) (ha : a ∈ m - Nets.presetₜ N t) (h : Flow.causal N (Sum.inr t') (Sum.inl a)) (h' : Flow.causal N (Sum.inr t'') (Sum.inr t)) (c : immediate_conflict N t' t'') :
                                          theorem no_conflict_of_concurrent_preset_postset {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {m : Multiset α} {b : α} [DecidableEq α] (O : is_occurrence N) (e : Nets.presetₜ N t ≤ m) (ha : a ∈ m - Nets.presetₜ N t) (hb : b ∈ Nets.postsetₜ N t) (cf : conflict N (Sum.inl a) (Sum.inl b)) :
                                          theorem in_conc_postset_concurrent {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {m : Multiset α} {b : α} [DecidableEq α] (O : is_occurrence N) (C : Concurrent N m) (e : Nets.presetₜ N t ≤ m) (ne : a ≠ b) (ha : a ∈ m - Nets.presetₜ N t) (hb : b ∈ Nets.postsetₜ N t) :
                                          theorem conc_mem_pre_of_conc_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {x : α ⊕ β} {b : α} (ha : a ∈ Nets.presetₜ N t) (hb : b ∈ Nets.postsetₜ N t) (h : concurrent N x (Sum.inl b)) (h' : ¬Flow.preorder N (Sum.inl a) x) :
                                          theorem not_refl_of_not_trans {α β : Type} {x y : α ⊕ β} {r : α ⊕ β → α ⊕ β → Prop} (h2 : x ≠ y) (h1 : ¬Relation.TransGen r x y) :
                                          theorem ne_mem_pre_of_concurrent_mem_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (C : Concurrent N ({a} + Nets.postsetₜ N t)) (h : b ∈ Nets.presetₜ N t) :
                                          b ≠ a
                                          theorem not_causal_mem_pre_of_concurrent_postset {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (C : Concurrent N ({a} + Nets.postsetₜ N t)) (hb : b ∈ Nets.presetₜ N t) :
                                          theorem not_preorder_of_cause_of_concurrent_cause {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {x : α ⊕ β} {b : α} (C : Concurrent N ({a} + Nets.postsetₜ N t)) (hb : b ∈ Nets.presetₜ N t) (ic : Flow.immediate N (Sum.inl b) x) :
                                          theorem not_causal_concurrent_postset_of_mem_pre {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (C : Concurrent N ({a} + Nets.postsetₜ N t)) (hb : b ∈ Nets.presetₜ N t) :
                                          theorem conc_mem_pre_if_conc_mem_post {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {b : α} (C : Concurrent N ({a} + Nets.postsetₜ N t)) (h : b ∈ Nets.presetₜ N t) :
                                          theorem disjoint_add_pre_of_conc_add_post {α β : Type} {t : β} {N : Nets.Net α β} {m : Multiset α} (C : Concurrent N (m + Nets.postsetₜ N t)) :
                                          theorem nodup_add_pre_of_conc_add_post {α β : Type} {t : β} {N : Nets.Net α β} {m : Multiset α} (O : is_occurrence N) (C : Concurrent N (m + Nets.postsetₜ N t)) :
                                          theorem concurrent_of_le {α β : Type} {N : Nets.Net α β} {m m' : Multiset α} [DecidableEq α] (C : Concurrent N m) (h : m' ≤ m) :
                                          theorem conc_pre_of_conc_post {α β : Type} {t : β} {N : Nets.Net α β} {m : Multiset α} [DecidableEq α] (O : is_occurrence N) (C : Concurrent N (m + Nets.postsetₜ N t)) :
                                          theorem firing_preserves_concurrent {α β : Type} {a : α} {t : β} {N : Nets.Net α β} {m m' : Multiset α} {b : α} [DecidableEq α] (O : is_occurrence N) (C : Concurrent N m) {e : Nets.presetₜ N t ≤ m} (h : Nets.is_firing N m e m') (ha : a ∈ m') (hb : b ∈ m') (ne : a ≠ b) :
                                          theorem firing_preserves_concurrency {α β : Type} {t : β} {N : Nets.Net α β} {m m' : Multiset α} [DecidableEq α] (O : is_occurrence N) (C : Concurrent N m) {e : Nets.is_enabled N m t} (h : Nets.is_firing N m e m') :
                                          theorem firing_sequence_preserves_concurrent {α β : Type} {N : Nets.Net α β} {m m' : Multiset α} [DecidableEq α] (O : is_occurrence N) (ts : List β) (C : Concurrent N m) (f : Nets.is_firing_sequence N m ts m') :
                                          theorem minimal_places_concurrent {α β : Type} {M : ↑α β} (MO : is_marked_occurrence M) :
                                          theorem occ_net_safe {α β : Type} [DecidableEq α] {M : ↑α β} (MO : is_marked_occurrence M) :