| 分解弱可逆有限自动机的两个结果 |
| |
| 引用本文： | 王鸿吉.分解弱可逆有限自动机的两个结果[J].计算机研究与发展,2005,42(4):690-696. |
| |
| 作者姓名： | 王鸿吉 |
| |
| 作者单位： | 中国科学院软件研究所,北京,100080;中国科学院研究生院,北京,100039 |
| |
| 基金项目： | 国家自然科学基金项目(60073021)，国家自然科学基金重大国际(地区)合作研究项目(60310213)，国家杰出青年基金项目(60325206)，江西省自然科学基金项目(z01685) |
| |
| 摘 要： | 研究弱可逆有限自动机的分解可以为分析有限自动机公开钥密码体制的安全性提供一种重要途径．从输出权的角度研究了n元延迟τ步弱可逆有限自动机M的分解问题，首先证明了其可分解为一个延迟0步弱可逆有限自动机和一个τ阶延迟元当且仅当M的所有状态的长τ输出权为1．其次，在获得一类不可分解出延迟元的弱可逆有限自动机的基础上，构造出一个反例，否定回答了鲍丰在1993年提出的一个公开问题．同时给出了二元严格延迟τ步强连通弱可逆有限自动机可分解为一个严格延迟τ—1步弱可逆有限自动机和一个严格延迟1步弱可逆有限自动机的一个充分条件．
|
| 关 键 词： | 有限自动机 弱可逆 延迟 分解 输出权 |
Two Results of Decomposing Weakly Invertible Finite Automata |
| |
| Wang Hongji.Two Results of Decomposing Weakly Invertible Finite Automata[J].Journal of Computer Research and Development,2005,42(4):690-696. |
| |
| Authors: | Wang Hongji |
| |
| Abstract: | |
| |
| Keywords: | finite automata weakly invertible delay decomposition output weight |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
