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

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

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

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

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

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

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

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

数字图像的加权有限自动机表示

传统的图像压缩技术JPEG方法采用小波变换、离散余弦变换等方法进行,文中所使用的方法是与JPEG技术完全不同的方法[1],在用字母表上的字表示像素地址的基础上把每个像素的地址映射为一实数,则可以得到多分辨率灰度图像的加权有限自动机表示方法,该方法的有效应用将使图像压缩[1~7]的比例得以提高.     

有限自动机在密码技术中的应用探讨

通过对流密码体制一般原理的分析,提出了一个基于DFA的流密码模型.依据该模型,可以构造一类初始密钥长度可变、加密/解密简单快捷、强度较高的流密码,以满足不同的应用需求.     

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

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

有限自动机的半环方法

文章利用半环方法来讨论有限自动机.首先,利用线性代数基础给出半环上有限自动机的概念;然后,证明了半环上的有限自动机与不确定的有限状态自动机识别语言的一致性.从数学的角度看该方法使得有限自动机的讨论更加简洁.     

基于粗糙集理论的有限自动机最小化方法改进

有限自动机放在粗糙集的范畴中来研究,它的各个状态对应粗糙集论域中的每个对象,每个输入符号为一个等价关系。从粗糙集的角度,利用对论域进行知识划分的方法,每次产生新的等价类,直到每个等价类都不能划分为止,从而得到最小化的有限自动机。与已有的研究方法不同,该方法以粗糙集理论为工具,为有限自动机最小化方法研究提供了新的思路。     

一种基于有限运行时间自动机的基因网络模型

阐述了最近几年来国外基因网络系统逻辑行为的研究新进展——基于有限状态自动机模型的方法,针对该方法的局限性,提出了一种基于有限运行时间自动机的基因网络模型,以描述网络行为的时间约束.     

概率有限自动机的交换性

提出了一类概率有限自动机并给出其交换的概念,得到了此类自动机交换的一些刻画,定义了两个概率有限自动机的和与积,并且得到了和自动机、积自动机交换的充要条件。     

有限自动机在模式匹配中的应用与研究

有限自动机匹配算法是多模式匹配中的重要算法.反向有限自动机在一定的条件下能压缩自动机的规模,从而提高模式匹配的速度.将反向有限自动机算法与BM算法相结合,利用当前获取信息进一步增大匹配过程中的跳跃距离,可进一步提高模式匹配的速度.     

一种非确定型有穷自动机的极小化方法

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言．确定型有穷状态自动机（DFA）极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机．而非确定型有穷状态自动机（NFA）极小化问题尚未找到有效算法．尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加．从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机．     

线性有限自动机零状态的作用

通过零状态研究了线性有限自动机的一些性质,得到了线性有限自动机弱可逆的一些结果,并给出了最小线性子有限自动机的描述,最后给出了算法实现。     

有限群自动机的若干环论与图论性质

通过研究有限群自动机的关联环和导图来刻画有限群自动机,给出了有限群自动机不可约和不可分的一些判别法则。     

有限自动机积的初(末)态试验序列、UIO序列和同步序列

主要对积运算后有限自动机的初(末)态试验序列、U IO序列和同步序列进行了讨论,给出了积运算后的有限自动机与积运算前有限自动机的初(末)态试验序列、U IO序列和同步序列的联系,并给出了极小有限自动机的初态试验序列与U IO序列间的联系。     

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

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