dfa_is_simultaneously_synchronizing
Given an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, and a family of deterministic finite automata A : (i : Fin k) → DFA α (σ i), a word w : List α is simultaneously synchronizing for A if for every index i : Fin k, w is synchronizing for automaton A i.
Statement
def dfa_is_simultaneously_synchronizing {α : Type*} {k : ℕ} {σ : Fin k → Type*} (A : (i : Fin k) → DFA α (σ i)) (w : List α) : Prop
- Defined in
- arXiv:2611.09136
- Verified
- 15 Nov 2026
- Axioms
- none listed
- Built on 1
- dfa_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all…
- dfa_is_synchronizingA word
- Used by 3
- 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…
- op_1716_two_automata_subset_sync_le_two_optFor any two deterministic finite automata A (k = 2) and any two-stage sequential subset synchronization choice ws, the total length (ws…
- dfa_seq_subset_sync_stage_le_simultaneousFor any family of k deterministic finite automata A, any sequential subset synchronization choice ws, and any simultaneously synchronizing…
Read back from the Lean
Given an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, a family of DFAs A : (i : Fin k) → DFA α (σ i) sharing the alphabet α, and a word w : List α, dfa_is_simultaneously_synchronizing A w asserts that for every index i : Fin k, the word w is a synchronizing word for the DFA A i (that is, dfa_is_synchronizing (A i) w holds).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A word synchronizes a family of deterministic finite automata with heterogeneous state spaces if it synchronizes each automaton in the family. -/ def dfa_is_simultaneously_synchronizing {α : Type*} {k : ℕ} {σ : Fin k → Type*} (A : (i : Fin k) → DFA α (σ i)) (w : List α) : Prop := ∀ i : Fin k, dfa_is_synchronizing (A i) w