dfa_is_seq_subset_sync_choice
Given an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, a family of deterministic finite automata A : (i : Fin k) → DFA α (σ i), and a sequence of words ws : Fin k → List α, ws is a sequential subset synchronization choice if for every index i : Fin k, ws i is a shortest word subset-synchronizing the set Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten)), with length in WithTop ℕ equal to the subset reset threshold of that set in A i.
Statement
def dfa_is_seq_subset_sync_choice {α : Type*} {k : ℕ} {σ : Fin k → Type*} (A : (i : Fin k) → DFA α (σ i)) (ws : Fin k → List α) : Prop
- Defined in
- arXiv:2611.09136
- Verified
- 15 Nov 2026
- Axioms
- none listed
- Built on 2
- dfa_subset_reset_thresholdThe subset reset threshold
dfa_subset_reset_threshold A Sof a subsetSof states of a DFAAis the infimum inWithTop ℕof the… - dfa_is_subset_synchronizingA word
w : List αis subset-synchronizing for a subsetS : Set σof states of a deterministic finite automatonA : DFA α σif…
- dfa_subset_reset_thresholdThe subset reset threshold
- Used by 3
- dfa_seq_subset_sync_total_le_k_mul_simultaneousFor any family of k deterministic finite automata A and any sequential subset synchronization choice ws, the total length ∑ i, (ws…
- op_1716_two_automata_subset_sync_le_two_optFor any two deterministic finite automata A (k = 2) and any two-stage sequential subset synchronization choice ws, the total length (ws…
- dfa_seq_subset_sync_stage_le_simultaneousFor any family of k deterministic finite automata A, any sequential subset synchronization choice ws, and any simultaneously synchronizing…
Read back from the Lean
For a type α, a natural number k, a family of state types σ : Fin k → Type*, a family of DFAs A : (i : Fin k) → DFA α (σ i), and a family of words ws : Fin k → List α, dfa_is_seq_subset_sync_choice A ws asserts that for every index i : Fin k:
1. The word ws i is subset-synchronizing for S_i in automaton A i, where S_i is the range of states reachable in A i starting from any state q : σ i after reading the concatenation of the first i words ws 0, ws 1, ..., ws (i - 1) (that is, ((List.ofFn ws).take i.val).flatten).
2. The length of ws i (cast to WithTop ℕ) is equal to the subset reset threshold dfa_subset_reset_threshold (A i) S_i, which is the infimum in WithTop ℕ of the lengths of all words that subset-synchronize S_i in A i (i.e., ws i is a shortest word subset-synchronizing S_i in A i).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A sequence of words forms a sequential subset synchronization choice if each word is a shortest word subset-synchronizing the current state image of the corresponding automaton. -/ def dfa_is_seq_subset_sync_choice {α : Type*} {k : ℕ} {σ : Fin k → Type*} (A : (i : Fin k) → DFA α (σ i)) (ws : Fin k → List α) : Prop := ∀ i : Fin k, let S_i := Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten)) dfa_is_subset_synchronizing (A i) S_i (ws i) ∧ ((ws i).length : WithTop ℕ) = dfa_subset_reset_threshold (A i) S_i