线性有限自动机的同步序列及其生成算法

文章主要讨论了线性有限自动机的同步序列,得到了线性有限自动机有同步序列的充要条件,还讨论了一类输入存贮线性有限自动机及可等价嵌入输入存贮线性有限自动机的极小线性有限自动机的同步序列。最后给出了判断线性有限自动机有无同步序列以及求线性有限自动机(最短)同步序列的一些算法。     

有限自动机可识别语言的基数

利用有向图的邻接矩阵研究有限自动机的可识别语言的基数问题。通过建立有限自动机的可识别语言与其有向图中从初始结点（有限自动机的初始状态）到终止结点（有限自动机的终止状态）的路的一一对应关系,利用邻接矩阵给出了有限自动机的可识别语言的基数公式,研究了两个自动机不等价的充分条件。     

弱可逆有限自动机的分解

有限自动机公开钥密码体制的提出进一步激励了有限自动机可逆性的研究．在有限自动机公开钥密码体制中首次提出了自动机化合的概念．易知,两个弱可逆有限自动机的化合仍然是一个弱可逆有限自动机并且它的延迟步数不大于前两个有限自动机延迟步数之和．然而,另一方面,如何将一个弱可逆有限自动机分解为两个弱可逆有限自动机的化合却是一个非常困难的问题．该文主要考虑了一类n元严格延迟τ步弱可逆有限自动机M的延迟步数的分解问题．给出了一类特殊的n元弱可逆有限自动机分解的条件和结果．首先证明了如果对M中的每个状态s有T（s,τ）枝等,则M可分解为τ个延迟1步弱可逆有限自动机的化合．然后证明了M可分解为一个τ—m步弱可逆有限自动机和m阶延迟元的充要条件是对M中的每个状态s有T（s,m）枝等．     

关于延迟τ步(可)逆有限自动机结构的一些性质

本文讨论延迟τ步可逆有限自动机M的所有延迟τ步逆有限自动机组成的类的结构问题,和以给定有限自动机M′为延迟′步逆的所有有限自动机组成的类的结构问题。对于输入输出字母表大小相同的情形,给出了构造M的通用延迟τ步逆有限自动机和以M′为延迟τ步逆的通用有限自动机的方法,并证明了在等价的意义下前述两类有限自动机都构成一个分配有界格。     

带空移动的加权有限自动机量化等价及其转换

在经典的有限自动机理论中,带空移动的有限自动机与不带空移动的有限自动机是等价的。取值于实数的加权有限自动机是自动机的一种推广模型,它给经典自动机的每个转换赋一个取值于实数的权值,这些权值表示执行转换的代价。为了研究带空移动的加权有限自动机与不带空移动的加权有限自动机是否具有等价性这一问题,提出量化等价的概念,并研究如何将一个带空移动的加权有限自动机转换为一个与之量化等价的不带空移动的加权有限自动机。研究结果表明:这两者是量化等价的。     

扰动值模糊有限自动机及其语言*

引入扰动值模糊有限自动机及其语言的概念,讨论扰动值模糊有限自动机的状态转移函数的扩张问题,证明3类确定型扰动值模糊有限自动机、非确定型扰动值模糊有限自动机相互等价性,研究扰动值模糊有限自动机的语言关于正则运算的封闭性.     

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

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

有限自动机在复合事件检测中的应用

针对早期系统只提供原子事件的检测机制,不能检测由原子事件组成的复合事件的问题,提出了用有限自动机来检测复合事件的方法.说明了复合事件的组成和表达式,利用自动机原理对复合事件的检测模式进行了分析,给出了复合事件检测的具体过程:从事件表达式到不确定的有限自动机,从不确定的有限自动机到最小化确定的有限自动机,再用程序实现了确定的有限自动机.实例表明,自动机模型是检测复合事件的一种有效实现方式.     

格值有限自动机等价判定算法

引入了完备L-Fuzzy矩阵的概念,给出了基于格半群的模糊有限自动机的形式化定义,即完备格值有限自动机,研究了它的主要性质;给出了完备格值有限自动机的行为矩阵,从行为矩阵出发,给出了自动机状态等价和自动机等价的定义。最后,得到了该类自动机等价的判定算法。     

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

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

分解弱可逆有限自动机的两个结果

