构造型的D2FA生成算法

doi:10.13190/jbupt.2009s1.40.zhouh

北京邮电大学学报

构造型的D²FA生成算法

周颢;刘振华;赵保华

1. 中国科学技术大学计算机科学与技术系; 2. 安徽省计算与通讯软件重点实验室

收稿日期:2009-04-13 修回日期:1900-01-01 出版日期:2009-04-28 发布日期:2009-04-28
通讯作者: 周颢
基金资助:

Research of Constructing Algorithm to Create D²FA

Received:2009-04-13 Revised:1900-01-01 Online:2009-04-28 Published:2009-04-28
Supported by:

摘要/Abstract

摘要： Delayed input DFA (D²FA)中引入默认边来对确定状态机(DFA)进行状态转移精简. 为了提高D²FA生成算法的效率，分析了对正则表达式X得到的DFA(^∧X)与DFA(X)间的相关性，提出一种从DFA(^∧X)到D²FA(X)的构造型算法. 该算法将DFA(X)中的状态用DFA(^∧X)中的状态序列进行表示，从而基于状态序列进行默认边的选择，而不需要生成实际的DFA(X). 理论分析和实验结果表明，该算法降低了构造D²FA的算法复杂度，同时仍能保证进行模式匹配时的解析时间下限，以及对DFA的状态转移精简能力.

关键词: 确定状态机, D2FA, 默认边

Abstract: Delayed input deterministic finite automata (D²FA) reduces the transition edges of deterministic finite automata (DFA) by introducing default edges. The relevance between DFA(^∧X)and DFA(X) is analyzed to improve the efficiency of constructing algorithm to create D2FA. A constructing algorithm is presented to create D²FA from DFA. The algorithm expresses the state of DFA(X) with the state sequence of DFA(^∧X), hence the choice of default edges is relayed on the state sequence, rather than creating actual DFA(X). Experiments show that the algorithm greatly reduces the complexity of constructing D²FA, meanwhile it ensures a lower time bounds of pattern match and capacity of reducing state transition.

Key words: deterministic finite automata, delayed input deterministic finite automata, default edge

中图分类号:

周颢;刘振华;赵保华. 构造型的D²FA生成算法[J]. 北京邮电大学学报, doi: 10.13190/jbupt.2009s1.40.zhouh .

[1]	李勃. 路况PTZ摄像机自动标定方法[J]. 北京邮电大学学报, 2009, 32(s1): 24-29.
[2]	冯瑞军;魏丽红;刘涛;张晨;周文安. 数据网设备配置下发接口及应用[J]. 北京邮电大学学报, 2009, 32(s1): 140-143.
[3]	杨光松;肖明波;程恩;张静. 水声传感网中节省能量的寻路机制[J]. 北京邮电大学学报, 2009, 32(s1): 88-92.
[4]	成孝刚;陈启美;刘国庆. 总有界变差与图像清晰度之间的关系[J]. 北京邮电大学学报, 2009, 32(s1): 120-122.
[5]	石恒华;何泾沙;许鑫. 基于三元组信息的网络流量检测点选取算法[J]. 北京邮电大学学报, 2009, 32(s1): 73-76.
[6]	郑杰;屈玉贵;赵保华. 嵌入式无线传感器网络自组织通信协议栈[J]. 北京邮电大学学报, 2009, 32(s1): 84-87.
[7]	李文璟;王迎雪;王颖. 基于分域的IT配置管理数据库信息模型[J]. 北京邮电大学学报, 2009, 32(s1): 5-9.
[8]	潘耘;王励成;余镇危;梁辉. 基于随机进程代数的Overlay网络上的QoS性能评价[J]. 北京邮电大学学报, 2009, 32(s1): 129-133.
[9]	陈兴渝;钟朝亮. 基于Web的告警实时显示系统的设计与实现[J]. 北京邮电大学学报, 2009, 32(s1): 115-119.
[10]	徐鹏;黄兴平;龙湘明. 下一代网络业务领域模型及应用[J]. 北京邮电大学学报, 2009, 32(s1): 106-110.
[11]	黄文明;兰静;张阳. 基于改进蚁群算法的网格资源调度[J]. 北京邮电大学学报, 2009, 32(s1): 111-114.
[12]	肖刚;易雅新;肖俊;卢宁. 基于SNMP、WBEM和WSDM的系统管理技术比较[J]. 北京邮电大学学报, 2009, 32(s1): 134-139.
[13]	芮兰兰;郭春明;邱雪松;孟洛明. 下一代网络终端管理系统体系结构及流程实现[J]. 北京邮电大学学报, 2009, 32(s1): 77-83.
[14]	宋玲;陈凤. 支持MPLS流量工程的选播路由[J]. 北京邮电大学学报, 2009, 32(s1): 97-101.
[15]	陈平;乔秀全;刘臻;田小萍. 数据挖掘网格中决策树并行算法设计及性能分析[J]. 北京邮电大学学报, 2009, 32(s1): 49-52.

构造型的D²FA生成算法

Research of Constructing Algorithm to Create D²FA

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价