弱可逆有限自动机的分解

Decomposition of Weakly Invertible Finite Automata

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

In 1985, the finite automaton public key cryptosystem was proposed. It stimulates me investigation of invertibility of finite automata. The concept of composition of finite automata is first proposed in finite automaton public key cryptosystem. It is easy to get the conclusion that the composition of two weakly invertible finite automata is still a weakly invertible finite automaton, and its delay steps is no more than the sum of the delay steps of two finite automata. On the other hand, because lack the effective mathematics tool, the problem of how to decompose a weakly invertible finite automaton into two weakly invertible finite automata with smaller delay stops is still a difficult problem at present. In this paper, authors consider the problem of how to decompose a kind of n-ary weakly invertible finite automata with strict τ delays and get some resuits. Firstly, authors prove that M can be decomposed to r weakly invertible finite automatons with strict 1 delay if the tree T（s, τ） is equal-branch of all states, then prove M can be decomposed to a weakly invertible finite automaton with strict （τ-m） delays and a m-order delay units if the tree T（s,m） is equal-branch of all states.