Minimization of Non-deterministic Automata with Large Alphabets
Minimization of Non-deterministic Automata with Large Alphabets
复制标题
具有大字母的非确定性自动机的最小化
DOI：
10.1007/11605157_3
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Marcus Nilsson
中科院分区：
文献类型：
--
作者：
P. Abdulla;J. Deneux;Lisa Kaati;Marcus Nilsson
多年来，已经有几次尝试来解决有限自动机的互模拟最小化问题。最著名的算法之一是Paige和Tarjan提出的算法。该算法的复杂度为（mlogn），其中m是自动机中的边数，m是自动机中的状态数。算法应用中的一个瓶颈通常是可能出现在自动机边缘的标签数量。在本文中，我们适应Paige-Tarjan算法的情况下，标签的符号表示使用二进制决策图（BDDs）。我们表明，我们的算法有一个整体的复杂性，其中的字母表的大小。这意味着我们的算法将具有与其他算法相同的最坏情况行为。然而，正如我们的原型实现所示，由于BDD提供的紧凑表示，我们在性能上得到了巨大的提高。
There has been several attempts over the years to solve the bisimulation minimization problem for finite automata. One of the most famous algorithms is the one suggested by Paige and Tarjan. The algorithm has a complexity of(mlogn) wheremis the number of edges andnis the number of states in the automaton. A bottleneck in the application of the algorithm is often the number of labels which may appear on the edges of the automaton. In this paper we adapt the Paige-Tarjan algorithm to the case where the labels are symbolically represented using Binary Decision Diagrams (BDDs). We show that our algorithm has an overall complexity ofwhere ℓ is the size of the alphabet. This means that our algorithm will have the same worst case behavior as other algorithms. However, as shown by our prototype implementation, we get a vast improvement in performance due to the compact representation provided by the BDDs.