| 弱可逆有限自动机的分解 |
| |
| 引用本文： | 曹锋,邓培民,易忠.弱可逆有限自动机的分解[J].计算机学报,2005,28(9):1501-1507. |
| |
| 作者姓名： | 曹锋 邓培民 易忠 |
| |
| 作者单位： | 1. 广西师范大学数学与计算机科学学院,桂林,541004;上海交通大学计算机科学与工程系,上海,200030
2. 广西师范大学数学与计算机科学学院,桂林,541004 |
| |
| 基金项目： | 本课题得到广西壮族自治区自然科学基金（0135005）资助. |
| |
| 摘 要： | 有限自动机公开钥密码体制的提出进一步激励了有限自动机可逆性的研究．在有限自动机公开钥密码体制中首次提出了自动机化合的概念．易知，两个弱可逆有限自动机的化合仍然是一个弱可逆有限自动机并且它的延迟步数不大于前两个有限自动机延迟步数之和．然而，另一方面，如何将一个弱可逆有限自动机分解为两个弱可逆有限自动机的化合却是一个非常困难的问题．该文主要考虑了一类n元严格延迟τ步弱可逆有限自动机M的延迟步数的分解问题．给出了一类特殊的n元弱可逆有限自动机分解的条件和结果．首先证明了如果对M中的每个状态s有T（s，τ）枝等，则M可分解为τ个延迟1步弱可逆有限自动机的化合．然后证明了M可分解为一个τ—m步弱可逆有限自动机和m阶延迟元的充要条件是对M中的每个状态s有T（s，m）枝等．
|
| 关 键 词： | 有限自动机 弱可逆 分解 化合 延迟步数 |
| 收稿时间： | 2003-07-25 |
| 修稿时间： | 2003-07-252005-07-04 |
Decomposition of Weakly Invertible Finite Automata |
| |
| CAO Feng,DENG Pei-Min,YI Zhong.Decomposition of Weakly Invertible Finite Automata[J].Chinese Journal of Computers,2005,28(9):1501-1507. |
| |
| Authors: | CAO Feng DENG Pei-Min YI Zhong |
| |
| Abstract: | |
| |
| Keywords: | finite automata weakly invertible decomposition composition delay step |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
