dfa_is_synchronizable
def
A deterministic finite automaton A : DFA α σ is synchronizable if there exists a synchronizing word w : List α for A.
Statement
def dfa_is_synchronizable {α σ : Type*} (A : DFA α σ) : Prop
- Defined in
- arXiv:2611.09136 Sec. 2
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Built on 1
- dfa_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all…
- dfa_is_synchronizingA word
- Used by 7
- 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… - 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…
- 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_is_synchronizable_subsingletonEvery deterministic finite automaton whose state type is a subsingleton is synchronizable.
- 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_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_1293_intermediate_reset_threshold_k1_eq_one_k2_eq_oneFor every finite alphabet α with at least two symbols and k ∈ {1, 2}, there exist finite state types σ₁, σ₂ and synchronizable DFAs A₁ :…
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
Read back from the Lean
For types α and σ, and a deterministic finite automaton A : DFA α σ, dfa_is_synchronizable A asserts that there exists a word w : List α such that for all states q₁, q₂ : σ, evaluating A starting from q₁ on w results in the same state as evaluating A starting from q₂ on w (that is, A.evalFrom q₁ w = A.evalFrom q₂ w).
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 DFA is synchronizable if it admits a synchronizing word. -/ def dfa_is_synchronizable {α σ : Type*} (A : DFA α σ) : Prop := ∃ w : List α, dfa_is_synchronizing A w