带记忆的Boyer-Moore型模式匹配算法及其复杂性分析

通过构建前缀匹配自动机,使得每轮匹配后下个匹配窗口的文本总是保持左端部分为模式的一个前缀、右端部分全为未比较过的字符的形式.对于与此相应的模式匹配算法,已证明文本内的每个字符在整个匹配过程中最多被比较一次,从而字符总比较次数不超过n,已达到任意算法最坏情况下字符总比较次数的最小值.另外,在适当条件下还从理论上证明了此算法的亚线性(即字符总比较次数小于cn,其中常数c＜1).根据实验结果,算法的实际运行速度快于Boyer-Moore算法.     

利用水平分割法计算给定串中的所有Maximal(NE/SNE) Repeats

提出一种利用给定符号串x［1…n］的后缀数组和最 长公共前缀数组求x所有最大重复的新方法〖CD2〗水平分割法. 通过对x的最大不可扩展重复和最大超级不可扩展重复所有可能出现的位置以及判定条件的提炼, 分别给出仅由x的后缀数组和最长公共前缀数组求x的所有最大重复、 最大不可扩展重复和最大超级不可扩展重复的算法. 该算法克服了除后缀数组和最长公共前缀数组外, 还需利用其他辅助数组的缺陷, 降低了空间开销, 且时间复杂度没有增加, 并可以在对最长公共前缀数组仅进行一次扫描的情况下求出给定串的所有最大重复、 最大不可扩展重复和最大超级不可扩展重复.     

KMP的多种计算方法

通过对串的前缀、后缀、交迭的介绍，引出了对失败函数的求解，解决了KMP算法中匹配串的移动问题，并提出了各种计算方法．该方法和传统的KMP算法的时间复杂度都为O(m n)．     

一种新的多模式快速匹配算法

提出了一种针对多模式的快速模式匹配算法.算法分为预处理阶段和匹配阶段两个部分,预处理阶段对所有待匹配的模式进行分析,构造一个关于这些模式的树型有限状态自动机,匹配阶段利用这个模式自动机,对文本串进行一次性的搜索,查找文本是否包含模式集中的模式.为了提高了匹配速度,算法利用已匹配的字符串信息实行跳跃式的比较,避免了文本扫描指针的回溯.     

时间自动机与自动验证

给出时间自动机的基本概念,描述了区域自动机的构造方法,并且实现了区域自动机的构造算法.简述了通过时间自动机进行自动验证的过程,最后分析了区域自动机构造算法的时间复杂度.     

一种基于后缀数组的多重复模式匹配算法

要在海量的信息中进行多重复模式的查找,应用一般的查找方法所需O(n2)的复杂度.为了提高模式查找算法的效率,提出了算法Epattern searcher H.该算法是采用能节省空间占用的后缀数组数据结构来实现,同时又运用过滤算法的思想而设计,从而提高算法的运行速度.这里针对英文小说高频词的查找对算法进行测试,可得到时间复杂度为O(n)实验结果.     

一种快速的字串交叉模式匹配算法

介绍了一种基于高频字串提取的快速字串交叉模式匹配算法，同已有的KMP，BM等单模式匹配算法和有限自动机等多模式匹配算法相比，在字符集∑较大且字串个数远大于字串最大长度的情况下，该算法具有较低的时间复杂度和空间复杂度，并适用于字符集较大，词长较短的文本处理。     

一种新的多模式快速匹配算法

提出了一种针对多模式的快速模式匹配算法。算法分为预处理阶段和匹配阶段两个部分，预处理阶段对所有待匹配的模式进行分析，构造一个关于这些模式的树型有限状态自动机，匹配阶段利用这个模式自动机．对文本串进行一次性的搜索，查找文本是否包含模式集中的模式。为了提高了匹配速度，算法利用已匹配的字符串信息实行跳跃式的比较，避免了文本扫描指针的回溯。     

一种传感器网络中频繁移动模式挖掘算法

针对传感器网络中包括目标位置和时间的二维属性频繁移动模式挖掘问题,建立了一种新的树状结构OMP-tree,OMP-tree可以压缩存储大量的原始移动模式.同时提出了一种条件搜索算法,使用该算法可以大大减少满足条件的前缀模式数量.基于OMP-tree和条件搜索算法,设计了一种新的挖掘目标的频繁移动模式算法OMP-mine.该算法基于模式增长思想,直接递归地从条件模式基中得到频繁的前缀模式,然后连接后缀,达到模式增长的目的.仿真结果表明,OMP-mine算法可以有效挖掘出传感器网络中具有二维属性的频繁移动模式,并较好地降低了算法的时间和空间复杂度.     

基于前缀的BM串匹配改进算法

采用文献[11]求解子串前缀的方法，给出了BM算法一个改进算法。改进算法最坏情况下的时间复杂度达到O(m*n／k)，有效地减少了字符重复比较的次数，提高了匹配效率。     

自动机和形式语言结构的理论研究

