An efficient incremental DFA minimization algorithm
An efficient incremental DFA minimization algorithm
复制标题
一种高效的增量DFA最小化算法
DOI：
--
复制
发表时间：
2003
影响因子：
2.5
通讯作者：
J. Daciuk
中科院分区：
文献类型：
--
作者：
B. Watson;J. Daciuk
在本文中，我们提出了一种新的确定性有限自动机（DFA）最小化算法。该算法是增量的——它可以随时停止，从而产生部分最小化的自动机。所有其他（已知）最小化算法都具有不可用于部分最小化的中间结果。由于第一种算法易于理解但效率低下，我们考虑三种实用且有效的优化。前两个优化不会影响渐近最坏情况的运行时间——尽管它们在一大类自动机上表现良好。第三次优化产生了二次时间算法，该算法与之前已知的算法具有竞争力。
In this paper, we present a new Deterministic Finite Automata (DFA) minimization algorithm. The algorithm is incremental – it may be halted at any time, yielding a partially-minimized automaton. All of the other (known) minimization algorithms have intermediate results which are not useable for partial minimization. Since the first algorithm is easily understood but inefficient, we consider three practical and effective optimizations. The first two optimizations do not affect the asymptotic worst-case running time – though they perform well on a large class of automata. The third optimization yields an quadratic-time algorithm which is competitive with the previously known ones.