研究弱可逆有限自动机的分解可以为分析有限自动机公开钥密码体制的安全性提供一种重要途径．从输出权的角度研究了n元延迟τ步弱可逆有限自动机M的分解问题,首先证明了其可分解为一个延迟0步弱可逆有限自动机和一个τ阶延迟元当且仅当M的所有状态的长τ输出权为1．其次,在获得一类不可分解出延迟元的弱可逆有限自动机的基础上,构造出一个反例,否定回答了鲍丰在1993年提出的一个公开问题．同时给出了二元严格延迟τ步强连通弱可逆有限自动机可分解为一个严格延迟τ—1步弱可逆有限自动机和一个严格延迟1步弱可逆有限自动机的一个充分条件．     

概率有限自动机的积和分解

给出几种概率有限自动机的积,讨论了他们之间的相互关系,并在文献[1]的基础上利用这些积给出匀概率有限自动机的分解,证明了一个匀概率有限自动机可以分解为一个随机编码源、一个伯努利过程和一些确定有限自动机的串联积。     

关于弱可逆有限自动机延迟步数分解的两个结果

本文证明存在(任意元)延迟2步弱可逆有限自动机不等价于任何两个延迟1步弱可逆有限自动机的化合的任何子自动机。因而说明了不是对所有的弱可逆有限自动机,延迟步数都是可分解的,但对所有状态的延迟步数均为2的二元延迟2步弱可逆有限自动机,则分解是可行的。     

Mizumoto格值有限自动机及其最小化

提出取值为格半群的Mizumoto格值有限自动机的概念,得到基于模糊字符串的Mizumoto格值有限自动机的扩张模型,并详细讨论了其性质。同时建立了扩张Mizumoto格值有限自动机与标准扩张Mizumoto格值有限自动机的等价性,在此基础上给出了其最小化算法。     

循环自动机的等价性

主要讨论了两个循环有限自动机的等价性与循环有限自动机的生成子之间的关系,在某些条件下给出了两个循环有限自动机等价的充分必要条件。     

状态自动机矩阵模型的代数性质

有限自动机理论是控制理论、对象程序测试、神经网络、保密学等众多学科领域的重要研究工具犤1～4犦,探索有限自动机理论研究的新思路具有重要学术意义。文章在有限自动机矩阵模型表示方法基础上,采用矩阵理论和布尔代数为工具,针对无输出情形的特殊有限自动机(状态自动机),研究给出了基本代数性质及相应的物理意义。在采用新的数学方法进行有限自动机理论研究方面作了有益的探索,采用这种方法有利于算法设计和计算机自动处理。     

弱可逆线性有限自动机的一种分解

讨论有限自动机的分解有助于分析弱可逆有限自动机的结构和求解弱逆.首先证明了弱同构的弱可逆有限自动机具有相似的分解形式;接着考虑了一类特殊的弱可逆线性有限自动机的分解,从状态输出权的角度刻画了该分解存在的一个充分条件;然后把这种分解形式推广到了一般的弱可逆线性有限自动机上,即:延迟τ步弱可逆线性有限自动机分解成延迟0步弱可逆有限自动机和一种特殊的有限自动机MD,并得到了分解存在的充要条件;最后,用输出序列的代数性质来刻画其中的充分条件,并把它转化成了一个矩阵的秩的计算.这种分解形式并不局限于n元弱可逆有限自动机,而且分解条件也比较简单,仅与输出序列的性质有关.     

线性有限自动机的UIO序列及其生成算法

对线性有限自动机的UIO序列进行了讨论,得到了线性有限自动机的任意一状态有某一长度的UIO序列的充要条件,得到了线性有限自动机的(所有)状态有UIO序列的的充要条件,还给出了有UIO序列的线性有限自动机的状态的最短UIO序列长度的上界,最后给出了判断线性有限自动机的所有状态有无UIO序列以及有求其UIO序列的两个算法.     

一种新的基于有限自动机的XML过滤方法

设计实现了一种新的基于有限自动机的XML过滤方法，这种方法和以往基于有限自动机方法（不确定的有限自动机和确定的有限自动机）的不同在于它首先使用XML Schcma把带“*,//”的路径表达式简化，然后把生成的DFAs合并成一个大的DFA，这个DFA充当过滤引擎。     

格值有限状态自动机的半群

提出了格值有限状态自动机的定义,给出了格值有限状态自动机的两种同余关系,研究了格值有限状态自动机的半群的若干性质,最后给出了两种有限半群E(A)和E(A)的关系。