位置:成果数据库 > 期刊 > 期刊详情页
弱可逆线性有限自动机的一种分解
  • ISSN号:1000-1239
  • 期刊名称:计算机研究与发展
  • 时间:0
  • 页码:1043-1051
  • 语言:中文
  • 分类:TP301.1[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
  • 作者机构:[1]广西师范大学数学科学学院,广西桂林541004, [2]广西师范大学计算机科学与信息工程学院,广西桂林541004
  • 相关基金:国家自然科学基金项目(60663001);广西壮族自治区自然科学基金项目(0832103)
  • 相关项目:描述逻辑循环定义的理论框架及其推理机制研究
中文摘要:

讨论有限自动机的分解有助于分析弱可逆有限自动机的结构和求解弱逆.首先证明了弱同构的弱可逆有限自动机具有相似的分解形式;接着考虑了一类特殊的弱可逆线性有限自动机的分解,从状态输出权的角度刻画了该分解存在的一个充分条件;然后把这种分解形式推广到了一般的弱可逆线性有限自动机上,即:延迟τ步弱可逆线性有限自动机分解成延迟0步弱可逆有限自动机和一种特殊的有限自动机MD,并得到了分解存在的充要条件;最后,用输出序列的代数性质来刻画其中的充分条件,并把它转化成了一个矩阵的秩的计算.这种分解形式并不局限于it/元弱可逆有限自动机,而且分解条件也比较简单,仅与输出序列的性质有关.

英文摘要:

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.

同期刊论文项目
同项目期刊论文
期刊信息
  • 《计算机研究与发展》
  • 中国科技核心期刊
  • 主管单位:中国科学院
  • 主办单位:中国科学院计算技术研究所
  • 主编:徐志伟
  • 地址:北京市科学院南路6号中科院计算所
  • 邮编:100190
  • 邮箱:crad@ict.ac.cn
  • 电话:010-62620696 62600350
  • 国际标准刊号:ISSN:1000-1239
  • 国内统一刊号:ISSN:11-1777/TP
  • 邮发代号:2-654
  • 获奖情况:
  • 2001-2007百种中国杰出学术期刊,2008中国精品科...,中国期刊方阵“双效”期刊
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,荷兰文摘与引文数据库,美国工程索引,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊(2004版),中国北大核心期刊(2008版),中国北大核心期刊(2011版),中国北大核心期刊(2014版),中国北大核心期刊(2000版)
  • 被引量:40349