AFTD Auto-Formalizing Theoretical Domains

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 automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for all…
Used by 13

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