Abstract:
A deterministic incomplete automaton $\mathscr A=\langle Q,\Sigma,\delta\rangle$ is said to be partially monotonic if its state set $Q$ admits a linear order such that each partial transformation $\delta(\_,a)$ with $a\in\Sigma$ preserves the restriction of the order to the transformation domain. We show that if $\mathscr A$ possesses an annihilating word $w\in\Sigma^*$ whose action is nowhere defined, then $\mathscr A$ is annihilated by a word whose length does not exceed $|Q|+\bigl\lfloor\frac{|Q|-1}2\bigr\rfloor$, and this bound is tight.
Keywords:synchronizable automaton, reset word, partial automaton, annihilating word.