Exact profile search with dominance pruning
DefinitionSensitivityWordFrontierFor a fixed state count , enumerate the valid letters of the finite alphabet. The initial frontier consists only of the normalized all-ones profile. At each depth, apply every valid letter to every retained profile, then prune by the componentwise order on both profile matrices.
An insertion is skipped if an existing profile is no larger in every entry. Otherwise insert the new profile and remove existing profiles it dominates. All comparisons take place at the same depth. Write for the resulting finite list after stages. The Boolean test is
The definitions use finite enumeration and exact natural-number arithmetic. They make no claim that a successful depth or state count exists and supply no bound on runtime, depth, or state count. Correctness and completeness are proved separately; in particular, dominance pruning never splices entries from different reachable profiles.
import Definitions.Def_SensitivityWordFinite
/-!
Exact finite profile search with componentwise dominance pruning.
No search success or numerical growth bound is assumed by these definitions.
-/
set_option autoImplicit false
namespace FiniteDominance
variable {α : Type} (R : α → α → Prop) [DecidableRel R]
def insert (x : α) (s : List α) : List α :=
if ∃ y ∈ s, R y x then s else x :: s.filter (fun y => ¬ R x y)
def prune : List α → List α
| [] => []
| x :: s => insert R x (prune s)
end FiniteDominance
namespace SensitivityWordFrontier
open SensitivityProfileCycle SensitivityProfileSearch SensitivityProfileWord
open SensitivityWordFinite
def Below {n : ℕ} (P Q : Profile n) : Prop :=
∀ i j, P.zero i j ≤ Q.zero i j ∧ P.one i j ≤ Q.one i j
instance {n : ℕ} : DecidableRel (@Below n) := fun P Q => by
unfold Below
infer_instance
def maps (n m : ℕ) : List (Fin n → Fin m) :=
(List.pi (List.finRange n) (fun _ => List.finRange m)).map
(fun f i => f i (List.mem_finRange i))
def allLetters (n : ℕ) : List (Letter n) :=
(maps n n).flatMap fun t =>
(maps n n).flatMap fun g =>
(maps n 3).flatMap fun a =>
(maps n 6).map fun q => Letter.mk t g a q
def alphabet (n : ℕ) : List (Letter n) :=
(allLetters n).filter (fun C => C.recipe.Valid)
def expand {n : ℕ} (s : List (Profile n)) : List (Profile n) :=
s.flatMap fun P => (alphabet n).map fun C => step C.recipe P
def frontier (n : ℕ) : ℕ → List (Profile n)
| 0 => [normalize (unitProfile n)]
| k+1 => FiniteDominance.prune Below (expand (frontier n k))
def succeeds (n k : ℕ) : Bool :=
(frontier n k).any fun P => decide (height P ^ 43 < 14055 ^ (20*k))
end SensitivityWordFrontier