基于信息系统的确定有限自动机最小化算法

• 作者: 姚光顺 杨传健 王波 葛浩
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 确定有限自动机 信息系统 等价类 最小化
• 年，卷（期）: 2012,（7）
• 所属期刊栏目: 人工智能
• 页码范围: 1991-1993,1997
• 分类号: TP301
• 字数: 4424字
• 语种: 中文
• DOI: 10.3724/SP.J.1087.2012.01991

摘要

目前,确定有限自动机(DFA)最小化问题多侧重于理论研究,尚无太多便于实现的算法,为此,对确定有限自动机最小化方法进行了研究,提出将DFA转换为信息系统,基于等价类划分方法简化信息系统,再将简化的信息系统转换为最小化DFA；针对上述处理过程,给出一个基于分治思想的DFA最小化算法,在平均情况下该算法的时间复杂度为O(n log n),空间复杂度为O(n).最后通过实例验证了所提算法的正确性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	葛浩	滁州学院机械与电子工程学院	52	512	11.0	21.0
2	杨传健	滁州学院计算机与信息工程学院	39	411	10.0	19.0
3	姚光顺	滁州学院计算机与信息工程学院	24	67	4.0	7.0
4	王波	滁州学院机械与电子工程学院	37	68	4.0	7.0