Accepting runs and modal game plays
Lax369799.AutomatonRunGame · concepts/Lax369799/AutomatonRunGame.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Every accepting run supplies winning modal choices. Finite branches use the final-state test, while infinite branches use the parity condition. Inserting zero-priority marking positions between word positions does not alter the acceptance condition.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.ModalAcceptanceGame |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Accepting runs and modal game plays |
| 6 | type: theorem |
| 7 | --- |
| 8 | Every accepting run supplies winning modal choices. Finite branches use |
| 9 | the final-state test, while infinite branches use the parity condition. |
| 10 | Inserting zero-priority marking positions between word positions does |
| 11 | not alter the acceptance condition. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.AutomatonRunGame |
| 15 | open TransitionEncoding TransitionSystems UnfoldAutomata ModalAcceptanceGame |
| 16 | |
| 17 | axiom parity_interleave {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 18 | (S : TransitionSystem P) (w : ℕ → Fin M.unary) (p : ℕ → Vertex M S) |
| 19 | (he : ∀ n, (game M S).priority (p (2*n)) = |
| 20 | ceiling M.condition - M.condition.priority (M.condition.run w n)) |
| 21 | (ho : ∀ n, (game M S).priority (p (2*n+1)) = 0) : |
| 22 | M.condition.AcceptsInfinite w ↔ (game M S).EveWins p |
| 23 | |
| 24 | axiom run_winning {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 25 | {S : RankedSystems.System (TransitionAlphabet P) 0} (r : Run M S) (hr : r.Accepting) : |
| 26 | ParityWinningRegions.Winning (game M (decode S)) true |
| 27 | (position M.condition.initial (decode S).initial) |
| 28 | |
| 29 | end Lax369799.AutomatonRunGame |
| 30 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments