AFTD Auto-Formalizing Theoretical Domains

dfa_prod_attains_upper_bound

def

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

Statement

def dfa_prod_attains_upper_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 1

Read back from the Lean

For types α, σ₁, σ₂ and two DFAs A₁ : DFA α σ₁ and A₂ : DFA α σ₂ over the alphabet α, dfa_prod_attains_upper_bound A₁ A₂ is defined as the proposition that the reset threshold (in WithTop ℕ) of the product automaton dfa_prod A₁ A₂ equals the sum of the reset threshold of A₁ and the reset threshold of A₂.

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 upper bound `dfa_reset_threshold A₁ + dfa_reset_threshold A₂`. -/
def dfa_prod_attains_upper_bound {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : Prop := dfa_reset_threshold (dfa_prod A₁ A₂) = dfa_reset_threshold A₁ + dfa_reset_threshold A₂
See it in the graphDiscuss this resultChallenge it