On Monotonic Directable Nondeterministic Automata

A finite automaton is called directable if it has an input word which takes it from every state into the same state. Directability of nondeterministic (n. d.) automata can be defined in different ways. In [7], three notions of directability, D1-, D2-, and D3- directability, are introduced. Here, for each i = 1, 2, 3, we present sharp bounds for the maximal lengths of the shortest Di-directing words of n-state monotonic Di-directable n.d. automata.