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

Quantitative automata for the finite bisimulation theorem

Lax369799.QuantitativeAutomata · concepts/Lax369799/QuantitativeAutomata.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 bound for the recognizing algebra gives explicit bounds for the unary and nullary types, word states and priorities of the equivalent clone automaton. The infinite stabilization defining its transition table does not change any of these finite bounds.

    Concept map
    42 concepts; 3 descendants hidden
    100%
    A common condition for finite and infinitealgebraic branch wordsThe algebraic condition on infinite branchwordsAlgebras and recognitionClone-automataClone-automaton normal form and modaltranslationCombining finite and infinite branchconditionsYield acceptance of finite presentationsFinite-state evaluation of terminating branchwordsContexts over finite presentationsContextual preorders on finite presentationsFinite presentations without reachabilitypruningContextual quotient algebras of finitepresentationsFlattening and contextsFlattening, resolutions, and yield congruenceInfinite Ramsey theorem for pairsMSO-definable languages are algebraicallyrecognisableModal mu-calculusMonadic second-order logic on transitionsystemsMorphisms, unfoldings, and yieldsDeterminization of infinite-word automataRegular infinite products of linked pairsQuantitative automata for the finitebisimulation theoremExplicit state and priority bounds for worddeterminizationComputable bounds on the syntactic nullaryand unary sortsComputable bounds for MSO recognizingalgebrasComputable bounds for the algebraic branchautomatonRanked sets, set-systems, and systemsRenaming variables in systems andresolutionsResolutions and bounded profilesStable factorization with recurrent verticesThe earlier continuity-bearing set-algebrainterfacePure second-order syntaxTranslation to pure second-order logicAlgebras on fully supported systemsSystems with all output variables reachableYield-syntactic order and quotientRanked encodings of transition systemsFinite transition systems and bisimulationThe unary semigroup and its actionStable factorization of algebraic branchwordsUnfold-automata and regular-tree acceptanceIdempotent factorization of infinite words
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.QuantitativeProfiles
    2import Lax369799.QuantitativeWordConditions
    3import Lax369799.BisimAutomatonTheorem
    4
    5/-!
    6---
    7title: Quantitative automata for the finite bisimulation theorem
    8type: theorem
    9---
    10A bound for the recognizing algebra gives explicit bounds for the unary
    11and nullary types, word states and priorities of the equivalent clone
    12automaton. The infinite stabilization defining its transition table does
    13not change any of these finite bounds.
    14-/
    15
    16namespace Lax369799.QuantitativeAutomata
    17
    18def unaryBound (f : ℕ → ℕ) := QuantitativeProfiles.quotientBound f 1
    19def nullaryBound (f : ℕ → ℕ) := QuantitativeProfiles.quotientBound f 0
    20
    21def stateBound (f : ℕ → ℕ) :=
    22 QuantitativeWordConditions.stateBound (unaryBound f) (nullaryBound f)
    23
    24def priorityBound (f : ℕ → ℕ) :=
    25 QuantitativeWordConditions.priorityBound (unaryBound f)
    26
    27open TransitionEncoding UnfoldAutomata
    28
    29axiom automaton_bound {P : Type} [Finite P]
    30 (L : Algebras.Language (TransitionAlphabet P))
    31 (hL : ∀ S T,RankedBisimilar S T → (S ∈ L ↔ T ∈ L))
    32 (f : ℕ → ℕ) (hA : QuantitativeRecognition.Bound f L) :
    33 ∃ M : UnfoldAutomaton (TransitionAlphabet P),
    34 BisimAutomata.IsBisimAutomaton M ∧ Recognizes M L ∧
    35 M.unary ≤ unaryBound f ∧ M.nullary ≤ nullaryBound f ∧
    36 M.condition.states ≤ stateBound f ∧ (∀ q,M.condition.priority q ≤ priorityBound f)
    37
    38end Lax369799.QuantitativeAutomata
    Show Proof

    Discussion

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

    Loading discussion…