Compressed transitions and their clone closure
Lax369799.CloneTransitions · concepts/Lax369799/CloneTransitions.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Lemma 108 compresses each block of directions by taking the meet of its unary labels, retains the compressed tuples occurring infinitely often, and closes them under uniform duplication. The closure is a clone table, and one threshold controls all compressed transition families appearing in a finite input system.
Concept map
Evidence
This concept declares 6 statements. Each proof establishes one of them relative to its assumptions.
1 clone_automaton proven
2 closure_closed proven
3 component proven
4 refinement proven
5 stabilizes proven
6 uniform_stabilization proven
Lean source view on GitHub
| 1 | import Lax369799.BisimAutomata |
| 2 | import Lax369799.FiniteRecurrence |
| 3 | import Lax369799.FiniteAlgebraMeets |
| 4 | import Mathlib.Logic.Equiv.Fin.Basic |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Compressed transitions and their clone closure |
| 9 | type: theorem |
| 10 | --- |
| 11 | Lemma 108 compresses each block of directions by taking the meet of its |
| 12 | unary labels, retains the compressed tuples occurring infinitely often, |
| 13 | and closes them under uniform duplication. The closure is a clone table, |
| 14 | and one threshold controls all compressed transition families appearing |
| 15 | in a finite input system. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax369799.CloneTransitions |
| 19 | open RankedSystems (RankedSet) |
| 20 | open SetSystemAlgebras BisimAutomata UnfoldAutomata TransitionEncoding |
| 21 | |
| 22 | def Closure {H : Type} (B : ∀ n, Set (Fin n → H)) (n : ℕ) : Set (Fin n → H) := |
| 23 | {b | ∃ p m, 0 < p ∧ 0 < m ∧ ∃ h : p * m = n, |
| 24 | ∃ c ∈ B p, b = fun i => Duplicate c (Fin.cast h.symm i)} |
| 25 | |
| 26 | def compress {A : RankedSet} (E : SetAlgebra A) {n k : ℕ} |
| 27 | (b : Fin (n * k) → A 1) : Fin n → A 1 := |
| 28 | fun i => FiniteAlgebraMeets.value E (fun j : Fin k => b (finProdFinEquiv (i, j))) |
| 29 | |
| 30 | def alpha {A : RankedSet} {V : Type} (E : SetAlgebra A) |
| 31 | (T : V → ∀ n, Set (Fin (n + 1) → A 1)) (ν : V) (n k : ℕ) : Set (Fin n → A 1) := |
| 32 | {c | ∃ (l : ℕ) (h : n * k = l + 1) (b : Fin (l + 1) → A 1), |
| 33 | b ∈ T ν l ∧ compress E (fun i => b (Fin.cast h i)) = c} |
| 34 | |
| 35 | def beta {A : RankedSet} {V : Type} (E : SetAlgebra A) |
| 36 | (T : V → ∀ n, Set (Fin (n + 1) → A 1)) (ν : V) (n : ℕ) : Set (Fin n → A 1) := |
| 37 | FiniteRecurrence.Recurrent (alpha E T ν n) |
| 38 | |
| 39 | noncomputable def automaton {P H : Type} [Fintype H] {z : ℕ} |
| 40 | (B : Set P → ∀ n, Set (Fin n → H)) (leaves : Set P → Set (Fin z)) |
| 41 | (D : WordCondition (Fintype.card H) z) : UnfoldAutomaton (TransitionAlphabet P) where |
| 42 | unary := Fintype.card H |
| 43 | nullary := z |
| 44 | transition := fun n ν => {b | (fun i => (Fintype.equivFin H).symm (b i)) ∈ Closure (B ν) (n + 1)} |
| 45 | leafTransition := leaves |
| 46 | condition := D |
| 47 | |
| 48 | axiom closure_closed {H : Type} (B : ∀ n, Set (Fin n → H)) {n m : ℕ} |
| 49 | (b : Fin n → H) (hb : b ∈ Closure B n) (hm : 0 < m) : Duplicate b ∈ Closure B (n * m) |
| 50 | |
| 51 | axiom component {A : RankedSet} (E : SetAlgebra A) {n k : ℕ} |
| 52 | (b : Fin (n * k) → A 1) (i : Fin n) (j : Fin k) : |
| 53 | Below E (compress E b i) (b (finProdFinEquiv (i, j))) |
| 54 | |
| 55 | axiom stabilizes {A : RankedSet} {V : Type} (E : SetAlgebra A) [Finite (A 1)] |
| 56 | (T : V → ∀ n, Set (Fin (n + 1) → A 1)) (ν : V) (n : ℕ) : |
| 57 | ∃ N, ∀ k, N ≤ k → alpha E T ν n k ⊆ beta E T ν n |
| 58 | |
| 59 | axiom uniform_stabilization {A : RankedSet} {V I : Type} (E : SetAlgebra A) |
| 60 | [Finite (A 1)] [Finite I] (T : V → ∀ n, Set (Fin (n + 1) → A 1)) |
| 61 | (ν : I → V) (arity : I → ℕ) : |
| 62 | ∃ N, ∀ i k, N ≤ k → alpha E T (ν i) (arity i) k ⊆ beta E T (ν i) (arity i) |
| 63 | |
| 64 | axiom clone_automaton {P H : Type} [Fintype H] {z : ℕ} |
| 65 | (B : Set P → ∀ n, Set (Fin n → H)) (leaves : Set P → Set (Fin z)) |
| 66 | (D : WordCondition (Fintype.card H) z) : IsBisimAutomaton (automaton B leaves D) |
| 67 | |
| 68 | axiom refinement {A : RankedSet} {V : Type} (E : SetAlgebra A) |
| 69 | (T : V → ∀ n, Set (Fin (n + 1) → A 1)) (ν : V) {n : ℕ} |
| 70 | (b : Fin n → A 1) (hb : b ∈ Closure (beta E T ν) n) : |
| 71 | ∃ (l : ℕ) (c : Fin (l + 1) → A 1), c ∈ T ν l ∧ |
| 72 | ∃ σ : Fin (l + 1) → Fin n, Function.Surjective σ ∧ |
| 73 | ∀ i, Below E (b (σ i)) (c i) |
| 74 | |
| 75 | end Lax369799.CloneTransitions |
| 76 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments