有限状态自动机的并行确定化及过程分析

本文通过对并行环境下非确定有限自动机和确定有限自动机的等价性和转换进行研究,详细分析了非确定有限自动机到确定有限自动机的并行转换方法及算法,并以实例给出了其间并行转化的过程。

基于事件确定有限自动机的UML2.0序列图描述与验证

为了确保软件分析与设计阶段UML2.0序列图模型的可靠性,采用命题投影时序逻辑(propositional projection temporal logic,简称PPTL)模型检测方法对该模型进行分析和验证.提出了事件确定有限自动机(event deterministic finite automata,简称ETDFA),并使用该自动机为序列图建立形式化模型,通过给出的基于ETDFA的PPTL模型检测算法得到验证结果.该方法可以在基于Spin的PPTL模型检测器的支持下实现.实例结果表明,该方法可以验证序列图的性质并保证其可靠性.

确定有限自动机的矩阵形式

研究自动机的方法有状态转换函数、RTL、VHDL以及矩阵形式等方法.矩阵形式与其它方法相比能很好地完成对自动机状态转化过程的演算.自动机是描述集合之间某种关系,它的工作过程是一种逻辑推理过程.根据自动机的逻辑形式定义,结合矩阵方式,建立了自动机的矩阵逻辑运算方程;同时讨论了矩阵表示的有关性质.

确定有限自动机最小化算法的并行处理

对有限自动机模型最小化做了深入分析,提出了一种基于可区分状态表结构的并行最小化算法,以实例详细描述了算法并行处理过程并验证其算法的可行性。

基于确定有限状态自动机的改进多模式匹配算法研究

针对网络入侵检测系统的一般问题,在详细分析现存单模式与多模式匹配算法的基础上,将AC算法里的DFSA方法与单模式匹配算法BMH的思想相融合,以求取优化检测效率为目标,提出一种基于确定有限状态自动机的改进多模式匹配算法。该算法特别适合在大字符集文本串中查找小字符集模式串。将该改进多模式匹配算法应用到Snort入侵检测过程中,针对处理结果进行科学评价。通过实例的应用,验证了该改进算法的可行性和高效性。

确定有限自动机的逻辑形式定义

通过分析确定有限自动机状态转换函数的内在含义,引入有关的原子命题,得到确定有限自动机的逻辑形式定义并证明了状态转换函数表示与逻辑表示之间的等价性.

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

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

确定型格值有限自动机的最小化

给出了确定型格值有限自动机的定义,并同时给出了有效终止状态和可达到状态的定义。指出了求取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最小化算法的一个容易实现的构造型描述和相应示例。

P2P网络中基于非确定有限自动机的XML数据流过滤

将自动机方法对XML数据的过滤延伸到P2P网络中,依据在本地XML系统YFilter中构造非确定有限自动机(NFA)的思想,采用Chord环建立起分布式的NFA对于peer节点中的XML数据的查询过滤系统,并基于递归法执行查询过滤,在不同的peer节点上得到满足查询条件的数据集合。通过实验验证了当查询的数量和网络大小发生变化时分布式NFA的方法的执行性能。结果表明:本文方法可在不同的过滤场景中处理百万数量级的XPath查询,具有良好的网络流量和过滤延迟。

基于非确定型有限状态自动机的基因逻辑网络模型

阐述近年来基因网络逻辑行为的新模型———有限状态自动机模型,针对该模型的局限性,本文提出了改进,建立非确定型自动机模型,以描述网络行为的非确定型,适应基因网络的异常表达需要.

基于确定有限自动机实现MES的流程控制应用研究

简述确定有限自动机的基本概念,提出了应用确定有限自动机在MES中实现流程控制的思想。通过XML来构造确定有限自动机,并给出实现方法和实例。

基于信息系统的确定有限自动机最小化算法

目前,确定有限自动机(DFA)最小化问题多侧重于理论研究,尚无太多便于实现的算法,为此,对确定有限自动机最小化方法进行了研究,提出将DFA转换为信息系统,基于等价类划分方法简化信息系统,再将简化的信息系统转换为最小化DFA;针对上述处理过程,给出一个基于分治思想的DFA最小化算法,在平均情况下该算法的时间复杂度为O(n log n),空间复杂度为O(n)。最后通过实例验证了所提算法的正确性。

确定型模糊多重集有限自动机的极小化

主要研究确定型模糊多重集有限自动机的状态极小化问题。给出了模糊多重集有限自动机的同余和同态概念,并利用同余和同态关系研究了确定型模糊多重集有限自动机的极小化问题。进一步从确定型模糊多重集有限自动机自身出发,构造出极小模糊多重集有限自动机,并给出了极小化的算法。

确定有限自动机到正则表达式转换的并行处理

有限自动机和正则表达式都是描述语言重要方法,二者的转换具有重要意义.针对确定有限自动机模型做了深入的分析,在并行环境,提出了一种确定有限自动机到正则表达式的并行转换算法,并以实例详细描述了算法并行处理过程并验证了其算法的可行性.

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

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

确定的有限元胞自动机的两个性质

提出了确定的有限元胞自动机的概念,通过对演化构形的惟一性特征的分析,证明了确定的有限元胞自动机的状态演化最终处于稳定状态或者循环状态;具有相同演化结果的状态构成等价关系两个性质.利用初等元胞自动机对其进行了验证,在此基础上,对元胞自动机的四个普遍性分类进行了三个层次的探讨.

基于确定性有限细胞自动机的开采沉陷模拟方法

针对矿区保护应用中的岩体变形模拟问题,提出了一种基于确定性有限细胞自动机的开采沉陷模拟方法。该方法采用自动机理论描述岩体内部和表面的沉降分布,能够以相对简单的方法获取沉降槽剖面,且该剖面与大地测量法观测到的剖面一致。在现有细胞自动机解决方案的基础上,通过在模型的第二个细胞网格中增加一个沉降网格的副本,提出了基于传播函数概念的水平位移模拟优化方法。该方法可同时对沉降和岩体模型内部和表面上的水平位移进行模拟。此外,确定了用于描述最大水平位移与最大沉降的比值关系式。对煤层抽取开采引起的300m×800m岩体进行了变形分布模拟。结果显示,提出模型的沉降和水平位移结果与几何积分理论一致,验证了其可行性。

用确定性的有限自动机进行图像压缩编码

本文提出用确定性的有限自动机（ＤＦＡ）进行图像压缩编码的方法。对一幅输入的数字化灰度图像，检测其中的自相似性，该图像可被表示成一个确定的有限自动机（ＤＰＡ）。ＤＦＡ的尺寸小于原图像。解码算法可以非常高效地由ＤＦＡ复原图像。

确定的有限自动机(DFA)化简方法改进

文章通过对DFA状态最小化算法的分析,指出了关于空集Φ的一个不等价问题,并讨论了问题的成因及解决方法。