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 automata with delay 2 is presented.

弱可逆有限自动机的分解

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

由单个状态生成的有限自动机的一些性质

本文研究了由单个状态生成的有限自动机的弱可逆性及分解,得出了由单个状态生成的有限自动机弱可逆的充分必要条件,证明了由单个状态生成的延迟τ步弱可逆有限自动机M能分解为一个延迟0步弱可逆有限自动机和一个τ阶延迟元的充要条件是M的生成子的τ长输出权为1.

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

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

路代数和有限自动机

本文定义了有限自动机的路代数,讨论了有限自动机的性质与其路代数的代数性质之间的关系,得出了一些结果.