弱可逆有限自动机的分解

• 作者: 易忠 曹锋 邓培民
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 有限自动机 弱可逆 分解 化合 延迟步数
• 年，卷（期）: 2005,（9）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1501-1507
• 页数: 7页
• 分类号: TP301
• 字数: 8426字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2005.09.011

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邓培民	广西师范大学数学与计算机科学学院	61	278	9.0	13.0
2	易忠	广西师范大学数学与计算机科学学院	65	244	9.0	11.0
3	曹锋	广西师范大学数学与计算机科学学院	3	101	3.0	3.0