基于参数设定的正则表达式匹配算法

为了解决现有正则表达式匹配算法在时间复杂度与空间复杂之间的平衡问题,提出一种通过参数动态设定的确定有限自动机(dynamic parameters DFA,DPDFA)的正则表达式匹配算法.首先对现有典型正则表达式匹配算法进行性能分析,指出它们在内存占用、规则匹配时间、可扩展性方面存在的不足.然后给出DPDFA算法的设计思想:先设定组合后状态数上限,分离组合表达式之间的互斥性,从而降低内存占用;再设定状态数增长率参数,将表达式进行切片,隔离状态数膨胀片段,降低它们之间的歧义匹配,从而节约匹配时间.试验结果表明,DPDFA算法在时间复杂度方面优于D2FA约23%,在空间复杂度方面优于m DFA约43%,在拓展性方面优于XFA近260%,整体匹配效率方面也优于其他算法.     

基于元胞自动机原理的微观交通仿真模型

描述了一种对高速路上的交通流仿真和预测的模型.该模型应用了元胞自动机原理对复杂的交通行为进行建模.这种基于元胞自动机的方法是将模拟的道路量离散为均匀的格子,时间也采用离散量,并采用有限的数字集.同时,在每个时间步长,每个格子通过车辆跟新算法来变换状态,车辆根据自定义的规则确定移动格子的数量.该方法使得在计算机上进行仿真运算更为可行.同时建立了跟车模型、车道变换的超车模型,并根据流程对新建的VP算法绘出时空图.提出了一个设想:将具备自学习的神经网络和仿真系统相结合,再根据安装在高速路上的传感器所获得的统计数据,系统能对几分钟以后的交通状态进行预测.     

城市交通优化中基于对偶算法的元胞自动机

对基于换乘时间的城市交通优化问题进行了数学模型分析,根据模型的对偶原理得到了问题的对偶算法,设计了元胞自动机.在元胞自动机中,以每一个站点作为一个元胞,根据是否获得最佳乘车线路将元胞分为2种状态,将中心元胞的下一个站点作为其邻居,演化规则只作用于未获得最佳乘车线路的元胞,并只需通过对演化时间与元胞的相应权值的比较来确定状态的改变.基于对偶算法元胞自动机具有元胞状态少、邻居关系简单、演化规则简便和计算量少的特点.仿真实验说明了基于对偶算法元胞自动机的有效性和可行性.     

基于有穷自动机的自然语言状态转换

针对Robocup自主机器人比赛中,机器人进攻和防守状态、动作转换延迟问题,采用一种基于有穷自动机模型的自然语言状态转换方法,把机器人、环境等自然语言信息抽象成形式化的符号和状态,并转化为有穷自动机输入符号.通过设定状态转移函数、字母表规则、无差别地完成各种状态转换过程.研究结果表明:该方法能有效地完成自然语言状态下的机器人状态、动作间的转换,具有较好的实时性和可靠性.     

格值自动机与语言

引入了格值自动机及其语言的概念,给出了格值自动机的状态转移函数可扩充的充分必要条件,证明了确定型格值自动机与格值自动机等价的充分必要条件,研究了格值自动机的语言关于正则运算的封闭性及其条件.所得结论表明了格值自动机及其语言的特性与取值格代数性质的紧密联系.     

基于元胞自动机的单源点最短路求解算法

针对图的单源点最短路问题,提出一种改进的基于元胞自动机模型的求解算法并分析了其算法复杂度.该算法定义了一个元胞自动机模型,通过元胞空间上元胞状态的变化,能够获得某设定结点到其他结点的最短路.在实验阶段,分别用经典Dijkstra算法和提出的算法对随机生成的不完全无向图进行分析.结果表明,相比于经典的Dijkstra算法,该算法不但能够获得与之相同的仿真结果,并且具有规则简单、易于实现、效率高等特点,具有明显的优越性.     

基于元胞自动机的拓扑排序算法

目的 利用元胞自动机的特性,找到一种新的拓扑排序算法.方法 将AOV网构造成一个元胞自动机模型,采用经过改造的邻接链表作为元胞的数据结构,并在其中引入随机编号项,所有元胞依据随机编号顺序地遵守演化规则进行演化,实现拓扑排序.结果 利用元胞自动机的时空局部规则和并行计算特性,设计并验证了拓扑排序算法.结论 与传统算法相比本算法在时间、空间复杂性上都有较大改善,并且在应用元胞自动机理论解决图的问题方面有所贡献.     

