dfa_is_subset_synchronizing
def
A word w : List α is subset-synchronizing for a subset S : Set σ of states of a deterministic finite automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for all q₁ q₂ ∈ S.
Statement
def dfa_is_subset_synchronizing {α σ : Type*} (A : DFA α σ) (S : Set σ) (w : List α) : Prop
- Defined in
- arXiv:2611.09136 Sec. 7
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Used by 8
- dfa_prod_subset_sync_two_stage_boundFor any synchronizing word
w₁ofA₁, the reset threshold of the direct productdfa_prod A₁ A₂is at most the length ofw₁plus the… - dfa_is_seq_subset_sync_choiceGiven an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, a family of deterministic finite automata A : (i…
- dfa_subset_reset_thresholdThe subset reset threshold
dfa_subset_reset_threshold A Sof a subsetSof states of a DFAAis the infimum inWithTop ℕof the… - op_1292_optimality_of_two_stage_subset_sync_falseOpen Problem OP-1292 does not hold: it is not the case that for every pair of synchronizable DFAs
A₁andA₂over a shared finite… - 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…
- dfa_stage_has_unique_shortest_choiceGiven an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, a family of deterministic finite automata A : (i…
- 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…
- dfa_prod_is_synchronizing_of_subset_synchronizingIf
w₁is a synchronizing word forA₁, andvis a subset-synchronizing word for the image set ofw₁onA₂, then the concatenated…
- dfa_prod_subset_sync_two_stage_boundFor any synchronizing word
Read back from the Lean
Given types α and σ, a DFA A with alphabet α and state type σ, a subset of states S : Set σ, and a word w : List α, dfa_is_subset_synchronizing A S w defines the proposition that for all states q₁ ∈ S and q₂ ∈ S, the state reached by running A on input w starting from q₁ is equal to the state reached by running A on w starting from q₂.
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 word synchronizes a subset of states in a DFA if it maps all states in the subset to a common state. -/ def dfa_is_subset_synchronizing {α σ : Type*} (A : DFA α σ) (S : Set σ) (w : List α) : Prop := ∀ q₁ ∈ S, ∀ q₂ ∈ S, A.evalFrom q₁ w = A.evalFrom q₂ w