关于二元延迟3步前馈逆有限自动机的结构
作者:
基金项目:

Supported by the National Natural Science Foundation of China for Grand International Joint Project under Grant No.60310213 (国家自然科学基金重大国际(地区)合作研究项目); the National Natural Science Foundation for Distinguished Young Scholars of China under Grant No.60325206 (国家杰出青年科学基金)


On the Structure of Binary Feedforward Inverse Finite Automata with Delay 3
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题.对延迟步数≥3的前馈逆结构的刻划,则是一个长期的未解决问题.研究了二元延迟3步前馈逆有限自动机的结构.对于自治有限自动机Ma的状态图为圈的二元延迟3步弱可逆半输入存储有限自动机C(Maf ),给出了其长3极小输出权分别为1,2,8三种情形下结构的一种刻画.由于C(Maf )延迟3步弱可逆当且仅当它是延迟3步弱逆,因此,得到了二元延迟3步前馈逆有限自动机结构的一种部分刻画.

    Abstract:

    The structure of feedforward inverses is a fundamental problem in the invertibility theory of finite automata. The characterization of the structure of feedforward inverses with delay steps ≥3 is a long-term unsolved problem. This paper deals with this topic. For a binary weakly invertible semi-input memory finite automaton C(Maf ) with delay 3, where the state graph of Ma is cyclic, the characterizations of the structures are given when its minimal 3-output weight is 1, 2, and 8, respectively. Because C(Maf ) is weakly invertible with delay 3 iff it is weakly inverse with delay 3, a partial characterization of the structure of binary feedforward inverses with delay 3 is obtained.

    参考文献
    相似文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王鸿吉,姚刚.关于二元延迟3步前馈逆有限自动机的结构.软件学报,2007,18(1):40-49

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2005-01-26
  • 最后修改日期:2005-04-18
文章二维码
您是第19988517位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号