Explicit state and priority bounds for word determinization
Lax369799.QuantitativeDeterminization · concepts/Lax369799/QuantitativeDeterminization.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Safra positions admit padded finite-vector encodings. Bounding the full label-and-mark table and the subsequent appearance record gives numeric bounds computed from the number of nondeterministic states.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax369799.OmegaDeterminization |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Explicit state and priority bounds for word determinization |
| 6 | type: theorem |
| 7 | --- |
| 8 | Safra positions admit padded finite-vector encodings. Bounding the full |
| 9 | label-and-mark table and the subsequent appearance record gives numeric |
| 10 | bounds computed from the number of nondeterministic states. |
| 11 | -/ |
| 12 | |
| 13 | namespace Lax369799.QuantitativeDeterminization |
| 14 | |
| 15 | def safraBound (n : ℕ) : ℕ := (2^(n+1))^((n+2)^n) |
| 16 | def stateBound (n : ℕ) : ℕ := safraBound n * (safraBound n)^(safraBound n) |
| 17 | def priorityBound (n : ℕ) : ℕ := 2*safraBound n |
| 18 | |
| 19 | open UnfoldAutomata OmegaDeterminization |
| 20 | |
| 21 | axiom determinization_bound {u z : ℕ} (B : Buchi u) (bound : ℕ) (hb : B.states ≤ bound) : |
| 22 | ∃ D : WordCondition u z, |
| 23 | (∀ w,D.AcceptsInfinite w ↔ B.Accepts w) ∧ |
| 24 | D.states ≤ stateBound bound ∧ (∀ q,D.priority q ≤ priorityBound bound) |
| 25 | |
| 26 | end Lax369799.QuantitativeDeterminization |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments