Combining finite and infinite branch conditions
Lax369799.CombinedWordCondition · concepts/Lax369799/CombinedWordCondition.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The finite-word evaluator can be combined with any parity condition on infinite words. The product reads both components in parallel, uses the parity component's priorities, and tests the evaluator's final state on terminating words.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FiniteBranchWords |
| 2 | import Lax369799.UnfoldAutomata |
| 3 | import Mathlib.Data.Fintype.Prod |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Combining finite and infinite branch conditions |
| 8 | type: theorem |
| 9 | --- |
| 10 | The finite-word evaluator can be combined with any parity condition on |
| 11 | infinite words. The product reads both components in parallel, uses the |
| 12 | parity component's priorities, and tests the evaluator's final state on |
| 13 | terminating words. |
| 14 | -/ |
| 15 | namespace Lax369799.CombinedWordCondition |
| 16 | open UnfoldAutomata FiniteBranchWords |
| 17 | |
| 18 | noncomputable def combine {u z : ℕ} (D : WordCondition u z) |
| 19 | (f : Fin u → Fin z → Fin z) (F : Set (Fin z)) : WordCondition u z := by |
| 20 | classical |
| 21 | let Q := Fin D.states × State (Fin z) |
| 22 | let e := Fintype.equivFin Q |
| 23 | exact { |
| 24 | states := Fintype.card Q |
| 25 | initial := e (D.initial, (machine f F).start) |
| 26 | step := fun q a => e (D.step (e.symm q).1 a, (machine f F).step (e.symm q).2 a) |
| 27 | priority := fun q => D.priority (e.symm q).1 |
| 28 | final := {q | (e.symm q).2 ∈ (machine f F).accept} } |
| 29 | |
| 30 | axiom finite_iff {u z : ℕ} (D : WordCondition u z) |
| 31 | (f : Fin u → Fin z → Fin z) (F : Set (Fin z)) |
| 32 | (w : List (Fin u)) (a : Fin z) : |
| 33 | (combine D f F).AcceptsFinite w a ↔ w.foldr f a ∈ F |
| 34 | |
| 35 | axiom infinite_iff {u z : ℕ} (D : WordCondition u z) |
| 36 | (f : Fin u → Fin z → Fin z) (F : Set (Fin z)) |
| 37 | (w : ℕ → Fin u) : |
| 38 | (combine D f F).AcceptsInfinite w ↔ D.AcceptsInfinite w |
| 39 | |
| 40 | end Lax369799.CombinedWordCondition |
| 41 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments