Порог аннуляции для частично монотонных автоматов

Детерминированный неполный автомат $\mathscr A=\langle Q,\Sigma,\delta\rangle$ называется частично монотонным, если на множестве его состояний $Q$ можно ввести такой линейный порядок, что каждое частичное преобразование $\delta(\_,a)$, где $a\in\Sigma$, сохраняет ограничение этого порядка на свою область определения. В работе показано, что если для $\mathscr A$ найдется какое-либо аннулирующее его слово $w\in\Sigma^*$, действие которого нигде не определено, то автомат $\mathscr A$ можно аннулировать словом длины не более $|Q|+\bigl\lfloor\frac{|Q|-1}2\bigr\rfloor$, причем приведенная оценка точна.