-
题名确定型格值有限自动机的最小化
被引量：2
- 1
-
-
作者
李斌
舒兰
-
机构
电子科技大学应用数学学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2010年第32期52-54,共3页
-
基金
国家自然科学基金(No.10671030)~~
-
文摘
给出了确定型格值有限自动机的定义,并同时给出了有效终止状态和可达到状态的定义。指出了求取DLFAM=(Q,Σ,δ,q0,σ)的实质是求取Q/Rk。由此以可到达状态为基础引入了等价关系Rk、Sk与商集Q/Sk,证明了Rk=Rk-1∩Sk,由此得到Q/Rk的等价类为Q/Rk-1中等价类与Q/Sk中等价类的非空交集全体。引入了Hk,并证明了可由Hk求取Q/Sk,从而得到仅利用集合运算便可求取Q/Rk的算法,最终给出了DLFA最小化算法的一个容易实现的构造型描述和相应示例。
-
关键词
格半群
确定型有限状态自动机
等价关系
商集
最小化
最小化算法
-
Keywords
lattice-ordered monoid； deterministic lattice finite automata； equivalence relation； quotient set； minimization； minimization algorithm；
-
分类号
O235
[理学—运筹学与控制论]
TP23
[理学—数学]
-
-
题名一种正则表达式匹配的存储空间优化技术
- 2
-
-
作者
华馨伊
黄献策
李启明
-
机构
上海海事大学信息工程学院
-
出处
《现代计算机（中旬刊）》
2017年第7期8-12,共5页
-
基金
国家自然科学基金(No.61472237)
上海市自然科学基金(No.14ZR1419700)
-
文摘
针对有限状态自动机DFA构造过程中出现状态爆炸导致存储空间大、匹配效率低等问题,提出一种基于规则分组及状态边压缩相结合的正则表达式引擎优化算法GCFA,通过将规则基于关联性进行分组,对各个分组所构造的联合DFA采用存储连续字符的范围代替单一字符以达到减少存储空间的目的。实验结果证明,与标准DFA构造算法相比较,GCFA算法对状态转移边的压缩率达到98%,与经典改进算法相比较,降低2个数量级的存储空间。
-
关键词
深度报文检测
网络安全
确定型有限状态自动机
正则表达式匹配
规则分组
-
Keywords
Deep Packet Inspection
Network Security
Deterministic Finite Automaton
Regular Expression Matching
Multiple DFAs
-
分类号
TP333
[自动化与计算机技术—计算机系统结构]
-
