AFTD Auto-Formalizing Theoretical Domains

dfa_prod_reset_threshold_bounds

theoremverifiedformalization

For any two deterministic finite automata A₁ and A₂ over the same alphabet, the reset threshold of their direct product satisfies max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) ≤ dfa_reset_threshold (dfa_prod A₁ A₂) and dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂.

Statement

theorem dfa_prod_reset_threshold_bounds {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) ≤ dfa_reset_threshold (dfa_prod A₁ A₂) ∧ dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂
Formalizes
arXiv:2611.09136 Proposition 3.4
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • dfa_prod_is_synchronizing_iffA word w is synchronizing for the direct product dfa_prod A₁ A₂ of two deterministic finite automata if and only if w is…
  • dfa_prod_is_synchronizing_appendIf w₁ is a synchronizing word for A₁ and w₂ is a synchronizing word for A₂, then the concatenated word w₁ ++ w₂ is a…
  • 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 3

Read back from the Lean

For any types α, σ₁, and σ₂, and any deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂, the reset threshold (the length of the shortest synchronizing word in WithTop ℕ, or ⊤ if none exists) of the product automaton dfa_prod A₁ A₂ satisfies: 1. It is greater than or equal to the maximum of the reset threshold of A₁ and the reset threshold of A₂, and 2. It is less than or equal to 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.

The proof, explained

The proof establishes the lower and upper bounds on the reset threshold of a direct product automaton separately. For the lower bound, any word synchronizing A₁ × A₂ must synchronize each factor, so the set of synchronizing word lengths for the product is a subset of that for each factor, which implies the infimum threshold of the product is at least the maximum of the individual thresholds. For the upper bound, when both automata are synchronizable, concatenating minimal-length synchronizing words w₁ for A₁ and w₂ for A₂ yields a synchronizing word for A₁ × A₂ of length |w₁| + |w₂| = rt(A₁) + rt(A₂); if either automaton is not synchronizable, its threshold is +∞, making the sum +∞ and the upper bound trivial.

  1. The lower bound max(rt(A₁), rt(A₂)) ≤ rt(A₁ × A₂) reduces to showing rt(A₁) ≤ rt(A₁ × A₂) and rt(A₂) ≤ rt(A₁ × A₂).

    Splitting the main conjunction with `constructor` separates the lower bound from the upper bound. Rewriting with `max_le_iff` and unfolding the definition of reset threshold reduces the lower bound to two independent subgoals: showing that the infimum of synchronizing word lengths for each factor automaton is at most that of the direct product.

    lines 3–6

    uses max_le_iff

      constructor
      · rw [max_le_iff]
        dsimp [dfa_reset_threshold]
        constructor
  2. rt(A₁) ≤ rt(A₁ × A₂)

    By antimonotonicity of infima (`sInf_le_sInf`), an inclusion of sets S ⊆ T implies sInf T ≤ sInf S. Any word w that synchronizes A₁ × A₂ also synchronizes A₁ by `dfa_prod_is_synchronizing_iff`, so its length belongs to the set of synchronizing lengths for A₁. Hence the set of lengths for the product is a subset of that for A₁, giving the inequality.

    lines 7–9

    uses sInf_le_sInf, dfa_prod_is_synchronizing_iff

        · apply sInf_le_sInf
          rintro - ⟨w, hw, rfl⟩
          exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw |>.1, rfl⟩
  3. rt(A₂) ≤ rt(A₁ × A₂)

    Symmetrically, any word synchronizing A₁ × A₂ synchronizes A₂ by `dfa_prod_is_synchronizing_iff`. By `sInf_le_sInf`, the infimum of synchronizing word lengths for A₂ is at most that of the product.

    lines 10–12

    uses sInf_le_sInf, dfa_prod_is_synchronizing_iff

        · apply sInf_le_sInf
          rintro - ⟨w, hw, rfl⟩
          exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw |>.2, rfl⟩
  4. The upper bound proof splits into cases depending on whether A₁ and A₂ have synchronizing words.

    We perform case analysis (`by_cases`) on whether the sets of synchronizing word lengths for A₁ and A₂ are nonempty.

    lines 13–14

      · by_cases h₁ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₁ w}).Nonempty
        · by_cases h₂ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₂ w}).Nonempty
  5. When both A₁ and A₂ have synchronizing words, rt(A₁ × A₂) ≤ rt(A₁) + rt(A₂).

    Because the sets of synchronizing lengths are nonempty subsets of ℕ ∪ {∞}, their infima are attained by elements of the sets (`csInf_mem`), giving words w₁ and w₂ that synchronize A₁ and A₂ with lengths rt(A₁) and rt(A₂). By `dfa_prod_is_synchronizing_append`, their concatenation w₁ ++ w₂ synchronizes A₁ × A₂. Its length is |w₁| + |w₂| = rt(A₁) + rt(A₂) by `List.length_append` and `Nat.cast_add`. Since sInf is bounded above by any element of the set (`sInf_le`), the upper bound follows.

    lines 15–24

    uses csInf_mem, dfa_prod_is_synchronizing_append, Nat.cast_add, List.length_append, sInf_le

          · obtain ⟨w₁, hw₁, heq₁⟩ := csInf_mem h₁
            obtain ⟨w₂, hw₂, heq₂⟩ := csInf_mem h₂
            have hsync : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂) :=
              dfa_prod_is_synchronizing_append A₁ A₂ w₁ w₂ hw₁ hw₂
            dsimp [dfa_reset_threshold]
            dsimp [dfa_reset_threshold] at heq₁ heq₂
            rw [← heq₁, ← heq₂]
            rw [← Nat.cast_add, ← List.length_append]
            apply sInf_le
            exact ⟨w₁ ++ w₂, hsync, rfl⟩
  6. When A₂ has no synchronizing word, rt(A₁ × A₂) ≤ rt(A₁) + rt(A₂).

    If A₂ has no synchronizing word, its set of synchronizing word lengths is empty (`Set.not_nonempty_iff_eq_empty`), so rt(A₂) = sInf ∅ = ⊤ (`WithTop.sInf_empty`). Since rt(A₁) + ⊤ = ⊤ (`WithTop.add_top`), the inequality rt(A₁ × A₂) ≤ ⊤ holds trivially by `le_top`.

    lines 25–28

    uses Set.not_nonempty_iff_eq_empty, WithTop.sInf_empty, WithTop.add_top, le_top

          · rw [Set.not_nonempty_iff_eq_empty] at h₂
            dsimp [dfa_reset_threshold]
            rw [h₂, WithTop.sInf_empty, WithTop.add_top]
            exact le_top
  7. When A₁ has no synchronizing word, rt(A₁ × A₂) ≤ rt(A₁) + rt(A₂).

    Similarly, if A₁ has no synchronizing word, its set of synchronizing lengths is empty (`Set.not_nonempty_iff_eq_empty`), giving rt(A₁) = ⊤ (`WithTop.sInf_empty`). Then ⊤ + rt(A₂) = ⊤ (`WithTop.top_add`), and the inequality holds by `le_top`.

    lines 29–32

    uses Set.not_nonempty_iff_eq_empty, WithTop.sInf_empty, WithTop.top_add, le_top

        · rw [Set.not_nonempty_iff_eq_empty] at h₁
          dsimp [dfa_reset_threshold]
          rw [h₁, WithTop.sInf_empty, WithTop.top_add]
          exact le_top
max_le_iff
The maximum of two elements is at most c if and only if each element is at most c: max a b ≤ c ↔ a ≤ c ∧ b ≤ c.
sInf_le_sInf
If s ⊆ t, then sInf t ≤ sInf s (antimonotonicity of infima).
dfa_prod_is_synchronizing_iff
A word w synchronizes the product automaton A₁ × A₂ if and only if it synchronizes both A₁ and A₂.
csInf_mem
In a well-founded conditionally complete linear order, every nonempty set contains its infimum.
dfa_prod_is_synchronizing_append
If w₁ synchronizes A₁ and w₂ synchronizes A₂, then the concatenated word w₁ ++ w₂ synchronizes the product automaton A₁ × A₂.
Nat.cast_add
The cast from ℕ to an additive monoid with 1 preserves addition: ↑(m + n) = ↑m + ↑n.
List.length_append
The length of the concatenation of two lists is the sum of their lengths: (as ++ bs).length = as.length + bs.length.
sInf_le
An element belonging to a set is an upper bound for the set's infimum: a ∈ s → sInf s ≤ a.
Set.not_nonempty_iff_eq_empty
A set is not nonempty if and only if it is empty: ¬s.Nonempty ↔ s = ∅.
WithTop.sInf_empty
In a type with a top element ⊤, the infimum of the empty set is ⊤.
WithTop.add_top
Adding ⊤ on the right in WithTop yields ⊤: x + ⊤ = ⊤.
WithTop.top_add
Adding ⊤ on the left in WithTop yields ⊤: ⊤ + x = ⊤.
le_top
Every element is less than or equal to the top element: a ≤ ⊤.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Reset threshold bounds for direct products of DFAs: max(rt(A₁), rt(A₂)) ≤ rt(A₁ × A₂) ≤ rt(A₁) + rt(A₂). -/theorem dfa_prod_reset_threshold_bounds {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) ≤ dfa_reset_threshold (dfa_prod A₁ A₂) ∧ dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂ := by  constructor  · rw [max_le_iff]    dsimp [dfa_reset_threshold]    constructor    · apply sInf_le_sInf      rintro - ⟨w, hw, rfl⟩      exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw |>.1, rfl⟩    · apply sInf_le_sInf      rintro - ⟨w, hw, rfl⟩      exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw |>.2, rfl⟩  · by_cases h₁ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₁ w}).Nonempty    · by_cases h₂ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₂ w}).Nonempty      · obtain ⟨w₁, hw₁, heq₁⟩ := csInf_mem h₁        obtain ⟨w₂, hw₂, heq₂⟩ := csInf_mem h₂        have hsync : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂) :=          dfa_prod_is_synchronizing_append A₁ A₂ w₁ w₂ hw₁ hw₂        dsimp [dfa_reset_threshold]        dsimp [dfa_reset_threshold] at heq₁ heq₂        rw [← heq₁, ← heq₂]        rw [← Nat.cast_add, ← List.length_append]        apply sInf_le        exact ⟨w₁ ++ w₂, hsync, rfl⟩      · rw [Set.not_nonempty_iff_eq_empty] at h₂        dsimp [dfa_reset_threshold]        rw [h₂, WithTop.sInf_empty, WithTop.add_top]        exact le_top    · rw [Set.not_nonempty_iff_eq_empty] at h₁      dsimp [dfa_reset_threshold]      rw [h₁, WithTop.sInf_empty, WithTop.top_add]      exact le_top
See it in the graphDiscuss this resultChallenge it