AFTD Auto-Formalizing Theoretical Domains

dfa_prod_attains_lower_bound

def

A pair of DFAs A₁ and A₂ over the same alphabet attains the lower bound of Proposition 3.4 if the reset threshold of their direct product equals max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂).

Statement

def dfa_prod_attains_lower_bound {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : Prop
Defined in
arXiv:2611.09136 Sec. 7, open question 1
Verified
09 Nov 2026
Axioms
none listed
Built on 2
  • dfa_reset_thresholdThe reset threshold dfa_reset_threshold A of a deterministic finite automaton A : DFA α σ is the infimum in WithTop ℕ of the lengths…
  • dfa_prodThe direct product dfa_prod A₁ A₂ of two deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂ over alphabet α is the DFA…
Used by 2

Read back from the Lean

Given an alphabet type α, state types σ₁ and σ₂, and two deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂, dfa_prod_attains_lower_bound A₁ A₂ is defined as the proposition that the reset threshold of the synchronous product automaton dfa_prod A₁ A₂ is equal to the maximum (in WithTop ℕ) of the reset threshold of A₁ and the reset threshold of A₂, where the reset threshold of an automaton is the infimum in WithTop ℕ of the lengths of all words that synchronize the automaton.

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

/-- Predicate asserting that the reset threshold of `dfa_prod A₁ A₂` attains the lower bound `max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂)`. -/
def dfa_prod_attains_lower_bound {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : Prop := dfa_reset_threshold (dfa_prod A₁ A₂) = max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂)
See it in the graphDiscuss this resultChallenge it