dfa_prod_is_synchronizing_iff
A word w is synchronizing for the direct product dfa_prod A₁ A₂ of two deterministic finite automata if and only if w is synchronizing for both A₁ and A₂.
Statement
theorem dfa_prod_is_synchronizing_iff {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w : List α) : dfa_is_synchronizing (dfa_prod A₁ A₂) w ↔ dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w
- Formalizes
- arXiv:2611.09136 Lemma 3.1
- Verified
- 09 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 2
- 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_synchronizingA word
- Used by 5
- 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… - dfa_prod_is_synchronizing_appendIf
w₁is a synchronizing word forA₁andw₂is a synchronizing word forA₂, then the concatenated wordw₁ ++ w₂is a… - dfa_prod_is_synchronizing_of_subset_synchronizingIf
w₁is a synchronizing word forA₁, andvis a subset-synchronizing word for the image set ofw₁onA₂, then the concatenated… - dfa_prod_reset_threshold_boundsFor any two deterministic finite automata
A₁andA₂over the same alphabet, the reset threshold of their direct product satisfies…
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
Read back from the Lean
For any types α, σ₁, and σ₂, any deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂, and any word w : List α: w is a synchronizing word for the product automaton dfa_prod A₁ A₂ if and only if w is a synchronizing word for A₁ and w is a synchronizing word for 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 equivalence is established in two directions using an auxiliary lemma showing that evaluation in the direct product DFA decomposes componentwise as `(dfa_prod A₁ A₂).evalFrom (q₁, q₂) w = (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w)`. For the forward direction, if the product automaton is synchronized by `w`, instantiating the synchronization condition on product states differing only in one coordinate and projecting yields that each factor automaton is synchronized. For the backward direction, if each factor is synchronized by `w`, evaluating from any two product states produces identical first components and identical second components, so the product states coincide.
Evaluating a word on the direct product automaton acts componentwise on states: `(dfa_prod A₁ A₂).evalFrom (q₁, q₂) w = (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w)`.
We prove this componentwise evaluation identity by induction on the word `w`, generalized over all state pairs `(q₁, q₂)`. The base case `w = []` holds by definition (`rfl`), as processing the empty word leaves any state unchanged. For the inductive step `a :: w`, unfolding `DFA.evalFrom` and list folding via `List.foldl_cons` rewrites the execution as a single transition step followed by evaluating `w`. The claim then follows by applying the induction hypothesis to the updated states `(A₁.step q₁ a, A₂.step q₂ a)`.
uses
DFA.evalFrom,List.foldl_consinduction w generalizing q₁ q₂ with | nil => rfl | cons a w ih => simp only [DFA.evalFrom, List.foldl_cons] exact ih (A₁.step q₁ a) (A₂.step q₂ a)
If the direct product automaton is synchronized by `w`, then the first automaton `A₁` is synchronized by `w`.
We split the equivalence and assume that `w` synchronizes `dfa_prod A₁ A₂` (hypothesis `h`). To show that `A₁` is synchronized, let `q₁, q₂` be any two states of `A₁`. We instantiate hypothesis `h` on the product states `(q₁, A₂.start)` and `(q₂, A₂.start)`. Rewriting both sides with `dfa_prod_is_synchronizing_iff_evalFrom` gives `(A₁.evalFrom q₁ w, A₂.evalFrom A₂.start w) = (A₁.evalFrom q₂ w, A₂.evalFrom A₂.start w)`. Taking the first projection of both sides using `congrArg Prod.fst` yields `A₁.evalFrom q₁ w = A₁.evalFrom q₂ w`.
uses
dfa_prod_is_synchronizing_iff_evalFrom,congrArg,Prod.fstconstructor · intro h constructor · intro q₁ q₂ have hprod := h (q₁, A₂.start) (q₂, A₂.start) rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] at hprod exact congrArg Prod.fst hprod
If the direct product automaton is synchronized by `w`, then the second automaton `A₂` is synchronized by `w`.
To show that `A₂` is synchronized, let `q₁, q₂` be any two states of `A₂`. Symmetrically to the previous step, we instantiate the product synchronization hypothesis `h` on `(A₁.start, q₁)` and `(A₁.start, q₂)`. Rewriting with `dfa_prod_is_synchronizing_iff_evalFrom` and projecting onto the second coordinate using `congrArg Prod.snd` yields `A₂.evalFrom q₁ w = A₂.evalFrom q₂ w`.
uses
dfa_prod_is_synchronizing_iff_evalFrom,congrArg,Prod.snd· intro q₁ q₂ have hprod := h (A₁.start, q₁) (A₁.start, q₂) rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] at hprod exact congrArg Prod.snd hprod
If both `A₁` and `A₂` are synchronized by `w`, then the direct product automaton is synchronized by `w`.
For the backward direction, assume `w` synchronizes `A₁` (hypothesis `h₁`) and `w` synchronizes `A₂` (hypothesis `h₂`). Given any two product states `(q₁, q₂)` and `(r₁, r₂)`, rewriting both sides of the product evaluation with `dfa_prod_is_synchronizing_iff_evalFrom` reduces the goal to showing `(A₁.evalFrom q₁ w, A₂.evalFrom q₂ w) = (A₁.evalFrom r₁ w, A₂.evalFrom r₂ w)`. By `Prod.ext`, this holds because `h₁ q₁ r₁` equates the first components and `h₂ q₂ r₂` equates the second components.
uses
dfa_prod_is_synchronizing_iff_evalFrom,Prod.ext· rintro ⟨h₁, h₂⟩ ⟨q₁, q₂⟩ ⟨r₁, r₂⟩ rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] exact Prod.ext (h₁ q₁ r₁) (h₂ q₂ r₂)
DFA.evalFrom- Evaluates a DFA on an input word starting from a given initial state by repeatedly applying its transition function.
List.foldl_cons- Folding a function over a non-empty list `a :: l` with accumulator `b` equals folding over `l` with accumulator `f b a`.
dfa_prod_is_synchronizing_iff_evalFrom- Evaluating the direct product automaton on a word `w` from initial state `(q₁, q₂)` produces the pair of states `(A₁.evalFrom q₁ w, A₂.evalFrom q₂ w)`.
congrArg- Applying a function `f` to equal arguments produces equal results (`a₁ = a₂ → f a₁ = f a₂`).
Prod.fst- The first projection of an ordered pair, mapping `(x, y)` to `x`.
Prod.snd- The second projection of an ordered pair, mapping `(x, y)` to `y`.
Prod.ext- Two ordered pairs are equal if their first components are equal and their second components are equal.
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.
lemma dfa_prod_is_synchronizing_iff_evalFrom {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (q₁ : σ₁) (q₂ : σ₂) (w : List α) : (dfa_prod A₁ A₂).evalFrom (q₁, q₂) w = (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w) := by induction w generalizing q₁ q₂ with | nil => rfl | cons a w ih => simp only [DFA.evalFrom, List.foldl_cons] exact ih (A₁.step q₁ a) (A₂.step q₂ a)/-- A word synchronizes the direct product of two DFAs iff it synchronizes both DFAs. -/theorem dfa_prod_is_synchronizing_iff {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w : List α) : dfa_is_synchronizing (dfa_prod A₁ A₂) w ↔ dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w := by constructor · intro h constructor · intro q₁ q₂ have hprod := h (q₁, A₂.start) (q₂, A₂.start) rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] at hprod exact congrArg Prod.fst hprod · intro q₁ q₂ have hprod := h (A₁.start, q₁) (A₁.start, q₂) rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] at hprod exact congrArg Prod.snd hprod · rintro ⟨h₁, h₂⟩ ⟨q₁, q₂⟩ ⟨r₁, r₂⟩ rw [dfa_prod_is_synchronizing_iff_evalFrom, dfa_prod_is_synchronizing_iff_evalFrom] exact Prod.ext (h₁ q₁ r₁) (h₂ q₂ r₂)