dfa_reset_threshold
def
The reset threshold dfa_reset_threshold A of a deterministic finite automaton A : DFA α σ is the infimum in WithTop ℕ of the lengths of all synchronizing words for A.
Statement
noncomputable def dfa_reset_threshold {α σ : Type*} (A : DFA α σ) : WithTop ℕ
- Defined in
- arXiv:2611.09136 Section 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 13
- 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_prod_attains_upper_boundA pair of DFAs
A₁andA₂over the same alphabet attains the upper bound of Proposition 3.4 if the reset threshold of their direct… - 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… - 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… - 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_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…
- 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₁ :…
- 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_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.
- dfa_prod_attains_lower_boundA pair of DFAs
A₁andA₂over the same alphabet attains the lower bound of Proposition 3.4 if the reset threshold of their direct…
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
Read back from the Lean
A definition assigning to each DFA A (with input alphabet α and state type σ) a value in WithTop ℕ (natural numbers with infinity), defined as the infimum of the lengths of all words w : List α that are synchronizing for A. If no synchronizing word exists, the value is ⊤ (infinity); if synchronizing words exist, it is the minimum length of such a word.
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
/-- The reset threshold of a DFA is the infimum in WithTop ℕ of the lengths of all synchronizing words. -/ noncomputable def dfa_reset_threshold {α σ : Type*} (A : DFA α σ) : WithTop ℕ := sInf ((fun w : List α => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing A w })