共查询到16条相似文献,搜索用时 187 毫秒
1.
讨论有限自动机的分解有助于分析弱可逆有限自动机的结构和求解弱逆.首先证明了弱同构的弱可逆有限自动机具有相似的分解形式;接着考虑了一类特殊的弱可逆线性有限自动机的分解,从状态输出权的角度刻画了该分解存在的一个充分条件;然后把这种分解形式推广到了一般的弱可逆线性有限自动机上,即:延迟τ步弱可逆线性有限自动机分解成延迟0步弱可逆有限自动机和一种特殊的有限自动机MD,并得到了分解存在的充要条件;最后,用输出序列的代数性质来刻画其中的充分条件,并把它转化成了一个矩阵的秩的计算.这种分解形式并不局限于n元弱可逆有限自动机,而且分解条件也比较简单,仅与输出序列的性质有关. 相似文献
2.
分解弱可逆有限自动机的两个结果 总被引:8,自引:0,他引:8
王鸿吉 《计算机研究与发展》2005,42(4):690-696
研究弱可逆有限自动机的分解可以为分析有限自动机公开钥密码体制的安全性提供一种重要途径.从输出权的角度研究了n元延迟τ步弱可逆有限自动机M的分解问题,首先证明了其可分解为一个延迟0步弱可逆有限自动机和一个τ阶延迟元当且仅当M的所有状态的长τ输出权为1.其次,在获得一类不可分解出延迟元的弱可逆有限自动机的基础上,构造出一个反例,否定回答了鲍丰在1993年提出的一个公开问题.同时给出了二元严格延迟τ步强连通弱可逆有限自动机可分解为一个严格延迟τ—1步弱可逆有限自动机和一个严格延迟1步弱可逆有限自动机的一个充分条件. 相似文献
3.
关于弱可逆有限自动机延迟步数分解的两个结果 总被引:7,自引:2,他引:5
本文证明存在(任意元)延迟2步弱可逆有限自动机不等价于任何两个延迟1步弱可逆有限自动机的化合的任何子自动机。因而说明了不是对所有的弱可逆有限自动机,延迟步数都是可分解的,但对所有状态的延迟步数均为2的二元延迟2步弱可逆有限自动机,则分解是可行的。 相似文献
4.
主要研究拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆性,以及它的弱逆,得到了拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆的充分必要条件,并且通过所得结果可以比较简便地构造出延迟k步与k+1步弱可逆拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱逆. 相似文献
5.
主要研究拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆性,以及它的弱逆,得到了拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆的充分必要条件,并且通过所得结果可以比较简便地构造出延迟k步与k+1步弱可逆拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱逆。 相似文献
6.
二元弱可逆有限自动机延迟步数的分解 总被引:7,自引:1,他引:6
本文考虑二元严格延迟τ步弱可逆有限自动机M的延迟步数的分解问题。首先证明如果M强连通且所有状态的延迟步数不小于τ-1,则M一定能分解为一个延迟0步弱可逆有限自动机和一个τ阶延迟元。然后证明如果M所有状态延迟步数均不小于m,那么M可以分解为一个严格延τ-m步弱可逆有限自动机和一个m阶延迟元。最后考虑了M可分解为一个严格延迟τ-1步和一个严格延迟1步弱可逆有限自动机的条件。 相似文献
7.
8.
关于弱可逆线性有限自动机的弱逆的结构 总被引:1,自引:1,他引:1
本文研究的主要问题是:对给定延迟τ步弱可逆线性有限自动机M,求出M的所有延迟τ步弱逆线性有限自动机。解决的办法是:首先求出所有M的延迟τ步弱逆的传输函数矩阵,然后对每个传输函数矩降,求出以它为传输函数矩阵的所有M的延迟τ步弱逆。 相似文献
9.
一种有限自动机公开钥密码体制和数字签名 总被引:15,自引:4,他引:15
本文提出一种基于有限自动机可逆性理论的公开钥密码体制,它的公开的加密算法由一个非线性延迟O步弱可逆γ阶输入存储有限自动机M和一个延迟τ步可逆(τ,τ)阶存储线性有限自动机M_1经过复合后所得的(τ γ,τ)阶存储有限自动机M所实现,它的秘密的解密算法由M_1的延迟τ步逆M_1′和M的延迟O步弱逆M所实现,这种有限自动机公开钥密码体制的保密性建立在求非线性有限自动机的弱逆的困难性和矩阵多项式因式分解的困难性之上,文中又讨论了用这种密码体制建立数字签名的方法。 相似文献
10.
本文讨论延迟τ步可逆有限自动机M的所有延迟τ步逆有限自动机组成的类的结构问题,和以给定有限自动机M′为延迟′步逆的所有有限自动机组成的类的结构问题。对于输入输出字母表大小相同的情形,给出了构造M的通用延迟τ步逆有限自动机和以M′为延迟τ步逆的通用有限自动机的方法,并证明了在等价的意义下前述两类有限自动机都构成一个分配有界格。 相似文献
11.
Structure of weakly invertible semi-input-memory finite automata with delay 2 总被引:1,自引:0,他引:1 下载免费PDF全文
Semi-input-memory finite automata,a kind of finite automata introduced by the author of this paper for studying error propagation,are a generalization of input-memory finite automata by appending an autonomous finite automaton component.This paper gives a characterization on the structure of weakly invertible semi-input-memory finite automata with delay 2 in which input alphabets and output alphabets have two elements and autonomous finite automata are cyclic.For the structure of feedforward inverse finite automata with delay 2,Zhu first gave a characterization;from a result on mutual invertibility of finite automata,the result mentioned above also leads to a different characterization on the structure of feedforward result mentioned above also leads to a different characterization on the structure of feedforward inverse finite automata with delay 2. 相似文献
12.
On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton 总被引:1,自引:1,他引:0 下载免费PDF全文
Chen Shihua 《计算机科学技术学报》1986,1(3):92-100
In this paper, we first give a method by which, for any weakly invertible finite automatonM with delay τ, the set of all weak inverse finite automata of M with delay τ can beconstructed. We then give a method by which, for any invertible one, all its inverses with delayτ can also be constructed. 相似文献
13.
通过对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机输出权的研究,得出对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机的任意一个状态,它的长r的输出权都是1;任何一个n元拟(r,r)阶存贮线性有限自动机M延迟r步弱可逆的充分必要条件是M都可以分解为一个延迟0步弱可逆有限自动机M0和一个延迟r步弱可逆拟(0,r)阶存贮线性有限自动机M1。 相似文献
14.
Structure of Weakly Invertible Semi-Input-Memory Finite Automata with Delay 1 总被引:4,自引:2,他引:4 下载免费PDF全文
Semi-input-memory finite automata,a kind of finite automata introduced by the first author of this paper for studying error propagation ,are a generalization of inputmemory finite automata ,by appending an autonomous finite automation component .In this paper,we give a characterization of the structure of weakly invertible semi-input-memory finite automata with delay 1,in which the state graph of each autonomous finite automation is cycle,From a result on mutual invertibility of finite automata obtained by th authors recently,it leads to a characerization of the structure of feedfoward inverse finite automata with delay 1. 相似文献
15.
姚刚 《计算机科学技术学报》2003,18(3):0-0
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. 相似文献
16.
环上线性有限自动机的可逆性的一些结果 总被引:8,自引:0,他引:8
本文证明了有单位元的有限交换环R上任何延迟t步(弱)可逆线性有限自动机皆有延迟t步线性(弱)逆的充分必要条件是环R满足条件: x(Ax=0→bx=0)→y(b=yA)我们还证明了对任何有单有限交换环R,R上输入、输出维数相同的延迟t步(弱)可逆线性有限自动机具有延迟t步线性(弱)逆. 相似文献