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

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

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

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

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

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

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

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

线性有限自动机输入输出集的性质

证明了两个线性有限自动机化合而得到的自动机具有输入输出均匀的性质,建立了由两个延迟1步弱可逆线性有限自动化合后得到的自动机的输入集个数与化合前自动机输入集个数的等式关系。     

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

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

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

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

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

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

拟（h,k）存贮有限自动机的可逆性

主要研究拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱可逆性,以及它的弱逆,得到了拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱可逆的充分必要条件,并且通过所得结果可以比较简便地构造出延迟k步与k＋1步弱可逆拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱逆。     

拟(h,k)存贮有限自动机的可逆性

主要研究拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆性,以及它的弱逆,得到了拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆的充分必要条件,并且通过所得结果可以比较简便地构造出延迟k步与k+1步弱可逆拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱逆.     

Decomposing a kind of weakly invertible finite automata with delay 2

Some properties of a finite automaton composed of two weakly invertible finite automata with delay 1 are given,where each of those two automata has the output set of each state with the same size.And for a weakly invertible finite automaton M with delay 2 satisfying the properties mentioned in this paper,two weakly invertible finite automata with delay 1 are constructed such that M is equivalent to a sub-finite-automaton of the composition of those two.So a method to decompose this a kind of weakly invertible finite automate with delay 2 is presented.     

Representations of Regular Ideals in Finite Automata

Regular ideals of a free monoid are shown to be characterized by weak (noninitial) representations in finite automata. The class of kernel ideals is also shown to be invariant under the action of several automata functors and to be equal to the class of zero ideals.     

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

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

基于模板有限自动机的正则表达式匹配算法

采用规则分组的办法解决DFA状态爆炸问题,随着规则数目的增加,空间压缩效率大大降低。针对此问题,提出了模板有限自动机分组算法,基于规则模板对规则集进行分组,各分组分别构建匹配引擎。同时,根据实际规则数目和系统结构对规则子集的数目改变,达到更好的匹配效率。理论分析和实验表明,与传统分组算法相比,在存储空间压缩相当情况下,分组数目大大减少;与其他典型的DFA改进算法相比,预处理时间和存储空间有数量级别的缩减,且匹配速率没有明显降低。