二元弱可逆有限自动机延迟步数的分解

本文考虑二元严格延迟τ步弱可逆有限自动机Ｍ的延迟步数的分解问题。首先证明如果Ｍ强连通且所有状态的延迟步数不小于τ－１，则Ｍ一定能分解为一个延迟０步弱可逆有限自动机和一个τ阶延迟元。然后证明如果Ｍ所有状态延迟步数均不小于ｍ，那么Ｍ可以分解为一个严格延τ－ｍ步弱可逆有限自动机和一个ｍ阶延迟元。最后考虑了Ｍ可分解为一个严格延迟τ－１步和一个严格延迟１步弱可逆有限自动机的条件。     

弱可逆有限自动机的分解

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

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

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

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

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

关于非线性有限自动机的弱可逆性

根据ＲＲ变换所得方程是否有解或至多一解可判定有限自动机Ｍ是否为弱逆或弱可逆。本文证明了这些充分条件与某类映射为满射或单射是等价的，从而减少了判定所需的工作量。本文还讨论了它们同时也是判定Ｍ为弱逆或弱可逆的必要条件的情形。     

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

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

弱可逆拟(r,r)阶存贮线性有限自动机的分解

通过对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机输出权的研究,得出对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机的任意一个状态,它的长r的输出权都是1;任何一个n元拟(r,r)阶存贮线性有限自动机M延迟r步弱可逆的充分必要条件是M都可以分解为一个延迟0步弱可逆有限自动机M0和一个延迟r步弱可逆拟(0,r)阶存贮线性有限自动机M1。     

环上线性有限自动机的可逆性的一些结果

本文证明了有单位元的有限交换环R上任何延迟t步(弱)可逆线性有限自动机皆有延迟t步线性(弱)逆的充分必要条件是环R满足条件: x(Ax=0→bx=0)→y(b=yA)我们还证明了对任何有单有限交换环R,R上输入、输出维数相同的延迟t步(弱)可逆线性有限自动机具有延迟t步线性(弱)逆.     

关于二元延迟3步前馈逆有限自动机的结构

前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题.对延迟步数≥3的前馈逆结构的刻划,则是一个长期的未解决问题.研究了二元延迟3步前馈逆有限自动机的结构.对于自治有限自动机M_a的状态图为圈的二元延迟3步弱可逆半输入存储有限自动机C(M_af ),给出了其长3极小输出权分别为1,2,8三种情形下结构的一种刻画.由于C(M_af )延迟3步弱可逆当且仅当它是延迟3步弱逆,因此,得到了二元延迟3步前馈逆有限自动机结构的一种部分刻画.     

基于广义有限自动机的图像压缩方法

提出一种用确定性的广义有限自动机(GFA)对灰度图像进行压缩编码的方法.对一幅输入的数字化灰度图像,检测其中的自相似性,该图像可以被表示成一个广义有限自动机.解码算法可以非常高效的由确定的广义有限自动机复原图像,且结果图像没有很明显的方块效应.这种方法与传统的有限自动机方法相比具有状态数较少、压缩比高、压缩效果较好的优点.     

汉字有穷自动机研究

为了更好地研究汉字信息输入系统，解决汉字输入的“瓶颈”问题，本文利用自动机理论，着眼于系统整体，建立了４种汉字信息输入处理系统的数学模型，引进了１－型，２－型，４－型自动机的概念，分别具体地给出了状态转移函数。     

正规文法与有限自动机的等价构造

在功能上,正规文法与有限自动机描述和识别语言是等价的,它们之间也存在等价构造算法,但这些构造算法有些复杂.对其算法进行了简化且给以了证明,并提出了一个从有限自动机构造等价左线性正规文法的算法,同时也进行了证明,最后给出了该算法的一个实例.     

由有穷自动机构造正则表达式的新算法

本文借助图论的理论,通过识别回路和不包含回路的由起始状态到终止状态的路径的方法,提出一种构造给定有穷自动机对应的正则表达式的新算法,并给出具体实例。     

一种PDA校表系统中的有限元区域划分算法

介绍了一个已经投入试运行的PDA校表系统.并针对该系统中任务划分效率低的现状,提出了一种新的区域划分算法.与传统的聚类划分算法相比,它具有时间复杂度低和灵活性高的优点.结合实际的可操作性引入了GPS全球定位技术,并将有限元分析和Bresenham画圆算法也加入到该算法中.最后通过VC实现了算法的仿真,仿真结果非常直观地证明了该算法的性能.统计和分析杭州计量所实际运行结果证明,加入该算法的PDA校表系统具有更高的效率.