基于LTL Tableau的自动机构造

基于线性时序逻辑(LTL)的模型检验是使用较为广泛的技术。该种模型检验最终归结为有穷自动机的判空问题,其复杂性来源于性质和模型乘积自动机的状态空间膨胀。作者提出了一种构造迟滞交换Co-Büchi自动机(Stuffer Alternating Co-Büchi)的具有线性复杂度的方法,该方法能够降低最终乘积自动机的空间复杂度。     

基于稠密时间的实时系统模型检测的一个应用

模型检测是一种用于并发系统性质验证的算法技术。实际生活中广泛应用的是带有时间约束的并发系统即实时系统，现在模型检测技术越来越被广泛地应用到这类系统的性质验证当中。这类系统通常用时间自动机来表示，而它们的性质则用时序逻辑公式表示。本文简要介绍了时间自动机和时序逻辑TCTL，并着重说明了如何进行基于稠密时间的实时系统的模型检测，最后给出了一个应用实例。     

基于时态逻辑的形式化联邦校核方法

提出了一种基于时态逻辑的形式化联邦校核方法，采用时态逻辑公式描述联邦各成员的行为逻辑关系，推导出与该时态逻辑公式对应的有限自动机模型，即规范自动机。同时，建立联邦全局行为的状态转移图，即实现自动机，通过检验规范自动机所接受的语言是否包含实现自动机所接受的语言来判断联邦运行时各成员的状态变化是否满足规范要求，达到校核联邦的目的。该方法可用来校核联邦及其成员的交互设计和逻辑行为运行的正确性和逻辑性，具有理论意义和应用价值。     

区间时序逻辑的模型检查

为了检验标注有限状态自动机描述的系统是否满足某个区间时序逻辑公式刻画的性质,定义了一套转换规则．利用这些规则,可以构造一个chop-自动机,该自动机接受的语言恰是所有满足这个区间时序逻辑公式的模型的集合．同时,定义了一套转换规则把一个chop-自动机转换为一个标注有限状态自动机,使得它们接受相同的原子命题序列集．这样,区间时序逻辑的模型检查问题就等价地转换成了很容易解决的两个标注有限状态自动机的语言包含问题．     

基于Spin的地铁门控制系统建模与验证

针对地铁门控制系统(MDCS)安全问题,提出一种MDCS检测方法。通过分析MDCS的控制逻辑,使用Promela建立了基于Spin的MDCS系统模型,将MDCS中的地铁控制系统、地铁门控制系统及屏蔽门控制系统抽象为三个进程,并用线性时态逻辑公式描述待验证性质,运行Spin后即可判断MDCS是否存在安全隐患。实验结果表明,该检测方法可有效验证MDCS的安全性。     

多速率混合系统的模型检查

研究了初始化的多速率混合系统的模型检查问题,即检验初始化的多速率自动机是否满足某个混合区间时序逻辑公式描述的性质．首先定义了一套转换规则把混合区间时序逻辑公式转化为区间时序逻辑公式．接着定义了初始化的多速率自动机状态空间上的等价关系及其对应的域自动机,并且通过构造域自动机对应的标注有限状态自动机,把初始化的多速率混合系统的模型检查问题等价地转换成了可解的区间时序逻辑的模型检查问题．利用区间时序逻辑的模型检查算法加上上述的转换规则,就可以解决初始化的多速率混合系统的模型检查问题．     

基于时间自动机网的C3I系统建模和实时性验证

针对目前缺乏描述和分析C3I系统的理论基础,提出了基于时间自动机理论的C3I系统的数学模型.建立了C3I系统中各个子系统的时间自动机模型,子系统之间通过通道进行通讯,通过时间自动机网把C3I系统构建为多个并行的时间自动机的网络模型.提出基于计算树逻辑CTL的C3I系统的实时性表达方法,详细描述使用模型检测工具Uppaal对C3I系统建模和所建模型的实时性验证的方法.实验结果证明,基于时间自动机的C3I系统的建模与模型检测方法是有效的,为C3I系统行为的分析、验证提供理论基础.与经典算法相比,该方法提高了对C3I系统建模和分析的效率.     

基于自动机的并发程序符号可达分析

为了缓解模型检测并发程序中出现的状态爆炸问题,将并发程序建模成异步动态下推网络,同时将异步动态下推网络转化为异步下推网络,在异步下推网络下提出一种基于自动机的符号可达算法。该算法能避免精确搜索每一个状态空间,有效地缓解了状态爆炸。     

基于自动机理论的密码匹配方法

针对用户安全登录问题,提出了一种基于自动机的密码匹配模型.首先,对于用户任意输入的密码进行同态映射加密; 其次,构造出可接受加密密码的自动机——状态数目可变自动机(VNS - DFA),该自动机不仅能够匹配加密密码,同时还可以输出加密密码的同态原像以及匹配成功的次数; 最后,在状态数目可变的自动机上对用户输入的密码进行实验验证表明,用户建立的密码经过同态映射后可全部被该自动机接受,且该自动机的时间复杂度优于传统的DFA以及改进的DFA.     

基于元胞自动机的移动机器人路径规划

为解决移动机器人全局最优路径规划存在的问题,提出了一种基于元胞自动机的路径规划算法。建立了移动机器人活动空间的环境模型,将移动机器人的起点、终点、障碍物及自由通路定义为一组离散的元胞,设计了元胞状态的演化规则,并且根据演化后的元胞状态确定了最优路径的搜索方法,并通过仿真实验验证了该算法在简单环境和复杂环境下都能够有效的进行路径规划,并且具有算法简单、速度快、效率高等特点。     

有限自动机与多路自动机的关系

简单介绍了多路自动机的定义，分析了多种自动机和有限自动机的关系，包括确定的有限自动机和非确定的有限自动机，并且给出了例子，本文的结论推广了计算学习理论中可有效学习的类的范围。     

多态自动机在字符串搜索及统计时的应用

多态自动机较之有穷自动机有更强的计算功能和对算法的描述功能,所以在计算理论和学习理论中有相当地位.本文首先简要地介绍了多态自动机,然后利用多态自动机的计算功能给出了一种搜索算法,此算法可以完成字符串的搜索和统计功能.文章对此算法的复杂度进行了分析,该算法的复杂度是多项式的,并且对此算法添加一些辅助部分也可以完成搜索网络资源的功能.此算法在计算机上也很容易实现.     

一种基于元胞自动机的安全多重图像水印算法

提出一种多重图像水印算法,利用元胞自动机和元胞自动机变换丰富复杂的性质增强水印安全．将图像分割成不重叠的子块,由混沌序号序列决定一个子块中将嵌入哪个图像水印,通过水印私钥对水印进行置乱加密和对子块进行二维元胞自动机变换,然后在低频系数中量化嵌入加密水印．实验结果表明,提出的算法有很好的安全性、不可见性和鲁棒性,多个水印的嵌入和提取互不干扰．     

构造型的D2FA生成算法

Delayed input DFA (D²FA)中引入默认边来对确定状态机(DFA)进行状态转移精简. 为了提高D²FA生成算法的效率,分析了对正则表达式X得到的DFA(^∧X)与DFA(X)间的相关性,提出一种从DFA(^∧X)到D²FA(X)的构造型算法. 该算法将DFA(X)中的状态用DFA(^∧X)中的状态序列进行表示,从而基于状态序列进行默认边的选择,而不需要生成实际的DFA(X). 理论分析和实验结果表明,该算法降低了构造D²FA的算法复杂度,同时仍能保证进行模式匹配时的解析时间下限,以及对DFA的状态转移精简能力.     

基于元胞自动机变换的重复水印算法

为了在满足水印不可见性和鲁棒性的同时,充分保障水印的安全性,提出了一种元胞自动机域的水印重复嵌入算法.利用元胞自动机的复杂多变的动力学特征,设计一个长的密钥矢量,先对水印进行元胞自动机加密,再对图像子块进行元胞自动机变换,利用纹理掩蔽特征将加密水印重复地嵌入图像子块中,水印检测无需原始图像.实验结果表明提出的算法有很好的鲁棒性、安全性和不可见性.     

基于可逆元胞自动机的图像加密算法

提出一种基于一维可逆元胞自动机（RCA）的新的图像加密算法,算法中可逆元胞自动机（RCA）规则和随机数据的应用使得图像具有更高安全性。可逆元胞自动机（RCA）加密算法将已知灰度图像变为二值图像,然后将其数据重新排列成一0-1序列,应用可逆元胞自动机（RCA）规则实现图像加密。灰度图像加密的仿真结果表明所提出的算法满足混合特性和扩散特性,一般的解密算法根本不可能对这种加密图像解密。     

二维异步元胞自动机计算机病毒传播

基于二维异步元胞自动机研究了计算机病毒传播,提出带有时延的计算机病毒传播模型.该模型能够有效克服以往基于同步元胞自动机的病毒传播模型难以考虑时延的问题,并且使研究者能够方便地通过调整参数达到模拟在不同拥塞程度网络中的病毒传播目的.研究结果表明,时延会使病毒传播的过程产生滞后现象,但不会改变其总体趋势.     

枝晶生长的元胞自动机模拟

元胞自动机是复杂体系的一种理想化模型，特别适合于处理那些难以用数学定量描述的复杂动态体系问题如材料的组织结构演变问题，尤其适合于计算机模拟实施。本文使用元胞自动机模型根据最基本的物理学原理和温度场模拟计算耦合，得到了枝晶的生长结构。由于本模型没有引用微观研究中关于枝晶的特殊理论，因此可以将这种结果看做是通用模型的一种特殊情况。这说明：元胞自动机模型除了能够完成对于微观结构的模拟以外，还特别适合于基机理的研究。     

基于细胞自动机的火焰生成算法

通过细胞自动机方法描述粒子的运动,从而体现气流场的整体扩散特性是一种可变形气流场的仿真方法之一,本文首先将细胞自动机模型引入到火焰现象的仿真中,提出了基于细胞自动机的火焰生成算法,并给出了相应的仿真结果,然后将该算法推广到小块烟雾的生成仿真中,取得了较好的仿真效果。