dfa_prod_is_synchronizing_of_subset_synchronizing
If w₁ is a synchronizing word for A₁, and v is a subset-synchronizing word for the image set of w₁ on A₂, then the concatenated word w₁ ++ v is a synchronizing word for the direct product dfa_prod A₁ A₂.
Statement
theorem dfa_prod_is_synchronizing_of_subset_synchronizing {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w₁ v : List α) (hw₁ : dfa_is_synchronizing A₁ w₁) (hv : dfa_is_subset_synchronizing A₂ (Set.range (fun q : σ₂ => A₂.evalFrom q w₁)) v) : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ v)
- Formalizes
- arXiv:2611.09136 Sec. 7
- Verified
- 09 Nov 2026
- Axioms
Quot.soundpropext- Built on 4
- dfa_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all… - dfa_prodThe direct product
dfa_prod A₁ A₂of two deterministic finite automataA₁ : DFA α σ₁andA₂ : DFA α σ₂over alphabetαis the DFA… - dfa_is_subset_synchronizingA word
w : List αis subset-synchronizing for a subsetS : Set σof states of a deterministic finite automatonA : DFA α σif… - dfa_prod_is_synchronizing_iffA word
wis synchronizing for the direct productdfa_prod A₁ A₂of two deterministic finite automata if and only ifwis…
- dfa_is_synchronizingA word
- Used by 1
- dfa_prod_subset_sync_two_stage_boundFor any synchronizing word
w₁ofA₁, the reset threshold of the direct productdfa_prod A₁ A₂is at most the length ofw₁plus the…
- dfa_prod_subset_sync_two_stage_boundFor any synchronizing word
Read back from the Lean
For any alphabet type α and state types σ₁ and σ₂, let A₁ be a DFA over α with state type σ₁, let A₂ be a DFA over α with state type σ₂, and let w₁ and v be lists of symbols in α (words). If w₁ is a synchronizing word for A₁, and v is a subset-synchronizing word for A₂ on the subset of states consisting of the image (range) of σ₂ under evaluation of w₁ (i.e., { A₂.evalFrom q w₁ | q : σ₂ }), then the concatenated word w₁ ++ v is a synchronizing word for the product DFA dfa_prod A₁ 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
To prove that w₁ ++ v is synchronizing for the direct product A₁ × A₂, we consider two arbitrary states (q₁, q₂) and (r₁, r₂) and show component-wise that they reach the same destination. In the first component, reading w₁ immediately synchronizes q₁ and r₁ to the same state in A₁ because w₁ is synchronizing, so reading v keeps them identical. In the second component, reading w₁ maps both states into the image set of w₁, which is then brought to a single state in A₂ by v because v is subset-synchronizing for that image.
To show that w₁ ++ v synchronizes the product DFA, it suffices to show that for any two initial states (q₁, q₂) and (r₁, r₂), both component DFAs reach the same final state after reading w₁ ++ v.
A word synchronizes an automaton if it sends every pair of states to the same destination. We introduce two arbitrary states (q₁, q₂) and (r₁, r₂) of the product automaton (line 3). Since evaluation on a product DFA decomposes component-wise (by dfa_prod_is_synchronizing_iff_evalFrom on line 4), the state reached in the product DFA is the pair of states reached in A₁ and A₂. Using extensionality on pairs (ext on line 5), the goal splits into verifying equality for the first component and the second component separately.
uses
dfa_prod_is_synchronizing_iff_evalFromintro ⟨q₁, q₂⟩ ⟨r₁, r₂⟩ rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] ext
The first component automaton A₁ reaches the same state from q₁ and r₁: A₁.evalFrom q₁ (w₁ ++ v) = A₁.evalFrom r₁ (w₁ ++ v).
Simplifying the first projection (line 6) leaves the equality in A₁. By DFA.evalFrom_of_append, running the concatenated word w₁ ++ v is equivalent to running w₁ first and then running v from the resulting state. Since w₁ is synchronizing for A₁ (hw₁), the states reached after w₁ are identical (A₁.evalFrom q₁ w₁ = A₁.evalFrom r₁ w₁), so running v afterwards leaves them equal as well.
uses
DFA.evalFrom_of_append· dsimp rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append, hw₁ q₁ r₁]
The second component automaton A₂ reaches the same state from q₂ and r₂: A₂.evalFrom q₂ (w₁ ++ v) = A₂.evalFrom r₂ (w₁ ++ v).
Simplifying the second projection (line 8) isolates the execution in A₂. Rewriting with DFA.evalFrom_of_append (line 9) splits the word w₁ ++ v into w₁ followed by v. The intermediate states A₂.evalFrom q₂ w₁ and A₂.evalFrom r₂ w₁ both belong to the image set of w₁ on A₂ by Set.mem_range_self. Since v is subset-synchronizing for this image set (hv), running v from these two intermediate states yields the same final state, closing the goal (line 10).
uses
DFA.evalFrom_of_append,Set.mem_range_self· dsimp rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append] exact hv _ (Set.mem_range_self q₂) _ (Set.mem_range_self r₂)
dfa_prod_is_synchronizing_iff_evalFrom- Evaluating a word from a state pair in the direct product DFA equals the pair of states reached by evaluating the word in each component DFA independently.
DFA.evalFrom_of_append- Evaluating a concatenated word x ++ y from a starting state is equal to evaluating x from that start state, and then evaluating y from the resulting state.
Set.mem_range_self- For any function f and input i, the value f(i) belongs to the range of f.
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.
/-- Concatenating a synchronizing word for A₁ with a word that subset-synchronizes its image in A₂ yields a synchronizing word for the direct product. -/theorem dfa_prod_is_synchronizing_of_subset_synchronizing {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w₁ v : List α) (hw₁ : dfa_is_synchronizing A₁ w₁) (hv : dfa_is_subset_synchronizing A₂ (Set.range (fun q : σ₂ => A₂.evalFrom q w₁)) v) : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ v) := by intro ⟨q₁, q₂⟩ ⟨r₁, r₂⟩ rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] ext · dsimp rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append, hw₁ q₁ r₁] · dsimp rw [DFA.evalFrom_of_append, DFA.evalFrom_of_append] exact hv _ (Set.mem_range_self q₂) _ (Set.mem_range_self r₂)