期刊文献+
共找到72篇文章
< 1 2 4 >
每页显示 20 50 100
1-Way Multihead Quantum Finite State Automata
1
作者 Debayan Ganguly Kingshuk Chatterjee Kumar Sankar Ray 《Applied Mathematics》 2016年第9期1005-1022,共18页
1-way multihead quantum finite state automata (1QFA(k)) can be thought of modified version of 1-way quantum finite state automata (1QFA) and k-letter quantum finite state automata (k-letter QFA) respectively. It has b... 1-way multihead quantum finite state automata (1QFA(k)) can be thought of modified version of 1-way quantum finite state automata (1QFA) and k-letter quantum finite state automata (k-letter QFA) respectively. It has been shown by Moore and Crutchfield as well as Konadacs and Watrous that 1QFA can’t accept all regular language. In this paper, we show different language recognizing capabilities of our model 1-way multihead QFAs. New results presented in this paper are the following ones: 1) We show that newly introduced 1-way 2-head quantum finite state automaton (1QFA(2)) structure can accept all unary regular languages. 2) A language which can’t be accepted by 1-way deterministic 2-head finite state automaton (1DFA((2)) can be accepted by 1QFA(2) with bounded error. 3) 1QFA(2) is more powerful than 1-way reversible 2-head finite state automaton (1RMFA(2)) with respect to recognition of language. 展开更多
关键词 1-Way Quantum finite State automaton (1QFA) k-Letter Quantum finite State Automata (k-Letter QFA) 1-Way Multihead Quantum finite State automaton (1QFA(k)) 1-Way deterministic 2-Head finite State automaton (1dfa((2)) 1-Way Reversible Multihead finite State automaton (1RMFA(k))
下载PDF
Xgadget:基于动静结合的二进制Gadget搜索
2
作者 吕建强 付才 +3 位作者 何帅 江帅 李明 韩兰胜 《计算机工程与应用》 CSCD 北大核心 2024年第9期299-308,共10页
代码复用技术一直以来都是软件安全研究领域的热点,ROP(return-oriented programming)、JOP(jump-oriented programming)和DOP(data-oriented programming)技术是典型代表。Gadget搜索是代码复用的基础,针对现有静态搜索算法存在支持的G... 代码复用技术一直以来都是软件安全研究领域的热点,ROP(return-oriented programming)、JOP(jump-oriented programming)和DOP(data-oriented programming)技术是典型代表。Gadget搜索是代码复用的基础,针对现有静态搜索算法存在支持的Gadget类型不多,不能同时搜索动态链接库等问题,提出了基于动静结合的二进制Gadget搜索方法,基于此开发了搜索工具Xgadget。利用动态映像级插桩,对所有函数进行反汇编;设计了Token级和指令级有穷自动机,实现了基于自动机的静态搜索算法;在五款应用程序中对其进行了测试与评估。实验结果表明,算法支持ROP、JOP、DOP等多种Gadget类型的搜索,能够同时对目标程序动态链接库进行搜索,搜索数量是ROPgadget的12.5倍,单位指令搜索时间较之降低32.1%。算法为不同需求的代码复用提供更为广泛的支持,且输出结果是二进制Gadget,后续复用更直接,有利于代码复用自动化利用。 展开更多
关键词 代码复用 Gadget搜索 动静结合 dfa算法 二进制 DOP方法 动态链接库
下载PDF
一种新的DFA状态最小化算法 被引量:2
3
作者 范书义 孟晨 王成 《计算机工程与应用》 CSCD 2012年第1期47-48,67,共3页
提出了一种基于状态转换矩阵的适合计算机实现的DFA状态最小化算法,在计算等价状态过程中,通过记录扫描过程中发现的具有相同输入字符和相同转换状态的状态判定链表,算法可以用一遍扫描和与传统算法相近的存储空间实现DFA状态的最小化... 提出了一种基于状态转换矩阵的适合计算机实现的DFA状态最小化算法,在计算等价状态过程中,通过记录扫描过程中发现的具有相同输入字符和相同转换状态的状态判定链表,算法可以用一遍扫描和与传统算法相近的存储空间实现DFA状态的最小化。与传统的DFA状态最小化算法相比,该算法具有较好的时间复杂度和相同的空间复杂度。 展开更多
关键词 确定有穷自动机(dfa) 状态最小化 状态转换矩阵
下载PDF
使用DFA的Web会话构造方法 被引量:1
4
作者 黄金晶 赵雷 杨季文 《计算机工程与应用》 CSCD 北大核心 2009年第8期138-140,共3页
会话识别是Web使用挖掘数据预处理中重要的一个环节。将确定的有限自动机(DFA)思想运用于会话构造,针对一段用户访问日志,通过DFA中各个状态间的转换,实现会话构造。该方法更多考虑页面之间的连续性,关注用户的实际访问序列,有利于后续... 会话识别是Web使用挖掘数据预处理中重要的一个环节。将确定的有限自动机(DFA)思想运用于会话构造,针对一段用户访问日志,通过DFA中各个状态间的转换,实现会话构造。该方法更多考虑页面之间的连续性,关注用户的实际访问序列,有利于后续的用户访问模式的挖掘。 展开更多
关键词 WEB使用挖掘 数据预处理 会话识别 确定的有限自动机(dfa)
下载PDF
识别幺半群强半格的最少状态DFA 被引量:1
5
作者 黎宏伟 《江苏师范大学学报(自然科学版)》 CAS 2017年第4期36-38,共3页
为了研究识别幺半群强半格的最少状态DFA,对幺半群强半格的R类进行了深入探讨,证明了当每个幺半群中只有一个R类时,幺半群强半格中的R类的个数就是幺半群的个数,且半群中的R类是正规语言中的一种右不变等价类.借助这两个结论,证明了识... 为了研究识别幺半群强半格的最少状态DFA,对幺半群强半格的R类进行了深入探讨,证明了当每个幺半群中只有一个R类时,幺半群强半格中的R类的个数就是幺半群的个数,且半群中的R类是正规语言中的一种右不变等价类.借助这两个结论,证明了识别幺半群强半格的最少状态DFA的终结状态的个数等于幺半群的个数,并建立了识别幺半群强半格的最少状态DFA. 展开更多
关键词 强半格 幺半群 确定型有穷自动机
下载PDF
一个完善的基于判定链表的DFA最小化算法
6
作者 陈矗 任平红 +1 位作者 禹继国 马炳先 《计算机工程与应用》 CSCD 2013年第6期48-51,共4页
应用判定链表进行DFA最小化方法中只处理无互相依赖等价状态会造成最小化结果不正确。针对此问题,分析了DFA中状态的k次传递等价、含自回路状态的等价以及互相依赖等价等结构特点,将分析结果应用于DFA最小化算法中,提出了一个完善的基... 应用判定链表进行DFA最小化方法中只处理无互相依赖等价状态会造成最小化结果不正确。针对此问题,分析了DFA中状态的k次传递等价、含自回路状态的等价以及互相依赖等价等结构特点,将分析结果应用于DFA最小化算法中,提出了一个完善的基于判定链表的DFA最小化算法。该算法涵盖所有等价状态的链表处理,与传统的分割或合并算法的最小化结果一致,保证了基于判定链表的最小化结果的正确性。 展开更多
关键词 判定链表 确定有限状态自动机(dfa) 最小化
下载PDF
ɑFA:一种基于非信任字符比较的高性能正则表达式匹配算法
7
作者 杨嘉佳 关健 +2 位作者 于增明 张雷 姚旺君 《电子技术应用》 2024年第6期57-60,共4页
正则表达式匹配技术在数据治理、解析提取和深度包检测方面有着重大应用价值。然而,由于其在通用平台上的匹配性能较低,无法满足实际环境下数据实时处理的应用需求,限制了其在高性能数据处理领域的应用范围。针对当前正则表达式匹配性... 正则表达式匹配技术在数据治理、解析提取和深度包检测方面有着重大应用价值。然而,由于其在通用平台上的匹配性能较低,无法满足实际环境下数据实时处理的应用需求,限制了其在高性能数据处理领域的应用范围。针对当前正则表达式匹配性能较低的问题,提出一种基于非信任字符比较的高性能正则表达式匹配算法,称之为ɑFA。该算法通过每次判断连续的若干个字符是否属于最常被访问状态的非信任字符集,获取无需通过DFA匹配可直接跳过的字符数,减少字符匹配过程中访问内存DFA状态转移表的次数,从而实现字符匹配的加速处理。实验结果表明,ɑFA算法可获得相比于原始DFA匹配算法约为1.05~7.58倍的性能加速比。 展开更多
关键词 正则表达式匹配 确定型有限自动机 高性能数据处理
下载PDF
On Some Properties of Graph of Prefix Code
8
作者 Nikolai I. Krainiukov Mikhail E. Abramyan Boris F. Melnikov 《Journal of Applied Mathematics and Physics》 2024年第4期1571-1581,共11页
We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be ... We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. . 展开更多
关键词 finite Languages Minimal deterministic Automata CONCATENATION CODES Graph of automaton Free Algebra
下载PDF
一种基于DFA的服务行为模型及其应用
9
作者 曹永忠 丁秋林 《微计算机信息》 北大核心 2007年第21期276-278,共3页
本文对Web服务行为描述进行深入分析,在构造web服务自动集成结构基础上,对原有限自动机定义进行语义扩展和候选集扩展,达到准确地描述Web服务间的执行步骤、行为间简单逻辑运算关系和代价选择运算关系目的。完成服务提供商提供服务流与... 本文对Web服务行为描述进行深入分析,在构造web服务自动集成结构基础上,对原有限自动机定义进行语义扩展和候选集扩展,达到准确地描述Web服务间的执行步骤、行为间简单逻辑运算关系和代价选择运算关系目的。完成服务提供商提供服务流与用户期望在该结构下的自动匹配,为web服务自动集成提供了理论依据。 展开更多
关键词 行为 有限自动机 描述
下载PDF
对DFA最小化算法等价性问题的探讨与改进
10
作者 张坤 刘欣颖 亓静 《科技信息》 2008年第31期77-77,126,共2页
有穷自动机极小化问题的研究,在程序测试、模糊系统、概率自动机等方面具有重要意义。利用自动机状态集上的等价关系对自动机的状态集极小化,从而得到与原自动机功能等价的极小化自动机,该内容是词法分析的重点。很多编译原理书籍介绍的... 有穷自动机极小化问题的研究,在程序测试、模糊系统、概率自动机等方面具有重要意义。利用自动机状态集上的等价关系对自动机的状态集极小化,从而得到与原自动机功能等价的极小化自动机,该内容是词法分析的重点。很多编译原理书籍介绍的DFA最小化算法是"分割法",但该算法存在一定的问题,本文从对一些特殊的DFA的处理入手,分析"分割法"算法在等价原则方面的漏洞,并提出了对最小化问题的改进算法。 展开更多
关键词 确定的有穷自动机 不确定的有穷自动机 等价原则 状态集极小化 分割法
下载PDF
一种针对DFA状态爆炸的正则表达式匹配方法 被引量:4
11
作者 王翔 卢毓海 +1 位作者 马伟 刘燕兵 《计算机工程》 CAS CSCD 北大核心 2019年第4期148-156,共9页
针对基于确定有限状态自动机的匹配引擎在大规模、复杂规则下会出现状态爆炸的问题,提出正则表达式子串抽取算法。通过将子串抽取算法应用于DFA状态爆炸场景,设计基于子串抽取的正则匹配引擎。实验结果表明,该算法在单个规则上运行时间... 针对基于确定有限状态自动机的匹配引擎在大规模、复杂规则下会出现状态爆炸的问题,提出正则表达式子串抽取算法。通过将子串抽取算法应用于DFA状态爆炸场景,设计基于子串抽取的正则匹配引擎。实验结果表明,该算法在单个规则上运行时间可达10 ms量级,抽取率高达99%,同时匹配引擎具有较好的稳定性和可拓展性,且匹配速度优于相关开源匹配引擎。 展开更多
关键词 正则表达式 确定有限自动机 状态爆炸 子串抽取 匹配引擎
下载PDF
面向深度包检测的DFA细粒度并行匹配方法 被引量:5
12
作者 刘兴奎 邵宗有 +1 位作者 刘新春 孙凝晖 《计算机研究与发展》 EI CSCD 北大核心 2014年第5期1061-1070,共10页
确定性有限自动机(DFA)是实现正则表达式匹配的一种有效手段,但DFA的状态跳转是串行的,导致匹配速度慢、难以满足高速骨干网环境深度包检测(DPI)的性能需求.提出了一种称为LBDFA(Loopback DFA)的细粒度并行化状态跳转方法,通过将在Loopb... 确定性有限自动机(DFA)是实现正则表达式匹配的一种有效手段,但DFA的状态跳转是串行的,导致匹配速度慢、难以满足高速骨干网环境深度包检测(DPI)的性能需求.提出了一种称为LBDFA(Loopback DFA)的细粒度并行化状态跳转方法,通过将在Loopback状态上的连续跳转并行化,提高了匹配速度.此外,利用Bloom filter消除该并行跳转中的临时偏离现象,进一步提高了并行潜力.在L7-filter以及Snort规则集上的测试结果表明,LBDFA能够满足10Gbps以上的正则表达式匹配需求. 展开更多
关键词 正则表达式 确定性有限自动机 深度包检测 回环状态 FPGA
下载PDF
基于改进的Trie树和DFA的敏感词过滤算法 被引量:13
13
作者 吴珊 李英祥 +2 位作者 徐鸿雁 张仕霞 施宜军 《计算机应用研究》 CSCD 北大核心 2021年第6期1678-1682,1688,共6页
通过对文本内容中敏感词过滤方法及相关技术的研究,提出了一种基于改进的Trie树和DFA的敏感词过滤算法,解决了敏感词过滤技术中的人工干扰、分词障碍等关键问题,提高了文本中敏感词过滤的准确性和有效性。提出的算法包括三个步骤:基于... 通过对文本内容中敏感词过滤方法及相关技术的研究,提出了一种基于改进的Trie树和DFA的敏感词过滤算法,解决了敏感词过滤技术中的人工干扰、分词障碍等关键问题,提高了文本中敏感词过滤的准确性和有效性。提出的算法包括三个步骤:基于排列组合的数学原理对中文词向中拼混合词进行扩充;采用改进的Trie树结构来存储DFA的所有状态,构建敏感词树;根据构建的敏感词树结构以及采用最小匹配规则对文本内容中的敏感词进行检测和过滤。通过分析得到构建敏感词树算法的时间复杂度为O(n×len),敏感词检测及过滤算法时间复杂度为O(L)。实验结果表明,本算法其查准率为100%,查全率约为87%~100%。 展开更多
关键词 改进的Trie树 确定有穷自动机(dfa) 敏感词过滤 最小匹配规则
下载PDF
基于决策树和DFA的老挝文敏感信息过滤算法 被引量:4
14
作者 王艺皓 丁洪伟 +2 位作者 王丽清 李波 李浩 《计算机应用与软件》 北大核心 2022年第7期241-246,274,共7页
通过对老挝文语言特点的分析,提出一种基于确定有穷自动机和决策树的老挝文敏感信息过滤算法。将老挝文进行词汇划分和编码化处理,合理地解决老挝文与汉语书写上的差异性以及计算机读取存储出现乱码的问题;结合决策树的特点,构建老挝文... 通过对老挝文语言特点的分析,提出一种基于确定有穷自动机和决策树的老挝文敏感信息过滤算法。将老挝文进行词汇划分和编码化处理,合理地解决老挝文与汉语书写上的差异性以及计算机读取存储出现乱码的问题;结合决策树的特点,构建老挝文敏感信息决策树,该树不依赖于词典,且可以实现实时更新;基于确定有穷自动机模型实现了老挝文敏感信息的检测和过滤,同时也实现了实时报警。实验表明,该过滤算法针对老挝文有较高的工作效率,同时也取得了较好的查全率和查准率。 展开更多
关键词 确定有穷自动机 决策树 敏感信息过滤 老挝文过滤 网络舆情
下载PDF
基于DFA复合式Agent模型的设计与实现 被引量:1
15
作者 卢薇薇 蔡自兴 +1 位作者 文志强 陈爱斌 《中南大学学报(自然科学版)》 EI CAS CSCD 北大核心 2010年第2期600-608,共9页
针对机器人团队协作检测与跟踪动态目标的需要,提出1种基于有限状态自动机(DFA)的复合式Agent模型。通过结合有限状态自动机的行为状态模型,对复合式Agent模型进行改进,在固定路线的动态目标跟踪实验中,对改进前后的Agent模型实际实验... 针对机器人团队协作检测与跟踪动态目标的需要,提出1种基于有限状态自动机(DFA)的复合式Agent模型。通过结合有限状态自动机的行为状态模型,对复合式Agent模型进行改进,在固定路线的动态目标跟踪实验中,对改进前后的Agent模型实际实验数据进行比较,并将该模型应用于基于区域的多机器人多目标跟踪实验中。结果表明:改进后的Agent模型通过有限状态自动机中的状态抽象,不仅从目标检测与跟踪的角度提高了Agent个体性能,还从社会的角度,提高了群体团队的协作性能;提出的模型通过行为状态模型将动作、决策等与环境信息进行了有效的分离,从而具有较好的可移植性和高扩展性;改进后的Agent模型跟踪偏差期望值与样本方差均降为改进前的一半,为实时的目标协作检测与跟踪提供了有效途径。 展开更多
关键词 复合式Agent模型 有限状态自动机 动态多目标跟踪
下载PDF
基于DFA的入侵检测方法研究 被引量:1
16
作者 云雷 万紫骞 《电子质量》 2013年第7期7-10,共4页
计算机网络安全环境不断恶化,各种网络攻击行为层出不穷,入侵检测技术作为一种主要的网络安全技术引起了人们的广泛关注。伴随着网络对实时性、吞吐量等的更高要求,入侵检测技术的检测效率逐渐成为系统的瓶颈问题。该文提出了一种基于DF... 计算机网络安全环境不断恶化,各种网络攻击行为层出不穷,入侵检测技术作为一种主要的网络安全技术引起了人们的广泛关注。伴随着网络对实时性、吞吐量等的更高要求,入侵检测技术的检测效率逐渐成为系统的瓶颈问题。该文提出了一种基于DFA模式匹配引擎的入侵检测方法,该方法利用DFA在模式匹配方面的优越性以提高入侵检测系统的检测效率;之后,该文对该方法进行了相关性能分析。该文的研究将有助于入侵检测技术的不断完善与发展。 展开更多
关键词 入侵检测 模式匹配 确定有穷自动机 检测效率
下载PDF
深度包检测中一种高效的正则表达式压缩算法 被引量:28
17
作者 徐乾 鄂跃鹏 +1 位作者 葛敬国 钱华林 《软件学报》 EI CSCD 北大核心 2009年第8期2214-2226,共13页
提出一种基于确定的有穷状态自动机(deterministic finite automaton,简称DFA)的正则表达式压缩算法.首先,定义了膨胀率DR(distending rate)来描述正则表达式的膨胀特性.然后基于DR提出一种分片的算法RECCADR(regular expressions cut a... 提出一种基于确定的有穷状态自动机(deterministic finite automaton,简称DFA)的正则表达式压缩算法.首先,定义了膨胀率DR(distending rate)来描述正则表达式的膨胀特性.然后基于DR提出一种分片的算法RECCADR(regular expressions cut and combine algorithm based on DR),有效地选择出导致DFA状态膨胀的片段并隔离,降低了单个正则表达式存储需求.同时,基于正则表达式的组合关系提出一种选择性分群算法REGADR(regular expressions group algorithm based on DR),在可以接受的存储需求总量下,通过选择性分群大幅度减少了状态机的个数,有效地降低了匹配算法的复杂性. 展开更多
关键词 正则表达式 确定的有穷状态自动机(deterministic finite automaton 简称dfa) 深度包检测(deep packet inspection 简称DPI) 多模式匹配算法 入侵检测
下载PDF
面向存储的正则表达式匹配算法综述 被引量:13
18
作者 姚远 刘鹏 +1 位作者 单征 田双鹏 《计算机应用》 CSCD 北大核心 2009年第12期3171-3173,3177,共4页
正则表达式匹配是当前深度包检测领域中的关键性技术。介绍了面向存储的正则表达式匹配算法的基本思想和设计方法,给出了算法分类并比较了典型压缩算法间的差异,分析了正则表达式语法对算法设计的影响,最后论述了目前研究中面临的技术... 正则表达式匹配是当前深度包检测领域中的关键性技术。介绍了面向存储的正则表达式匹配算法的基本思想和设计方法,给出了算法分类并比较了典型压缩算法间的差异,分析了正则表达式语法对算法设计的影响,最后论述了目前研究中面临的技术难点并对今后算法设计的发展趋势作了展望。 展开更多
关键词 确定的有限自动机 面向存储 正则表达式 深度包检测 压缩算法
下载PDF
一种基于智能有限自动机的正则表达式匹配算法 被引量:14
19
作者 张大方 张洁坤 黄昆 《电子学报》 EI CAS CSCD 北大核心 2012年第8期1617-1623,共7页
本文提出了一种基于智能有限自动机(Smart Finite Automaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与... 本文提出了一种基于智能有限自动机(Smart Finite Automaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与XFA相比,在存储空间开销上减少了44.1%,在存储器访问次数上减少了69.1%. 展开更多
关键词 深度数据包检测 正则表达式匹配 确定型有限自动机 扩展有限自动机 智能有限自动机
下载PDF
基于稀疏矩阵存储的状态表压缩算法 被引量:5
20
作者 姚远 刘鹏 +1 位作者 王辉 笱程成 《计算机应用》 CSCD 北大核心 2010年第8期2157-2160,2217,共5页
正则表达式匹配对于网络安全应用至关重要。将稀疏矩阵和索引表引入确定的有限自动机的状态转换表,提出了一种稀疏矩阵索引的状态压缩表算法,并给出了稀疏矩阵和索引表的构造方法。而后同字母压缩表算法结合,给出了该算法的优化策略。... 正则表达式匹配对于网络安全应用至关重要。将稀疏矩阵和索引表引入确定的有限自动机的状态转换表,提出了一种稀疏矩阵索引的状态压缩表算法,并给出了稀疏矩阵和索引表的构造方法。而后同字母压缩表算法结合,给出了该算法的优化策略。最后在实际规则集上进行评估,实验结果证明了算法的压缩效果,并进一步得出了算法的适用范围。 展开更多
关键词 确定的有限自动机 深度包检测 正则表达式 稀疏矩阵 压缩算法
下载PDF
上一页 1 2 4 下一页 到第
使用帮助 返回顶部