On directable nondeterministic trapped automata
On directable nondeterministic trapped automata
复制标题
关于可定向非确定性俘获自动机
DOI：
10.5555/896971.896974
复制
发表时间：
2003
期刊：
影响因子：
0.4
通讯作者：
Masami Ito
中科院分区：
文献类型：
--
作者：
B. Imreh;C. Imreh;Masami Ito
一个有限自动机被称为可定向的，如果它有一个输入字，一个引导字，它把它从每个状态带到同一个状态。对于非确定性（n.d.）自动机，定向性可以通过几种方式来推广。在[8]中，引入了三个这样的概念，D1-，D2-和D3-定向性。在本文中，我们介绍了陷波的n. d。自动机，并对每个i = 1，2，3，给出了n状态Di-directable陷n.d.自动机事实证明，对于这类特殊的n. d。自动机，更好的界限，可以找到比一般情况下，和一些得到的界限是尖锐的。
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. In [8], three such notions, D1-, D2-, and D3-directability, are introduced. In this paper, we introduce the trapped n.d. automata, and for each i = 1, 2, 3, present lower and upper bounds for the lengths of the shortest Di-directing words of n-state Di-directable trapped n.d. automata. It turns out that for this special class of n.d. automata, better bounds can be found than for the general case, and some of the obtained bounds are sharp.