Differential Semigroups of Automaton Perturbations and Incremental Syntactic Reconstruction

Let $A=(Q,\Sigma,\delta,q_0,F)$ and $B=(Q,\Sigma,\delta',q_0,F)$ be deterministic finite automata on the same state set and with the same input alphabet. For each word $w\in\Sigma^*$, let $\delta_w,\delta'_w\in Q^Q$ be the induced transformations. We introduce the differential transition semigroup

$$D(A,B)={(\delta_w,\delta'_w):w\in\Sigma^*}\leq Q^Q\times Q^Q,$$

and the defect set

$$\operatorname{Def}(f,g)={q\in Q:f(q)\neq g(q)}.$$

A composition law for defects is established and used to prove a backward localization theorem: the disagreement of every word-induced pair is contained in the backward saturation of the set of locally modified states. Consequently, if the initial state lies outside the backward saturation, then the recognized language is invariant and the syntactic semigroups coincide. A local update algorithm is then obtained whose running time depends on the saturation size rather than on the full transition semigroup. The construction yields a rigorous differential framework for dynamic automata and incremental syntactic reconstruction.