On Monotonic Directable Nondeterministic Automata
On Monotonic Directable Nondeterministic Automata
复制标题
关于单调可定向非确定性自动机
DOI：
10.25596/jalc-2003-539
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Masami Ito
中科院分区：
文献类型：
--
作者：
B. Imreh;C. Imreh;Masami Ito
如果一个有限自动机有一个输入字可以把它从每个状态带到相同的状态，那么它就被称为可定向自动机。不确定性自动机的可指向性可以用不同的方式来定义。在[7]中，引入了方向性的三个概念，D1-、D2-和D3-方向性。在这里，对于每一个i = 1,2,3，我们给出了n态单调双向自动机的最短双向词的最大长度的明确界限。
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.