The annulation threshold for partially monotonic automata
Dmitry S. Ananichev · Russian Mathematics · 2010
A deterministic incomplete automaton = 〈Q, Σ, δ〉 is partially monotonic if its state set Q admits a linear order such that each partial transformation δ(_, a) with a ∈ Σ preserves the restriction of the order to the domain of the transformation. We show that if possesses an annihilator word w ∈ Σ* whose action is nowhere defined, then is annihilated by a word of length $$ \left| Q \right| + \left\lfloor {\frac{{\left| Q \right| - 1}} {2}} \right\rfloor $$ and this bound is tight.