dfa_is_synchronizing
def
A word w : List α is synchronizing for a deterministic finite automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for all states q₁ q₂ : σ.
Statement
def dfa_is_synchronizing {α σ : Type*} (A : DFA α σ) (w : List α) : Prop
- Defined in
- arXiv:2611.09136 Section 2
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Used by 23
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
A₁andA₂over a common alphabet, the direct product attains the lower bound… - dfa_is_synchronizableA deterministic finite automaton
A : DFA α σis synchronizable if there exists a synchronizing wordw : List αforA. - dfa_prod_is_synchronizing_iffA word
wis synchronizing for the direct productdfa_prod A₁ A₂of two deterministic finite automata if and only ifwis… - 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_prod_attains_lower_bound_of_subsingletonProposition 3.13 of arXiv:2611.09136: For any two DFAs
A₁andA₂over a subsingleton (unary) alphabet, their direct product always… - dfa_simultaneous_reset_thresholdGiven an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, and a family of deterministic finite automata A :…
- op_1293_intermediate_reset_thresholdOpen Problem OP-1293 (arXiv:2611.09136 Sec. 7, open question 2): For every finite alphabet α with at least two symbols, any positive…
- dfa_prod_is_synchronizing_appendIf
w₁is a synchronizing word forA₁andw₂is a synchronizing word forA₂, then the concatenated wordw₁ ++ w₂is a… - dfa_reset_thresholdThe reset threshold
dfa_reset_threshold Aof a deterministic finite automatonA : DFA α σis the infimum inWithTop ℕof the lengths… - 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_is_synchronizable_subsingletonEvery deterministic finite automaton whose state type is a subsingleton is synchronizable.
- dfa_is_simultaneously_synchronizingGiven an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, and a family of deterministic finite automata A :…
- op_1293_product_reset_threshold_lower_bound_attainedFor every nonempty finite alphabet α and positive integers k₁, k₂, there exist finite state types σ₁, σ₂ and synchronizable DFAs A₁ : DFA…
- op_1670_opposite_cerny_product_two_three_is_synchronizingThe binary word [false, true, true, false] synchronizes the direct product dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3) of the 2-state Černý…
- 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… - op_1293_product_reset_threshold_upper_bound_attainedFor every finite alphabet α with at least two symbols and positive integers k₁, k₂, there exist finite state types σ₁, σ₂ and…
- op_1670_opposite_cerny_product_reset_threshold_two_threeThe reset threshold of the direct product dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3) of the 2-state Černý automaton and the 3-state…
- dfa_prod_reset_threshold_boundsFor any two deterministic finite automata
A₁andA₂over the same alphabet, the reset threshold of their direct product satisfies… - op_1667_opposite_cerny_product_two_is_synchronizingThe binary word [false, true] of length 2 synchronizes the direct product of the 2-state Černý automaton C_2 and its letter-swapped copy…
- dfa_is_synchronizing_subsingletonEvery word is synchronizing for a deterministic finite automaton whose state type is a subsingleton.
- op_1667_opposite_cerny_product_reset_threshold_twoThe reset threshold of the direct product of the 2-state Černý automaton C_2 and its letter-swapped copy C_2^swap is 2.
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
Read back from the Lean
For an alphabet type α, a state type σ, a deterministic finite automaton A : DFA α σ, and a word w : List α, dfa_is_synchronizing A w asserts that for all states q₁, q₂ : σ, evaluating A on word w starting from q₁ results in the same state as evaluating A on word 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 w is synchronizing for a DFA A if it maps all states to the same state. -/ def dfa_is_synchronizing {α σ : Type*} (A : DFA α σ) (w : List α) : Prop := ∀ q₁ q₂ : σ, A.evalFrom q₁ w = A.evalFrom q₂ w