Abstract:
A deterministic incomplete automaton A=⟨Q,Σ,δ⟩ is said to be 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 transformation domain. We show that if A possesses an annihilating word w∈Σ∗ whose action is nowhere defined, then A is annihilated by a word whose length does not exceed |Q|+⌊|Q|−12⌋, and this bound is tight.
Keywords:
synchronizable automaton, reset word, partial automaton, annihilating word.
This publication is cited in the following 2 articles:
M. V. Volkov, “Synchronization of finite automata”, Russian Math. Surveys, 77:5 (2022), 819–891
Turker U.C., Yenigun H., “Complexities of Some Problems Related To Synchronizing, Non-Synchronizing and Monotonic Automata”, Int. J. Found. Comput. Sci., 26:1 (2015), 99–121