Clone-automaton normal form and modal translation
Lax369799.BisimAutomatonTheorem · concepts/Lax369799/BisimAutomatonTheorem.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A bisimulation-invariant language recognised by a rankwise-finite algebra has a recognising clone-automaton (Lemma 108, Section 6.4). The modal translation identifies the acceptance of such an automaton with a mu-calculus sentence when its recognised language is bisimulation-invariant. The latter hypothesis is explicit: the duplication condition alone does not assert language invariance.
Concept map
Evidence
This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.
1 bisim_automaton_exists proven
2 bisim_automaton_runs proven
3 bisim_automaton_to_mu proven
Lean source view on GitHub
| 1 | import Lax369799.SupportedAlgebras |
| 2 | import Lax369799.BisimAutomata |
| 3 | import Lax369799.ModalMuCalculus |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Clone-automaton normal form and modal translation |
| 8 | type: theorem |
| 9 | --- |
| 10 | A bisimulation-invariant language recognised by a rankwise-finite algebra |
| 11 | has a recognising clone-automaton (Lemma 108, Section 6.4). |
| 12 | The modal translation identifies the acceptance of such an automaton with |
| 13 | a mu-calculus sentence when its recognised language is bisimulation-invariant. |
| 14 | The latter hypothesis is explicit: the duplication condition alone does |
| 15 | not assert language invariance. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax369799.BisimAutomatonTheorem |
| 19 | open RankedSystems Algebras UnfoldAutomata TransitionEncoding BisimAutomata |
| 20 | |
| 21 | axiom bisim_automaton_exists {P : Type} [Finite P] |
| 22 | (L : Language (TransitionAlphabet P)) |
| 23 | (hL : ∀ S T, RankedBisimilar S T → (S ∈ L ↔ T ∈ L)) |
| 24 | (hA : SupportedAlgebras.Recognizable L) : |
| 25 | ∃ M : UnfoldAutomaton (TransitionAlphabet P), |
| 26 | IsBisimAutomaton M ∧ UnfoldAutomata.Recognizes M L |
| 27 | |
| 28 | /-- The clone automaton admits an accepting run on each accepted presentation. -/ |
| 29 | axiom bisim_automaton_runs {P : Type} [Finite P] |
| 30 | (L : Language (TransitionAlphabet P)) |
| 31 | (hL : ∀ S T, RankedBisimilar S T → (S ∈ L ↔ T ∈ L)) |
| 32 | (hA : SupportedAlgebras.Recognizable L) : |
| 33 | ∃ M : UnfoldAutomaton (TransitionAlphabet P), |
| 34 | IsBisimAutomaton M ∧ UnfoldAutomata.Recognizes M L ∧ |
| 35 | ∀ S ∈ L, ∃ r : Run M S, r.Accepting |
| 36 | |
| 37 | axiom bisim_automaton_to_mu {P : Type} [Finite P] |
| 38 | (M : UnfoldAutomaton (TransitionAlphabet P)) (hM : IsBisimAutomaton M) |
| 39 | (hL : ∀ S T, RankedBisimilar S T → (Accepts M S ↔ Accepts M T)) : |
| 40 | ∃ φ : ModalMuCalculus.Sentence P, ∀ S, |
| 41 | Accepts M S ↔ ModalMuCalculus.Models (decode S) φ |
| 42 | |
| 43 | end Lax369799.BisimAutomatonTheorem |
| 44 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments