AFTD Auto-Formalizing Theoretical Domains

dfa_seq_subset_sync_total_le_k_mul_simultaneous

theoremverifiedformalization

For any family of k deterministic finite automata A and any sequential subset synchronization choice ws, the total length ∑ i, (ws i).length is at most k times the length of any simultaneously synchronizing word w_opt.

Statement

theorem dfa_seq_subset_sync_total_le_k_mul_simultaneous {α : Type*} {k : ℕ} {σ : Fin k → Type*}
    (A : (i : Fin k) → DFA α (σ i)) (ws : Fin k → List α)
    (h_choice : dfa_is_seq_subset_sync_choice A ws)
    (w_opt : List α) (h_opt : dfa_is_simultaneously_synchronizing A w_opt) :
    (∑ i : Fin k, (ws i).length) ≤ k * w_opt.length
Formalizes
arXiv:2611.09136
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • dfa_is_simultaneously_synchronizingGiven an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, and a family of deterministic finite automata A :…
  • dfa_is_seq_subset_sync_choiceGiven an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, a family of deterministic finite automata A : (i…
  • 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…
  • dfa_is_subset_synchronizingA word w : List α is subset-synchronizing for a subset S : Set σ of states of a deterministic finite automaton A : DFA α σ if…
  • dfa_subset_reset_thresholdThe subset reset threshold dfa_subset_reset_threshold A S of a subset S of states of a DFA A is the infimum in WithTop ℕ of the…
Used by 1

Read back from the Lean

Given an alphabet type α, a natural number k, and state space types σ i for each i : Fin k: For a collection of DFAs A i : DFA α (σ i) and a sequence of words ws i : List α for i : Fin k, suppose that ws is chosen greedily by sequential subset synchronization: for each i : Fin k, letting S_i be the set of states in σ i reachable from any state via the concatenation of the preceding words ws 0, ..., ws (i - 1), the word ws i synchronizes S_i (maps all states in S_i to a single state) and has minimal length among all words that synchronize S_i for A i. Suppose also that w_opt : List α is a simultaneously synchronizing word for the family A (for every i : Fin k, w_opt maps all states of A i to a single state). Then the sum of the lengths of the words ws i over all i : Fin k is less than or equal to k * w_opt.length.

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

To bound the total length of the sequentially chosen words, the proof shows that each individual word ws i is at most as long as any simultaneously synchronizing word w_opt, and then sums this bound across all k automata. For each automaton A i, because w_opt synchronizes the entire automaton, it also synchronizes the subset S_i of states reachable after applying the previous words. Since ws i is chosen to attain the subset reset threshold (the minimum length of any word synchronizing S_i), its length cannot exceed that of w_opt; summing over all k automata completes the proof.

  1. For each index i, the simultaneously synchronizing word w_opt synchronizes the state subset S_i reachable after applying the previous words.

    Fix an automaton index i. By assumption, w_opt simultaneously synchronizes all automata, so it synchronizes the entire state space of A i. In particular, it synchronizes any subset of states of A i, including the subset S_i formed by the states reachable after applying the concatenation of the words chosen for previous automata ws 0, ..., ws (i - 1).

    lines 7–13

      have h_le : ∀ i : Fin k, (ws i).length ≤ w_opt.length := by
        intro i
        have h_opt_i : dfa_is_synchronizing (A i) w_opt := h_opt i
        have h_sub : dfa_is_subset_synchronizing (A i)
          (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) w_opt := by
          intro q₁ _ q₂ _
          exact h_opt_i q₁ q₂
  2. The subset reset threshold of S_i in A i is at most the length of w_opt (in ℕ ∪ {∞}).

    Because w_opt synchronizes S_i, its length belongs to the set of lengths of all words synchronizing S_i (by Set.mem_image_of_mem). The subset reset threshold is defined as the infimum (sInf) of this set of lengths, so by sInf_le, the threshold is bounded above by the length of w_opt.

    lines 14–23

    uses Set.mem_image_of_mem, sInf_le

        have h_len_eq := (h_choice i).2
        have h_mem : (w_opt.length : WithTop ℕ) ∈ (fun w : List α => (w.length : WithTop ℕ)) ''
          { w | dfa_is_subset_synchronizing (A i)
            (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) w } := by
          exact Set.mem_image_of_mem _ h_sub
        have h_inf_le : dfa_subset_reset_threshold (A i)
          (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) ≤
          (w_opt.length : WithTop ℕ) := by
          unfold dfa_subset_reset_threshold
          exact sInf_le h_mem
  3. For each index i, the length of ws i is at most the length of w_opt as natural numbers.

    By the definition of a sequential subset synchronization choice (h_choice), the length of ws i is equal to the subset reset threshold of S_i. Substituting this equality into the previous bound yields (ws i).length ≤ w_opt.length in WithTop ℕ, which unwraps to an inequality in ℕ via WithTop.coe_le_coe.mp.

    lines 24–27

    uses WithTop.coe_le_coe.mp

        have h_top : ((ws i).length : WithTop ℕ) ≤ (w_opt.length : WithTop ℕ) := by
          rw [h_len_eq]
          exact h_inf_le
        exact WithTop.coe_le_coe.mp h_top
  4. The total length ∑ i, (ws i).length is at most k * w_opt.length.

    Using Finset.sum_le_sum, we sum the inequality (ws i).length ≤ w_opt.length over all k indices in Fin k. The right-hand side is a sum of k identical terms of value w_opt.length, which simplifies to k * w_opt.length.

    lines 28–30

    uses Finset.sum_le_sum

      calc (∑ i : Fin k, (ws i).length)
        _ ≤ ∑ i : Fin k, w_opt.length := Finset.sum_le_sum (fun i _ => h_le i)
        _ = k * w_opt.length := by simp
Set.mem_image_of_mem
If an element belongs to a set, its image under a function belongs to the image of that set.
sInf_le
The infimum of a set is at most any element in that set.
WithTop.coe_le_coe.mp
An inequality between natural numbers coerced to WithTop ℕ implies the corresponding inequality between the natural numbers themselves.
Finset.sum_le_sum
If one function is pointwise less than or equal to another on a finite set, the sum of the first function over that set is at most the sum of the second.

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

/-- The total length of words in any sequential subset synchronization choice for k automata is at most k times the length of any simultaneously synchronizing word. -/theorem dfa_seq_subset_sync_total_le_k_mul_simultaneous {α : Type*} {k : ℕ} {σ : Fin k → Type*}    (A : (i : Fin k) → DFA α (σ i)) (ws : Fin k → List α)    (h_choice : dfa_is_seq_subset_sync_choice A ws)    (w_opt : List α) (h_opt : dfa_is_simultaneously_synchronizing A w_opt) :    (∑ i : Fin k, (ws i).length) ≤ k * w_opt.length := by  have h_le : ∀ i : Fin k, (ws i).length ≤ w_opt.length := by    intro i    have h_opt_i : dfa_is_synchronizing (A i) w_opt := h_opt i    have h_sub : dfa_is_subset_synchronizing (A i)      (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) w_opt := by      intro q₁ _ q₂ _      exact h_opt_i q₁ q₂    have h_len_eq := (h_choice i).2    have h_mem : (w_opt.length : WithTop ℕ) ∈ (fun w : List α => (w.length : WithTop ℕ)) ''      { w | dfa_is_subset_synchronizing (A i)        (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) w } := by      exact Set.mem_image_of_mem _ h_sub    have h_inf_le : dfa_subset_reset_threshold (A i)      (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) ≤      (w_opt.length : WithTop ℕ) := by      unfold dfa_subset_reset_threshold      exact sInf_le h_mem    have h_top : ((ws i).length : WithTop ℕ) ≤ (w_opt.length : WithTop ℕ) := by      rw [h_len_eq]      exact h_inf_le    exact WithTop.coe_le_coe.mp h_top  calc (∑ i : Fin k, (ws i).length)    _ ≤ ∑ i : Fin k, w_opt.length := Finset.sum_le_sum (fun i _ => h_le i)    _ = k * w_opt.length := by simp
See it in the graphDiscuss this resultChallenge it