Refining runs of the clone table
Lax369799.CloneRunRefinement · concepts/Lax369799/CloneRunRefinement.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
An accepting run of the recurrent clone table lifts to an accepting run of the original transition table on a system with isomorphic decoding. The direction map is surjective, labels increase along every branch, and the algebraic word condition is monotone.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.CloneTransitions |
| 2 | import Lax369799.BranchMonotonicity |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Refining runs of the clone table |
| 7 | type: theorem |
| 8 | --- |
| 9 | An accepting run of the recurrent clone table lifts to an accepting run |
| 10 | of the original transition table on a system with isomorphic decoding. |
| 11 | The direction map is surjective, labels increase along every branch, |
| 12 | and the algebraic word condition is monotone. |
| 13 | -/ |
| 14 | namespace Lax369799.CloneRunRefinement |
| 15 | open RankedSystems (RankedSet System) |
| 16 | open TransitionEncoding UnfoldAutomata SetSystemAlgebras |
| 17 | |
| 18 | noncomputable def fromTable {P : Type} {Y : RankedSet} [Fintype (Y 1)] [Fintype (Y 0)] |
| 19 | (T : Set P → ∀ n, Set (Fin (n + 1) → Y 1)) |
| 20 | (leaves : Set P → Set (Fin (Fintype.card (Y 0)))) |
| 21 | (D : WordCondition (Fintype.card (Y 1)) (Fintype.card (Y 0))) : |
| 22 | UnfoldAutomaton (TransitionAlphabet P) where |
| 23 | unary := Fintype.card (Y 1) |
| 24 | nullary := Fintype.card (Y 0) |
| 25 | transition := fun n ν => {b | (fun i => (Fintype.equivFin (Y 1)).symm (b i)) ∈ T ν n} |
| 26 | leafTransition := leaves |
| 27 | condition := D |
| 28 | |
| 29 | variable {P : Type} {Y : RankedSet} (E : SetAlgebra Y) |
| 30 | [Fintype (Y 1)] [Fintype (Y 0)] |
| 31 | (T : Set P → ∀ n, Set (Fin (n + 1) → Y 1)) |
| 32 | (leaves : Set P → Set (Fin (Fintype.card (Y 0)))) |
| 33 | (D : WordCondition (Fintype.card (Y 1)) (Fintype.card (Y 0))) |
| 34 | (S : System (TransitionAlphabet P) 0) |
| 35 | (r : Run (CloneTransitions.automaton (CloneTransitions.beta E T) leaves D) S) |
| 36 | |
| 37 | axiom run_refinement |
| 38 | (hD : Lax369799.BranchMonotonicity.ConditionMonotone E D) (hr : r.Accepting) : |
| 39 | ∃ U : System (TransitionAlphabet P) 0, Isomorphic (decode U) (decode S) ∧ |
| 40 | ∃ s : Run (fromTable T leaves D) U, s.Accepting |
| 41 | |
| 42 | end Lax369799.CloneRunRefinement |
| 43 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments