AFTD Auto-Formalizing Theoretical Domains

dfa_simultaneous_reset_threshold

def

Given an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, and a family of deterministic finite automata A : (i : Fin k) → DFA α (σ i), the simultaneous reset threshold of A is the infimum in WithTop ℕ of the lengths of all words w : List α that simultaneously synchronize every automaton A i in the family (evaluating to ⊤ if no such word exists).

Statement

noncomputable def dfa_simultaneous_reset_threshold {α : Type*} {k : ℕ} {σ : Fin k → Type*}
    (A : (i : Fin k) → DFA α (σ i)) : WithTop ℕ
Defined in
arXiv:2611.09136
Verified
15 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…

Read back from the Lean

Given an alphabet α, a natural number k, a family of state types σ : Fin k → Type*, and a family of deterministic finite automata A : (i : Fin k) → DFA α (σ i), dfa_simultaneous_reset_threshold A is the infimum in WithTop ℕ of the lengths of all words w : List α that are synchronizing for every automaton A i (for all i : Fin k). If no such word exists, it 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 simultaneous reset threshold of a family of deterministic finite automata with heterogeneous state spaces is the infimum in WithTop ℕ of the lengths of simultaneously synchronizing words. -/
noncomputable def dfa_simultaneous_reset_threshold {α : Type*} {k : ℕ} {σ : Fin k → Type*}
    (A : (i : Fin k) → DFA α (σ i)) : WithTop ℕ := sInf ((fun w : List α => (w.length : WithTop ℕ)) '' { w | ∀ i : Fin k, dfa_is_synchronizing (A i) w })
See it in the graphDiscuss this resultChallenge it