Reindexing the outgoing directions at each vertex
Lax369799.DirectionReindexing · concepts/Lax369799/DirectionReindexing.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Replace the directions at every vertex by a finite set mapping surjectively onto the original directions. Successors and valuations are preserved after forgetting direction order and multiplicity. The resulting deterministic system has an isomorphic decoding, as used in the cloning and rerouting constructions of Lemma 108.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.TransitionEncoding |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Reindexing the outgoing directions at each vertex |
| 6 | type: theorem |
| 7 | --- |
| 8 | Replace the directions at every vertex by a finite set mapping |
| 9 | surjectively onto the original directions. Successors and valuations |
| 10 | are preserved after forgetting direction order and multiplicity. The |
| 11 | resulting deterministic system has an isomorphic decoding, as used in |
| 12 | the cloning and rerouting constructions of Lemma 108. |
| 13 | -/ |
| 14 | |
| 15 | namespace Lax369799.DirectionReindexing |
| 16 | open RankedSystems TransitionEncoding |
| 17 | |
| 18 | structure Reindexing {P : Type} (S : System (TransitionAlphabet P) 0) where |
| 19 | arity : S.val.Vertex → ℕ |
| 20 | map : ∀ v, Fin (arity v) → Fin (S.val.graph.label v).1 |
| 21 | surjective : ∀ v, Function.Surjective (map v) |
| 22 | |
| 23 | def graph {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) : |
| 24 | Presentation (TransitionAlphabet P) 0 S.val.Vertex where |
| 25 | label := fun v => ⟨R.arity v, (S.val.graph.label v).2⟩ |
| 26 | initial := S.val.graph.initial |
| 27 | root := ∅ |
| 28 | edge := fun v d t => ∃ i : Fin (R.arity v), d = i.val ∧ S.val.graph.edge v (R.map v i).val t |
| 29 | direction_valid := by rintro v d t ⟨i, rfl, _⟩; exact i.isLt |
| 30 | |
| 31 | structure Realizes {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) |
| 32 | (T : System (TransitionAlphabet P) 0) where |
| 33 | vertex : T.val.Vertex ≃ S.val.Vertex |
| 34 | label : ∀ v, T.val.graph.label v = ⟨R.arity (vertex v), (S.val.graph.label (vertex v)).2⟩ |
| 35 | initial : ∀ v, T.val.graph.initial v ↔ S.val.graph.initial (vertex v) |
| 36 | edge : ∀ v d t, T.val.graph.edge v d t ↔ |
| 37 | ∃ i : Fin (R.arity (vertex v)), d = i.val ∧ |
| 38 | S.val.graph.edge (vertex v) (R.map (vertex v) i).val (Sum.map vertex id t) |
| 39 | |
| 40 | /-- Canonical realization, retaining exactly the original vertex type. -/ |
| 41 | def system {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) : |
| 42 | System (TransitionAlphabet P) 0 := by |
| 43 | let G := graph S R |
| 44 | have hstep {v w : S.val.Vertex} (h : S.val.graph.Step v w) : G.Step v w := by |
| 45 | obtain ⟨d, hd⟩ := h |
| 46 | let i : Fin (S.val.graph.label v).1 := ⟨d, S.val.graph.direction_valid _ _ _ hd⟩ |
| 47 | obtain ⟨j, hj⟩ := R.surjective v i |
| 48 | exact ⟨j.val, j, rfl, by simpa only [hj] using hd⟩ |
| 49 | have hreach (v : S.val.Vertex) : G.Reachable v := by |
| 50 | obtain ⟨a, ha, hp⟩ := S.val.reachable v |
| 51 | have hi : S.val.graph.initial a := ha.elim id (fun h => by rw [S.property.2.1] at h; exact h.elim) |
| 52 | refine ⟨a, Or.inl hi, ?_⟩ |
| 53 | induction hp with |
| 54 | | refl => exact .refl |
| 55 | | @tail y z hp hyz ih => exact ih.tail (hstep hyz) |
| 56 | let U : SetSystem (TransitionAlphabet P) 0 := ⟨S.val.size, G, hreach⟩ |
| 57 | have hdet : U.Deterministic := by |
| 58 | refine ⟨S.property.1, rfl, ?_⟩ |
| 59 | intro v d hd |
| 60 | let i : Fin (R.arity v) := ⟨d, hd⟩ |
| 61 | obtain ⟨t, ht, hu⟩ := S.property.2.2 v (R.map v i).val (R.map v i).isLt |
| 62 | refine ⟨t, ⟨i, rfl, ht⟩, ?_⟩ |
| 63 | rintro t' ⟨j, hj, ht'⟩ |
| 64 | have hji : j = i := Fin.ext hj.symm |
| 65 | subst j |
| 66 | exact hu t' ht' |
| 67 | exact ⟨U, hdet⟩ |
| 68 | |
| 69 | /-- Its realization map is the identity on vertices. -/ |
| 70 | def realizes {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) : |
| 71 | Realizes S R (system S R) where |
| 72 | vertex := Equiv.refl _ |
| 73 | label := fun _ => rfl |
| 74 | initial := fun _ => Iff.rfl |
| 75 | edge := by intro v d t; cases t <;> exact Iff.rfl |
| 76 | |
| 77 | |
| 78 | axiom zero_iff {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) |
| 79 | (v : S.val.Vertex) : R.arity v = 0 ↔ (S.val.graph.label v).1 = 0 |
| 80 | |
| 81 | axiom realization {P : Type} (S : System (TransitionAlphabet P) 0) (R : Reindexing S) : |
| 82 | ∃ T, Nonempty (Realizes S R T) |
| 83 | |
| 84 | axiom decode_isomorphic {P : Type} {S T : System (TransitionAlphabet P) 0} |
| 85 | (R : Reindexing S) (h : Realizes S R T) : Isomorphic (decode T) (decode S) |
| 86 | |
| 87 | end Lax369799.DirectionReindexing |
| 88 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments