Effective translation of bisimulation-invariant finite MSO
Lax369799.EffectiveFiniteTranslation · concepts/Lax369799/EffectiveFiniteTranslation.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The algorithm is total on all MSO sentences over an explicitly encoded finite vocabulary. It enumerates bounded modal transition tables and selects a compiled sentence by finite graph tests. Under the promised finite bisimulation invariance, the selected sentence agrees on every finite reachable transition system. No invariance decision is required. This formalizes the effectivity argument following Theorem 2.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax369799.FiniteTesting |
| 2 | import Lax369799.QuantitativeFiniteTheorem |
| 3 | import Mathlib.Data.List.ProdSigma |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Effective translation of bisimulation-invariant finite MSO |
| 8 | type: theorem |
| 9 | --- |
| 10 | The algorithm is total on all MSO sentences over an explicitly encoded |
| 11 | finite vocabulary. It enumerates bounded modal transition tables and |
| 12 | selects a compiled sentence by finite graph tests. Under the promised |
| 13 | finite bisimulation invariance, the selected sentence agrees on every |
| 14 | finite reachable transition system. No invariance decision is required. |
| 15 | This formalizes the effectivity argument following Theorem 2. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax369799.EffectiveFiniteTranslation |
| 19 | open ModalMuCalculus |
| 20 | |
| 21 | def candidates {P : Type} [Fintype P] [Encodable P] [DecidableEq P] |
| 22 | (φ : MonadicSecondOrder.Sentence P) : List (Sentence P) := |
| 23 | let f := QuantitativeRecognition.msoBound φ |
| 24 | (List.range (QuantitativeAutomata.unaryBound f+1)).flatMap (fun u => |
| 25 | (List.range (QuantitativeAutomata.nullaryBound f+1)).flatMap (fun z => |
| 26 | (List.range (QuantitativeAutomata.stateBound f+1)).flatMap (fun d => |
| 27 | (FiniteModalData.elements (FiniteModalData.Data P u z d (QuantitativeAutomata.priorityBound f))).map |
| 28 | FiniteModalData.compile))) |
| 29 | |
| 30 | def conjunction {P : Type} (φ ψ : MonadicSecondOrder.Sentence P) : MonadicSecondOrder.Sentence P := |
| 31 | .neg (.disj (.neg φ) (.neg ψ)) |
| 32 | |
| 33 | def difference {P : Type} (ψ χ : Sentence P) : MonadicSecondOrder.Sentence P := |
| 34 | .disj (conjunction (UnrestrictedLogic.sentence ψ) (.neg (UnrestrictedLogic.sentence χ))) |
| 35 | (conjunction (.neg (UnrestrictedLogic.sentence ψ)) (UnrestrictedLogic.sentence χ)) |
| 36 | |
| 37 | def separationBound {P : Type} (cs : List (Sentence P)) : ℕ := |
| 38 | ((cs.product cs).map (fun e => QuantitativeFiniteTheorem.modelBound (difference e.1 e.2))).foldr max 0 |
| 39 | |
| 40 | def compile {P : Type} [Fintype P] [Encodable P] [DecidableEq P] |
| 41 | (φ : MonadicSecondOrder.Sentence P) : Sentence P := |
| 42 | let cs := candidates φ |
| 43 | (cs.find? (fun ψ => FiniteTesting.test (separationBound cs) φ ψ)).getD .bot |
| 44 | |
| 45 | open TransitionSystems |
| 46 | |
| 47 | axiom mu_translation_correct {P : Type} (ψ : Sentence P) (S : TransitionSystem P) : |
| 48 | Models S ψ ↔ MonadicSecondOrder.Models S (UnrestrictedLogic.sentence ψ) |
| 49 | |
| 50 | -- Compiler correctness is the effective theorem in FiniteBisimulationTheorem. |
| 51 | -- Keep one Archive statement for this result. |
| 52 | |
| 53 | end Lax369799.EffectiveFiniteTranslation |
| 54 |
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments