While this submission is a draft, it cannot be used by other submissions.

Clone-automaton normal form and modal translation

Lax369799.BisimAutomatonTheorem · concepts/Lax369799/BisimAutomatonTheorem.lean · lax-369799

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    16 concepts; 4 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.SupportedAlgebras
    2import Lax369799.BisimAutomata
    3import Lax369799.ModalMuCalculus
    4
    5/-!
    6---
    7title: Clone-automaton normal form and modal translation
    8type: theorem
    9---
    10A bisimulation-invariant language recognised by a rankwise-finite algebra
    11has a recognising clone-automaton (Lemma 108, Section 6.4).
    12The modal translation identifies the acceptance of such an automaton with
    13a mu-calculus sentence when its recognised language is bisimulation-invariant.
    14The latter hypothesis is explicit: the duplication condition alone does
    15not assert language invariance.
    16-/
    17
    18namespace Lax369799.BisimAutomatonTheorem
    19open RankedSystems Algebras UnfoldAutomata TransitionEncoding BisimAutomata
    20
    21axiom 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. -/
    29axiom 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
    37axiom 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
    43end Lax369799.BisimAutomatonTheorem
    44
    Show ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…