dfa_prod_attains_lower_bound
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 Aof a deterministic finite automatonA : DFA α σis the infimum inWithTop ℕof the lengths… - dfa_prodThe direct product
dfa_prod A₁ A₂of two deterministic finite automataA₁ : DFA α σ₁andA₂ : DFA α σ₂over alphabetαis the DFA…
- dfa_reset_thresholdThe reset threshold
- Used by 2
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
A₁andA₂over a common alphabet, the direct product attains the lower bound… - dfa_prod_attains_lower_bound_of_subsingletonProposition 3.13 of arXiv:2611.09136: For any two DFAs
A₁andA₂over a subsingleton (unary) alphabet, their direct product always…
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
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₂)