Exact finite profile search with variable parameters and dominance pruning
DefinitionSensitivityVariableFrontierFix a valid graph and labeling datum, a state count , and a depth . Enumerate the finite recipe alphabet and retain only valid recipes. Starting from the normalized upper-triangular all-ones profile, expand each retained profile by every allowed letter. At each depth, discard a profile when another retained profile is componentwise no larger in both matrices.
The Boolean success test checks whether any retained profile of height , clamped below by two, satisfies
where is the datum's vertex count. All parameters come from the supplied datum. The definitions reuse generic finite-list pruning and enumeration from the earlier search module; they impose none of that module's fixed numerical parameters.
The search terminates for every fixed input and depth. Its correspondence with arbitrary admissible words is a separate theorem. No success, global search bound, or practical runtime bound is asserted.
import Definitions.Def_SensitivityVariableFinite
import Definitions.Def_SensitivityWordFrontier
/-!
Finite exact search at arbitrary certified graph parameters.
The imported fixed-parameter module supplies only the generic finite-list
dominance-pruning and finite-function enumeration definitions.
-/
set_option autoImplicit false
namespace SensitivityVariableFrontier
open SensitivityProfileCycle SensitivityProfileSearch SensitivityVariableWord
open SensitivityVariableFinite
abbrev Below {n : ℕ} := @SensitivityWordFrontier.Below n
abbrev maps := SensitivityWordFrontier.maps
def allLetters (q n : ℕ) : List (Letter q n) :=
(maps n n).flatMap fun t =>
(maps n n).flatMap fun g =>
(maps n 3).flatMap fun a =>
(maps n q).map fun v => Letter.mk t g a v
def alphabet (q n : ℕ) : List (Letter q n) :=
(allLetters q n).filter (fun C => C.recipe.Valid)
def expand {n : ℕ} (G : GraphData) (s : List (Profile n)) : List (Profile n) :=
s.flatMap fun P => (alphabet G.toleranceCount n).map fun C =>
SensitivityVariableWord.step G C.recipe P
def frontier (G : GraphData) (n : ℕ) : ℕ → List (Profile n)
| 0 => [SensitivityProfileSearch.normalize (unitProfile n)]
| k+1 => FiniteDominance.prune Below (expand G (frontier G n k))
def succeeds (G : GraphData) (n k : ℕ) : Bool :=
(frontier G n k).any fun P => decide (height P ^ 43 < G.vertices ^ (20*k))
end SensitivityVariableFrontier