Model checking along a construction sequence
Lax185574.ConstructionModelChecking · concepts/Lax185574/ConstructionModelChecking.lean · lax-185574
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Evidence
Each proof establishes this claim relative to its assumptions.
In the paper
- page 15 of this submission's paper
Lean source view on GitHub
| 1 | import Lax185574.Algorithms |
| 2 | import Lax185574.ConstructionSequences |
| 3 | import Lax185574.Width |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Model checking along a construction sequence |
| 8 | type: theorem |
| 9 | --- |
| 10 | There is an algorithm which, given a sentence φ and an n-vertex graph G |
| 11 | together with a construction sequence of G of length λ, determines |
| 12 | whether G ⊨ φ in time |
| 13 | |
| 14 | λ · n² · poly_φ(K), |
| 15 | |
| 16 | where K is the radius-r depth-d width of the construction sequence, for |
| 17 | some r and d that depend only on φ. |
| 18 | |
| 19 | # Formalization notes |
| 20 | |
| 21 | The algorithm is an algorithm in the sense of `Lax185574.Algorithms`, |
| 22 | one for all sentences. For each sentence there are the radius `r`, the |
| 23 | depth `d`, the degree `b` and the constant `c` of the time bound. The |
| 24 | input is the triple of G, a script of the construction sequence and φ, |
| 25 | with the encodings of `Lax185574.Encodings`. The construction sequence |
| 26 | is the run of the script, see `Lax185574.ConstructionSequences`, so λ is |
| 27 | the length of the run. K is the width of `Lax185574.Width`. |
| 28 | |
| 29 | The time bound λ · n² · poly_φ(K) is spelled out as |
| 30 | `λ · (n+1)² · (K+1)^b`. The graph without vertices has construction |
| 31 | sequences of every length, and the factor (n+1)² keeps the bound large |
| 32 | enough 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 |
| 34 | sequence, whatever its width. So an algorithm that needs r and d can try |
| 35 | all pairs in parallel, and the right pair costs only a constant factor |
| 36 | that depends on φ. |
| 37 | -/ |
| 38 | |
| 39 | namespace Lax185574.ConstructionModelChecking |
| 40 | |
| 41 | open Lax185574.Graphs Lax185574.FirstOrderLogic Lax185574.Algorithms |
| 42 | open Lax185574.ConstructionSequences Lax185574.Width |
| 43 | |
| 44 | /-- **Model checking along a construction sequence.** One algorithm |
| 45 | decides `G ⊨ φ`, given `G`, a construction sequence of `G` by its |
| 46 | script `σ`, and `φ`, in time `O(λ · (n+1)² · (K+1)^b)`, where `λ` is |
| 47 | the length of the sequence and `K` its radius-`r` depth-`d` width. The |
| 48 | numbers `r`, `d`, `b` and the constant `c` depend on `φ`. -/ |
| 49 | axiom 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 | |
| 55 | end Lax185574.ConstructionModelChecking |
| 56 |
Formalization notes
The algorithm is an algorithm in the sense of , one for all sentences. For each sentence there are the radius , the depth , the degree and the constant of the time bound. The input is the triple of G, a script of the construction sequence and φ, with the encodings of . The construction sequence is the run of the script, see , so λ is the length of the run. K is the width of .
The time bound λ · n² · poly_φ(K) is spelled out as . 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 φ.
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments