UIO序列生成算法的继续改进  

Further improved UIO sequences generation algorithm

作　　者：黎中文[1] 张来顺[1] 

机构地区：[1]解放军信息工程大学电子技术学院,河南郑州450004

出　　处：《计算机工程与设计》2011年第11期3722-3724,3839,共4页Computer Engineering and Design

摘　　要：为解决传统的UIO(唯一输入输出)序列方法中使用的UIO搜索树规模过于庞大的问题,分析了UIO树的构造过程,并结合LANG算法提出的一系列的剪枝方法和节点链搜索技术,提出了一种改进的UIO序列算法,使用转换表格连接方法替代传统的构造UIO树的方法,并将节点链搜索技术在算法循环调用,去掉不需要的节点,加快UIO序列生成,降低搜索空间。通过实验结果表明,与现有算法相比,该算法在降低时间复杂度和空间复杂度两方面有较大改进。To deal with the too huge size of the UI0 searching tree used in the traditional UIO sequences methods, the process of constructing the UIO tree is analyzed. Combined with the series of pruning methods and chain-node search technology proposed in LANG algorithm, a improved UIO tree sequences generation algorithm is proposed. The connection method with the translation table is used instead of the traditional method of constructing UIO tree, and chain-node search technology are recycled call, to remove the nodes un- necessary, the search space is reduced and the UIO sequence generation is speed up. Experiments show the improvement in reducing both of the time complexity and space complexity, compared with existing algorithms.

关 键 词：有限自动机 唯一输入输出序列 表格连接 标记状态 节点链搜索技术 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]