Unary normal form of deterministic elements
Lax369799.DeterministicElements · concepts/Lax369799/DeterministicElements.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
In a set-algebra, every deterministic element of positive rank is a parallel family of unary values, one at each variable. This is the characterization in the earlier draft. The set-algebra hypothesis includes continuity; it is not implicit in an arbitrary substitution algebra. DirectionProjections proves the revised canonical decomposition for extremal elements without that continuity hypothesis.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.AutomatonProperty |
| 2 | import Lax369799.UnarySystems |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Unary normal form of deterministic elements |
| 7 | type: theorem |
| 8 | --- |
| 9 | In a set-algebra, every deterministic element of positive rank is a |
| 10 | parallel family of unary values, one at each variable. This is the |
| 11 | characterization in the earlier draft. The set-algebra hypothesis includes |
| 12 | continuity; it is not implicit in an arbitrary substitution algebra. |
| 13 | DirectionProjections proves the revised canonical decomposition for |
| 14 | extremal elements without that continuity hypothesis. |
| 15 | -/ |
| 16 | namespace Lax369799.DeterministicElements |
| 17 | open RankedSystems SetAlgebras AutomatonProperty |
| 18 | |
| 19 | /-- Retain a chosen variable and rename it to the sole output variable. -/ |
| 20 | def projection {A : RankedSet} {n : ℕ} (S : SetSystem A n) (i : Fin n) : SetSystem A 1 where |
| 21 | size := S.size |
| 22 | graph := { |
| 23 | label := S.graph.label |
| 24 | initial := S.graph.initial |
| 25 | root := S.graph.root |
| 26 | edge := fun v d t => S.graph.edge v d (Sum.map id (fun _ => i) t) |
| 27 | direction_valid := fun v d _t h => S.graph.direction_valid v d _ h } |
| 28 | reachable := S.reachable |
| 29 | |
| 30 | /-- The disjoint unary letters b_i, with each sole edge going to x_i. -/ |
| 31 | def parallel {A : RankedSet} {n : ℕ} (b : Fin n → A 1) : SetSystem A n where |
| 32 | size := n |
| 33 | graph := { |
| 34 | label := fun v => ⟨1, b v⟩ |
| 35 | initial := Set.univ |
| 36 | root := ∅ |
| 37 | edge := fun v d t => d = 0 ∧ t = .inr v |
| 38 | direction_valid := by rintro v d t ⟨rfl, _⟩; exact Nat.zero_lt_one } |
| 39 | reachable := fun v => ⟨v, Or.inl trivial, .refl⟩ |
| 40 | |
| 41 | axiom unary_normal_form {A : RankedSet} (E : SetAlgebra A) {n : ℕ} (hn : 0 < n) |
| 42 | (a : A n) : Deterministic E a ↔ ∃ b : Fin n → A 1, E.eval n (parallel b) = a |
| 43 | |
| 44 | end Lax369799.DeterministicElements |
| 45 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments