AFTD Auto-Formalizing Theoretical Domains

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 subset S : Set σ of states of a deterministic finite automaton A : DFA α σ if…
Used by 6

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 })
See it in the graphDiscuss this resultChallenge it