Substitution after restricting inner output ports
Lax369799.SupportPorts · concepts/Lax369799/SupportPorts.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Renaming the outputs of each inner system and restricting the matching outer directions produce isomorphic flattened presentations. This holds for arbitrary port maps and retains roots and output variables. The restricted outer presentation has a deterministic reachable restriction when the original outer presentation is deterministic.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FinitePresentations |
| 2 | import Lax369799.Renaming |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Substitution after restricting inner output ports |
| 7 | type: theorem |
| 8 | --- |
| 9 | Renaming the outputs of each inner system and restricting the matching |
| 10 | outer directions produce isomorphic flattened presentations. This holds |
| 11 | for arbitrary port maps and retains roots and output variables. The |
| 12 | restricted outer presentation has a deterministic reachable restriction |
| 13 | when the original outer presentation is deterministic. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.SupportPorts |
| 17 | open RankedSystems |
| 18 | |
| 19 | def expanded {A B : RankedSet} {n : ℕ} {V : Type} |
| 20 | (G : Presentation A n V) (m : V → ℕ) |
| 21 | (σ : ∀ v, Fin (m v) → Fin (G.label v).1) |
| 22 | (S : ∀ v, System B (m v)) : Presentation (System B) n V where |
| 23 | label := fun v => ⟨(G.label v).1, Renaming.renameSystem (σ v) (S v)⟩ |
| 24 | initial := G.initial |
| 25 | root := G.root |
| 26 | edge := G.edge |
| 27 | direction_valid := G.direction_valid |
| 28 | |
| 29 | def restricted {A B : RankedSet} {n : ℕ} {V : Type} |
| 30 | (G : Presentation A n V) (m : V → ℕ) |
| 31 | (σ : ∀ v, Fin (m v) → Fin (G.label v).1) |
| 32 | (S : ∀ v, System B (m v)) : Presentation (System B) n V where |
| 33 | label := fun v => ⟨m v, S v⟩ |
| 34 | initial := G.initial |
| 35 | root := G.root |
| 36 | edge := fun v d t => ∃ i : Fin (m v), d = i.val ∧ G.edge v (σ v i).val t |
| 37 | direction_valid := by rintro v d t ⟨i, rfl, _⟩; exact i.isLt |
| 38 | |
| 39 | def flattened {B : RankedSet} {n : ℕ} {V : Type} |
| 40 | (G : Presentation (System B) n V) : |
| 41 | Presentation B n ((v : V) × (G.label v).2.val.Vertex) := |
| 42 | FinitePresentations.flattenPresentation { |
| 43 | G with label := fun v => ⟨(G.label v).1, |
| 44 | FinitePresentations.ofSetSystem (G.label v).2.val⟩ } |
| 45 | |
| 46 | axiom flatten_iso {A B : RankedSet} {n : ℕ} {V : Type} |
| 47 | (G : Presentation A n V) (m : V → ℕ) |
| 48 | (σ : ∀ v, Fin (m v) → Fin (G.label v).1) (S : ∀ v, System B (m v)) : |
| 49 | Nonempty (FinitePresentations.PresentationIso |
| 50 | (flattened (expanded G m σ S)) (flattened (restricted G m σ S))) |
| 51 | |
| 52 | axiom restricted_system {A B : RankedSet} {n : ℕ} {V : Type} [Fintype V] |
| 53 | (G : Presentation A n V) (m : V → ℕ) |
| 54 | (σ : ∀ v, Fin (m v) → Fin (G.label v).1) (S : ∀ v, System B (m v)) |
| 55 | (r : V) (hi : G.initial = {r}) (hr : G.root = ∅) |
| 56 | (ht : ∀ v d, d < (G.label v).1 → ∃! t, G.edge v d t) : |
| 57 | ∃ T : System (System B) n, T.val = trim (restricted G m σ S) |
| 58 | |
| 59 | end Lax369799.SupportPorts |
| 60 | |
| 61 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments