AFTD Auto-Formalizing Theoretical Domains

dfa_is_subset_synchronizing

def

A word w : List α is subset-synchronizing for a subset S : Set σ of states of a deterministic finite automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for all q₁ q₂ ∈ S.

Statement

def dfa_is_subset_synchronizing {α σ : Type*} (A : DFA α σ) (S : Set σ) (w : List α) : Prop
Defined in
arXiv:2611.09136 Sec. 7
Verified
09 Nov 2026
Axioms
none listed
Used by 8

Read back from the Lean

Given types α and σ, a DFA A with alphabet α and state type σ, a subset of states S : Set σ, and a word w : List α, dfa_is_subset_synchronizing A S w defines the proposition that for all states q₁ ∈ S and q₂ ∈ S, the state reached by running A on input w starting from q₁ is equal to the state reached by running A on w starting from q₂.

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 subset of states in a DFA if it maps all states in the subset to a common state. -/
def dfa_is_subset_synchronizing {α σ : Type*} (A : DFA α σ) (S : Set σ) (w : List α) : Prop := ∀ q₁ ∈ S, ∀ q₂ ∈ S, A.evalFrom q₁ w = A.evalFrom q₂ w
See it in the graphDiscuss this resultChallenge it