op_1716_two_automata_subset_sync_le_two_opt
For any two deterministic finite automata A (k = 2) and any two-stage sequential subset synchronization choice ws, the total length (ws 0).length + (ws 1).length is at most 2 * w_opt.length for any simultaneously synchronizing word w_opt.
Statement
theorem op_1716_two_automata_subset_sync_le_two_opt {α : Type*} {σ : Fin 2 → Type*} (A : (i : Fin 2) → DFA α (σ i)) (ws : Fin 2 → List α) (h_choice : dfa_is_seq_subset_sync_choice A ws) (w_opt : List α) (h_opt : dfa_is_simultaneously_synchronizing A w_opt) : (ws 0).length + (ws 1).length ≤ 2 * w_opt.length
- Formalizes
- arXiv:2611.09136
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_seq_subset_sync_total_le_k_mul_simultaneousFor any family of k deterministic finite automata A and any sequential subset synchronization choice ws, the total length ∑ i, (ws…
Read back from the Lean
For any alphabet α, any family of two state types σ : Fin 2 → Type*, any pair of deterministic finite automata A : (i : Fin 2) → DFA α (σ i), and any pair of words ws : Fin 2 → List α:
Assume that ws is chosen by sequential subset-synchronization (dfa_is_seq_subset_sync_choice A ws), which means:
- For i = 0: with S_0 being the range of states reachable under the empty word in A 0 (i.e., all states of A 0), ws 0 subset-synchronizes S_0, and the length of ws 0 achieves the subset-reset threshold of S_0 in A 0 (the minimum length of any word subset-synchronizing S_0).
- For i = 1: with S_1 being the set of states reachable in A 1 from any state under word ws 0, ws 1 subset-synchronizes S_1, and the length of ws 1 achieves the subset-reset threshold of S_1 in A 1.
Assume also that w_opt : List α is a word that simultaneously synchronizes both automata A 0 and A 1 (for each i ∈ Fin 2, all pairs of states in σ i transition to the same state under w_opt).
Then the sum of the lengths of ws 0 and ws 1 is at most twice the length of w_opt, that is:
(ws 0).length + (ws 1).length ≤ 2 * 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
The theorem specializes the general bound dfa_seq_subset_sync_total_le_k_mul_simultaneous (which bounds the total length of a sequential subset synchronization choice for k automata by k times the length of any simultaneously synchronizing word) to k = 2. It then expands the summation over Fin 2 into the sum of the two individual word lengths using Fin.sum_univ_two.
The sum of the lengths of the two synchronizing words, ∑ i, (ws i).length, is at most 2 * w_opt.length.
Apply the general theorem dfa_seq_subset_sync_total_le_k_mul_simultaneous with k = 2 to the two automata A, the choice ws, and the simultaneously synchronizing word w_opt.
uses
dfa_seq_subset_sync_total_le_k_mul_simultaneoushave h := dfa_seq_subset_sync_total_le_k_mul_simultaneous A ws h_choice w_opt h_opt(ws 0).length + (ws 1).length ≤ 2 * w_opt.length
Expand the sum over Fin 2 into the sum of the two terms (ws 0).length + (ws 1).length using Fin.sum_univ_two, simplifying the inequality established in the previous step into the goal.
uses
Fin.sum_univ_twosimpa [Fin.sum_univ_two] using h
dfa_seq_subset_sync_total_le_k_mul_simultaneous- for any k deterministic finite automata and sequential subset synchronization choice ws, the sum of lengths ∑ i, (ws i).length is at most k times the length of any simultaneously synchronizing word
Fin.sum_univ_two- the sum of a function over the two-element index type Fin 2 is the sum of its values at 0 and 1: ∑ i, f i = f 0 + f 1
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- For two deterministic finite automata, the total length of a two-stage sequential subset synchronization choice is at most twice the length of any simultaneously synchronizing word. -/theorem op_1716_two_automata_subset_sync_le_two_opt {α : Type*} {σ : Fin 2 → Type*} (A : (i : Fin 2) → DFA α (σ i)) (ws : Fin 2 → List α) (h_choice : dfa_is_seq_subset_sync_choice A ws) (w_opt : List α) (h_opt : dfa_is_simultaneously_synchronizing A w_opt) : (ws 0).length + (ws 1).length ≤ 2 * w_opt.length := by have h := dfa_seq_subset_sync_total_le_k_mul_simultaneous A ws h_choice w_opt h_opt simpa [Fin.sum_univ_two] using h