Computable bounds for the algebraic branch automaton
Lax369799.QuantitativeWordConditions · concepts/Lax369799/QuantitativeWordConditions.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The linked-pair automaton stores three elements of the unary monoid and two flags. Determinization and the finite-word evaluator give explicit state and priority bounds from the unary and nullary sort bounds.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax369799.QuantitativeDeterminization |
| 2 | import Lax369799.AlgebraicBranchCondition |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Computable bounds for the algebraic branch automaton |
| 7 | type: theorem |
| 8 | --- |
| 9 | The linked-pair automaton stores three elements of the unary monoid and |
| 10 | two flags. Determinization and the finite-word evaluator give explicit |
| 11 | state and priority bounds from the unary and nullary sort bounds. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.QuantitativeWordConditions |
| 15 | |
| 16 | def buchiBound (u : ℕ) : ℕ := 4*(u+1)^3 |
| 17 | |
| 18 | def stateBound (u z : ℕ) : ℕ := |
| 19 | QuantitativeDeterminization.stateBound (buchiBound u) * (z^z+z+1) |
| 20 | |
| 21 | def priorityBound (u : ℕ) : ℕ := |
| 22 | QuantitativeDeterminization.priorityBound (buchiBound u) |
| 23 | |
| 24 | open UnfoldAutomata |
| 25 | |
| 26 | axiom exists_condition {A : RankedSystems.RankedSet} (E : FiniteSyntacticAlgebra.Algebra A) |
| 27 | (F : Set (A 0)) [Fintype (A 1)] [Fintype (A 0)] |
| 28 | (u z : ℕ) (hu : Fintype.card (A 1) ≤ u) (hz : Fintype.card (A 0) ≤ z) : |
| 29 | ∃ D : WordCondition (Fintype.card (A 1)) (Fintype.card (A 0)), |
| 30 | (∀ w a,D.AcceptsFinite w a ↔ FiniteBranchWords.value E |
| 31 | (w.map (Fintype.equivFin (A 1)).symm) ((Fintype.equivFin (A 0)).symm a) ∈ F) ∧ |
| 32 | (∀ w,D.AcceptsInfinite w ↔ AlgebraicOmegaWords.Accepts E F |
| 33 | (fun n => (Fintype.equivFin (A 1)).symm (w n))) ∧ |
| 34 | D.states ≤ stateBound u z ∧ (∀ q,D.priority q ≤ priorityBound u) |
| 35 | |
| 36 | end Lax369799.QuantitativeWordConditions |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments