THE SMALLEST AUTOMATION RECOGNIZING THE SUBWORDS OF A TEXT
THE SMALLEST AUTOMATION RECOGNIZING THE SUBWORDS OF A TEXT
复制标题
DOI：
10.1016/0304-3975(85)90157-4
复制
发表时间：
1985-09-01
影响因子：
1.1
通讯作者：
SEIFERAS, J
中科院分区：
文献类型：
--
作者：
BLUMER, A;BLUMER, J;SEIFERAS, J
设一个部分确定的有限自动机是一个DFA，其中每个状态不需要有一个过渡边缘的字母表的每个字母。我们证明了对于给定单词w的所有子词的集合的最小部分DFA，|W|>2，最多2个|W|-2个州和3个州|W|-4个过渡边，与字母表大小无关。我们给出了一个算法，以建立这个最小的部分DFA从输入线在线性时间。
Let a partial deterministic finite automaton be a DFA in which each state need not have a transition edge for each letter of the alphabet. We demonstrate that the smallest partial DFA for the set of all subwords of a given wordw, |w|>2, has at most 2|w|−2 states and 3|w|−4 transition edges, independently of the alphabet size. We give an algorithm to build this smallest partial DFA from the inputwon-line in linear time.