On monogenic nondeterministic automata

  • Csanád Imreh
  • Masami Ito


A finite automaton is said to be directable if it has an input word, a directing word, which takes it from every state into the same state. For nondeterministic (n.d.) automata, directability can be generalized in several ways, three such notions, D1-, D2-, and D3-directability, are used. In this paper, we consider monogenic n.d. automata, and for each i = 1,2,3, we present sharp bounds for the maximal lengths of the shortest Di-directing words.


Download data is not yet available.
How to Cite
Imreh, C., & Ito, M. (2008). On monogenic nondeterministic automata. Acta Cybernetica, 18(4), 777-782. Retrieved from https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3749
Regular articles