利用半群代数理论进一步讨论了自动机和形式语言的理论结构．首先构造了一个简单的有穷自动机的么半群，用代数理论分析了其性质，并推广到非确定性有穷自动机的情况．然后对字母表关于连接运算构成的么半群的性质作了进一步探讨，并给出了二进制串生成的半环，及研究了它的结构理论。     

非确定型有穷自动机的极小化

利用自动机状态集上的等价关系对自动机的状态集进行极小化, 从而得到与原自动机功能等价的极小化自动机. 通过两台确定型有穷自动机（DFA）的连接, 构造一台非确定型有穷自动机（NFA）. 利用这两台确定型有穷自动机状态集上的等价关系, 可以构造这台非确定型有穷自动机状态集上的等价关系, 从而对这台非确定型有穷自动机进行极小化. 结果表明这台非确定型有穷自动机的极小化自动机的状态复杂 度, 不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度; 并且自动机在等价关系基础上进行极小化时不改变识别语言.     

确定有限自动机推理的可计算逻辑分析

针对确定有限自动机对输入符号串的识别过程,提出了采用可计算逻辑来分析确定有限自动机的功能结构及其状态转换函数.在可计算逻辑中,计算问题是机器和环境博弈的过程.同样确定有限自动机对输入符号串的识别过程也可当作机器与用户的博弈,如果输入符号串满足确定有限自动机的语法规则能够识别出来,表示机器赢,否则用户赢.     

基于KMP算法的有限自动机的确定化

一般非确定有限自动机转化为确定的有限自动机,其时间复杂度是指数函数级.对于小规模的,以输入串为识别语言的非确定的有限自动机,可采用本文介绍的方法加以确定化,其效率有极大的提高.     

Linearly programmed DNA-based molecular computer operated on magnetic particle surface in test-tube

The postgenomic era has seen an emergence of new applications of DNA manipulation technologies, including DNA-based molecular computing. Surface DNA computing has already been reported in a number of studies that,however, all employ different mechanisms other than automaton functions. Here we describe a programmable DNA surface-computing device as a Turing machine-like finite automaton. The laboratory automaton is primarily composed of DNA (inputs, output-detectors, transition molecules as software), DNA manipulating enzymes and buffer system that solve artificial computational problems autonomously. When fluoresceins were labeled in the 5‘ end of (-) strand of the input molecule, direct observation of all reaction intermediates along the time scale was made so that the dynamic process of DNA computing could be conveniently visualized. The features of this study are: (i) achievement of finite automaton functions by linearly programmed DNA computer operated on magnetic particle surface and (ii)direct detection of all DNA computing intermediates by capiilary electrophoresis. Since DNA computing has the massive parallelism and feasibility for automation, this achievement sets a basis for large-scale implications of DNA computing for functional genomics in the near future.     

对DFA最小化算法等价性问题的探讨与改进

有穷自动机极小化问题的研究,在程序测试、模糊系统、概率自动机等方面具有重要意义。利用自动机状态集上的等价关系对自动机的状态集极小化,从而得到与原自动机功能等价的极小化自动机,该内容是词法分析的重点。很多编译原理书籍介绍的DFA最小化算法是＂分割法＂,但该算法存在一定的问题,本文从对一些特殊的DFA的处理入手,分析＂分割法＂算法在等价原则方面的漏洞,并提出了对最小化问题的改进算法。     

线性混合系统的一种验证方法

混合系统是指嵌入于物理环境中的数字实时系统．由于计算机技术的快速发展,混合系统在各行各业中都得到广泛应用,但是由于混合系统涉及到连续时间,因此其验证问题始终没有得到完善的解决．近年来,人们普遍采用模型检验方法对混合系统进行验证．由于线性混合系统在实际应用中可以表示大多数的嵌入式实时系统,因此我们着重研究这类混合系统的验证算法．本文首先介绍了混合系统的模型—混合自动机,然后提出了一种针对线性混合系统的基于区域的先划分再遍历的半确定性验证方法．经实例检验,该方法能够有效地验证线性混合系统．最后将本文的方法同有关的其它算法进行了比较     

改进的八近邻区域边界标定自动机

在图像边界标定算法的基础上,通过化简自动机的状态迁移映射,减少了自动机在提取边界过程中的运算步骤和存储空间,提高了自动机效率.     

一种快速单模式准确匹配算法

引入连续跳跃查找文本的思想，提出了一种新的单模式精确匹配算法，其最优条件下的时间复杂度为O[n/(m 1)]，新算法的平均时间复杂度分析表明其具有优越的查找性能，对比实验结果显示，新算法的性能优于目前所见的同类算法，特别是在模式较短的情况下，优势更为明显，这一特点非常适合于自然语言文本的检索。     

从粒子角度研究164号元胞自动机的极限语言复杂性

通过定义164号元胞自动机的基本粒子,找到了粒子的逆演化规律,从而完全确定了其极限语言,并证明了164号元胞自动机的极限语言是正规的。结果表明:用有限自动机就可以接收该极限语言。