格值直觉模糊有限自动机的直积与覆盖

给出了格值直觉模糊有限自动机,格值直觉模糊有限自动机的全直积、限制直积以及覆盖的定义,提出了格值直觉模糊有限自动机的状态转移函数可扩充的充要条件,研究了格值直觉模糊有限自动机在全直积和限制直积情形下的转移函数性质,讨论了格值直觉模糊有限自动机的全直积和限制直积的覆盖关系,得到了一些乘积自动机覆盖关系的传递性质,为进一步研究格值直觉模糊有限自动机奠定了基础.     

基于颜色复杂度和结构张量的恰可察觉失真模型

图像的恰可察觉失真(just noticeable distortion, JND)阈值是指人眼能够察觉的最小失真, 通常被用于去除图像/视频压缩中的视觉冗余. 针对 JND 模型对颜色和结构特征利用不充分的问题, 提出了一种基于颜色复杂度和结构张量的 JND 模型. 首先, 计算图像的颜色复杂度, 将其转换为与视觉敏感度相关的权值, 和对比掩蔽模型结合以提升模型的准确性; 然后, 利用结构张量对局部特征进行表示, 建立基于局部结构特征的调制因子, 估计结构不规则区域的视觉冗余程度; 最后, 将基于颜色复杂度的 JND 模型和基于结构张量的调制因子结合, 建立基于颜色复杂度和结构张量的 JND(complexity structure tensor based JND, CSJND)模型. 实验结果表明, 相比于已有的模型, 该模型在主观感知质量相同的前提下, 能使 PSNR 值明显降低; 该模型更加符合人眼的视觉特性, 能更准确地估计出 JND 阈值.     

基于细胞自动机模型的自适应生产调度问题

用细胞自动机来建模生产调度问题,通过把调度序列分散到规则网络中,相邻细胞之间相互影响,可以避免细胞的早熟.当进化过程出现扰动时,可以通过控制器自行修改相关参数加以响应,实现自适应调度.介绍了细胞自动机的建模原理,并结合遗传算法的运算因子和进化规则,讨论了基于遗传细胞自动机模型的自适应生产调度方法,用算法的仿真结果验证了模型的有效性和适应性.     

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

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

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

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

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

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

基于混合策略的单模式匹配算法

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.     

基于TCP状态有限自动机的入侵检测研究

入侵检测是一种重要的信息安全防御技术.基于TCP状态有限自动机的入侵检测是一种异常检测方法,它能发现违背TCP状态有限自动机的行为.描述了TCP协议中正常的连接状态转换关系,构造了TCP状态有限自动杌,给出了基于TCP状态有限自动机的入侵检测实现.     

构件化嵌入式软件设计的能耗性质分析与验证

从嵌入式软件设计模型层对构件化实时嵌入式软件系统中能耗相关性质进行研究,包括:扩展了实时接口自动机在能耗语义方面的描述能力,通过引入状态能量消耗率,建立了能耗接口自动机形式化模型以及自动机网络,用以建模嵌入式软件设计阶段系统构件及其构件组合的能耗行为特征;对能耗接口自动机网络的状态空间进行了形式化分析,构造了相应的可兼容整型空间的可达图,并在此基础上给出了最小能耗计算和最大能耗验证的算法.     

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

Active XML Document Rewriting Based on Tree Automata Theory

The problem of document rewriting is a fundamental problem in active XML（AXML） data exchange and usually has a higher complexity. Prior work was focused on string automaton theory. This paper tries to solve it by using tree automaton. More precisely, the paper firstly defines a new tree automaton, active XML tree automaton （AXTA）, which can efficiently represent the set of AXML documents produced by an AXML document or AXML document schema. And then, an algorithm for constructing AXTA automaton is also proposed. Finally, a polynomial time（PTIME） determining algorithm for AXML document rewriting is presented based on AXTA automaton.     

一种改进的Nagel-Schreckenberg交通流模型

在Nagel-Schreckenberg交通流模型基础上,通过局域密度及当前车速两个参数来实现对减速概率的控制,同时考虑规则的不同运作次序可能会对系统的演化产生非凡的影响,提出一个改进的一维元胞自动机交通流模型,并进行数值模拟,将模拟结果与实测数据进行比较.结果显示,适当调节系统的相关参数,可以实现畅行相→低速同步相→宽幅运动阻塞相的转变.从系统中可以发现同步流和相分离的存在,弥补了Nagel-Schreckenberg交通流模型无法实现大尺度同步流的缺陷.