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

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

弱可逆有限自动机的分解

有限自动机公开钥密码体制的提出进一步激励了有限自动机可逆性的研究．在有限自动机公开钥密码体制中首次提出了自动机化合的概念．易知,两个弱可逆有限自动机的化合仍然是一个弱可逆有限自动机并且它的延迟步数不大于前两个有限自动机延迟步数之和．然而,另一方面,如何将一个弱可逆有限自动机分解为两个弱可逆有限自动机的化合却是一个非常困难的问题．该文主要考虑了一类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步弱可逆有限自 动机的一个充分条件.     

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

本文证明存在(任意元)延迟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。     

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

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

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

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

有限布尔代数上的线性自动机

自动机理论是计算机科学理论的重要组成部分。论文研究了布尔代数上的线性自动机,证明了任意一个线性有限自动机是函数布尔代数上的一个内动机。定出了有限布尔代数上的一类可逆线性内动机,给出并证明了有限布尔代数上内动机图型为下向森林的充分必要条件,给出了树型内动机中每一层节点数的计算公式,进而证明了有限布尔代数上的非可逆内动机图型为恰等叉支下向树的充分必要条件。     

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

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

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

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

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

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

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

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

有限自动机定义函数的线性本原圈积分解

本文讨论有限自动机显表出定义函数ｆ的线性本原圈积分解问题。在该圈积分解之下,函数ｆ被表成线性外函数因子ｆＬ与线性本原内涵数因子ｆＮ的圈积,这里函数ｆＬ定义了一个线性弱可逆有限自动机ＭｆＬ,而函数ｆＮ定义了一个非线性有限自动机ＭｆＮ且其不能再分解成一非平凡的线性外函数与一非线性内函数的圈积。本文证明了一函数ｆ的任两线性本原内因子互为对方的线性本原内因子,从而证明了函数ｆ的线性本原圈积分解的唯一性。本     

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

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

线性自动机的奇偶性

根据线性自动机的状态迁移图型,容易看出其迁移变换(置换)的奇偶性(对于非奇异情形)。本文利用线性自动机的图型理论,给出一些由初等因子组判定奇偶性的结果。     

关于正则文法及有限自动机的一点注记

本文讨论了正则语言的特征标c以及它的生成正则文法的变量个数n和其接受有限自动机的状态个数S(NM)之间的关系。得到了不等式n≥[log_2c-1],S(NM)≥[log_2c-1]。并且证明了,对任意整数 c>2,常存在这样的正则语言,此语言具特征标c,并恰能被一个含变量个数为[(log_2c)-1]的正则文法生成。     

右线性文法与有限自动机等价性的一个新证明

迄今为止,左、右线性文法与有限自动机的等价性都是通过相互模拟构造来证明的。文章首先引入字母表上的右线性方程组及其最小解的概念,证明了最小解的存在性与有效可解性,描述了最小解的结构;其次通过右线性方程组及其最小解,证明了右线性文法与有限自动机的等价性。完全类似地,可以引入字母表上的左线性方程组及其最小解,并且证明左线性文...     

有限布尔代数上的自动机

本文对有限布尔代数上的自动机进行了研究，证明了有限布尔代数上的可逆内动机保持正交性；定出了有限布尔代数上的对称可逆内动机及一般ｎ（≤３）阶可逆内动机的图型。