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

A Decomposition of the Weakly Invertible Linear Finite Automata

作　　者：姚兴华[1] 邓培民[1] 易忠[1] 蒋运承[2] 

机构地区：[1]广西师范大学数学科学学院,广西桂林541004 [2]广西师范大学计算机科学与信息工程学院,广西桂林541004

出　　处：《计算机研究与发展》2009年第6期1043-1051,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60663001);广西壮族自治区自然科学基金项目(0832103)~~

摘　　要：讨论有限自动机的分解有助于分析弱可逆有限自动机的结构和求解弱逆.首先证明了弱同构的弱可逆有限自动机具有相似的分解形式;接着考虑了一类特殊的弱可逆线性有限自动机的分解,从状态输出权的角度刻画了该分解存在的一个充分条件;然后把这种分解形式推广到了一般的弱可逆线性有限自动机上,即:延迟τ步弱可逆线性有限自动机分解成延迟0步弱可逆有限自动机和一种特殊的有限自动机MD,并得到了分解存在的充要条件;最后,用输出序列的代数性质来刻画其中的充分条件,并把它转化成了一个矩阵的秩的计算.这种分解形式并不局限于n元弱可逆有限自动机,而且分解条件也比较简单,仅与输出序列的性质有关.Composition of finite automata is a method of constructing new finite automata and is also a way of constructing public key in the finite automata public key crypt-systems. On the other hand, the study of the decomposition of weakly invertible finite automata is necessary, because it can help to analyze the structure of weakly invertible finite automata and solve its weak inverse. In this paper, firstly, it is proved that the weak isomorphism weakly invertible finite automata have similar decomposition. Secondly, a decomposition about a special weakly invertible linear finite automata （WILFA） M is considered, and a sufficient condition for the existence of this decomposition is found from the output weight of states. Thirdly, the decomposition is extended to the general WILFA, i. e. a WILFA with delay r can be decomposed into a WILFA with delay 0 and a finite automata MD. That is because any WILFA is weakly isomorphic to the special WILFA M. Meanwhile, a sufficient and necessary condition for the existence about this decomposition is obtained. Finally, this sufficient condition for the existence of the decomposition is reflected on the algebra property of the output sequence, and it is partly converted into counting the rank of a matrix. For this decomposing form, the decomposed finite automata needn＇t be n-ary weakly invertible finite automata, and the corresponding condition is only related with the output sequence.

关 键 词：有限自动机 弱可逆 分解 延迟 线性 输出权 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]