dfa_subset_reset_threshold
def
The subset reset threshold dfa_subset_reset_threshold A S of a subset S of states of a DFA A is the infimum in WithTop ℕ of the lengths of all words that subset-synchronize S.
Statement
noncomputable def dfa_subset_reset_threshold {α σ : Type*} (A : DFA α σ) (S : Set σ) : WithTop ℕ
- Defined in
- arXiv:2611.09136 Sec. 7
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Built on 1
- dfa_is_subset_synchronizingA word
w : List αis subset-synchronizing for a subsetS : Set σof states of a deterministic finite automatonA : DFA α σif…
- dfa_is_subset_synchronizingA word
- Used by 6
- 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…
- 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_subset_sync_two_stage_boundFor any synchronizing word
Read back from the Lean
dfa_subset_reset_threshold defines a function taking types α and σ, a deterministic finite automaton A : DFA α σ, and a subset of states S : Set σ, returning an element of WithTop ℕ. The value is the infimum in WithTop ℕ of the lengths of all words w : List α that are subset-synchronizing for A on S (that is, words w satisfying dfa_is_subset_synchronizing A S w). If no such word exists, the set is empty and the infimum evaluates to ⊤.
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 subset reset threshold of a subset S in a DFA is the infimum of lengths of words that subset-synchronize S. -/ noncomputable def dfa_subset_reset_threshold {α σ : Type*} (A : DFA α σ) (S : Set σ) : WithTop ℕ := sInf ((fun w : List α => (w.length : WithTop ℕ)) '' { w | dfa_is_subset_synchronizing A S w })