Model checking along a construction sequence

Lax185574.ConstructionModelChecking · concepts/Lax185574/ConstructionModelChecking.lean · lax-185574

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

    There is an algorithm which, given a sentence φ and an n-vertex graph G together with a construction sequence of G of length λ, determines whether G ⊨ φ in time

    λ · n² · poly_φ(K),

    where K is the radius-r depth-d width of the construction sequence, for some r and d that depend only on φ.

    Concept map
    13 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    In the paper

    • page 15 of this submission's paper

    Lean source view on GitHub

    1import Lax185574.Algorithms
    2import Lax185574.ConstructionSequences
    3import Lax185574.Width
    4
    5/-!
    6---
    7title: Model checking along a construction sequence
    8type: theorem
    9---
    10There is an algorithm which, given a sentence φ and an n-vertex graph G
    11together with a construction sequence of G of length λ, determines
    12whether G ⊨ φ in time
    13
    14λ · n² · poly_φ(K),
    15
    16where K is the radius-r depth-d width of the construction sequence, for
    17some r and d that depend only on φ.
    18
    19# Formalization notes
    20
    21The algorithm is an algorithm in the sense of `Lax185574.Algorithms`,
    22one for all sentences. For each sentence there are the radius `r`, the
    23depth `d`, the degree `b` and the constant `c` of the time bound. The
    24input is the triple of G, a script of the construction sequence and φ,
    25with the encodings of `Lax185574.Encodings`. The construction sequence
    26is the run of the script, see `Lax185574.ConstructionSequences`, so λ is
    27the length of the run. K is the width of `Lax185574.Width`.
    28
    29The time bound λ · n² · poly_φ(K) is spelled out as
    30`λ · (n+1)² · (K+1)^b`. The graph without vertices has construction
    31sequences of every length, and the factor (n+1)² keeps the bound large
    32enough to read them. The paper says that r and d are computable from
    33φ. Here they only exist. The algorithm is correct on every construction
    34sequence, whatever its width. So an algorithm that needs r and d can try
    35all pairs in parallel, and the right pair costs only a constant factor
    36that depends on φ.
    37-/
    38
    39namespace Lax185574.ConstructionModelChecking
    40
    41open Lax185574.Graphs Lax185574.FirstOrderLogic Lax185574.Algorithms
    42open Lax185574.ConstructionSequences Lax185574.Width
    43
    44/-- **Model checking along a construction sequence.** One algorithm
    45decides `G ⊨ φ`, given `G`, a construction sequence of `G` by its
    46script `σ`, and `φ`, in time `O(λ · (n+1)² · (K+1)^b)`, where `λ` is
    47the length of the sequence and `K` its radius-`r` depth-`d` width. The
    48numbers `r`, `d`, `b` and the constant `c` depend on `φ`. -/
    49axiom exists_program_modelChecking_sequence :
    50 ∃ A : Algorithm, ∀ φ : Sentence, ∃ r d c b : ℕ,
    51 ∀ (G : Graph) (σ : Script G.n), IsConstructionSequence G.toSimpleGraph σ.run →
    52 A.Decides c (G, σ, φ) (G ⊨ φ)
    53 (σ.run.length * (G.n + 1) ^ 2 * (width r d σ.run + 1) ^ b)
    54
    55end Lax185574.ConstructionModelChecking
    56
    Show Proof
    Formalization notes

    The algorithm is an algorithm in the sense of Lax185574.AlgorithmsLax185574.Algorithms, one for all sentences. For each sentence there are the radius rr, the depth dd, the degree bb and the constant cc of the time bound. The input is the triple of G, a script of the construction sequence and φ, with the encodings of Lax185574.EncodingsLax185574.Encodings. The construction sequence is the run of the script, see Lax185574.ConstructionSequencesLax185574.ConstructionSequences, so λ is the length of the run. K is the width of Lax185574.WidthLax185574.Width.

    The time bound λ · n² · poly_φ(K) is spelled out as λ⋅(n+1)2⋅(K+1)bλ · (n+1)² · (K+1)^b. The graph without vertices has construction sequences of every length, and the factor (n+1)² keeps the bound large enough to read them. The paper says that r and d are computable from φ. Here they only exist. The algorithm is correct on every construction sequence, whatever its width. So an algorithm that needs r and d can try all pairs in parallel, and the right pair costs only a constant factor that depends on φ.

    Discussion

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

    Loading discussion…