###
DOI:
Journal of Software:2007.18(1):40-49

关于二元延迟3步前馈逆有限自动机的结构
王鸿吉,姚刚
(中国科学院,软件研究所,北京,100080;中国科学院,研究生院,北京,100049;信息安全国家重点实验室(中国科学院,软件研究所),北京,100080)
On the Structure of Binary Feedforward Inverse Finite Automata with Delay 3
WANG Hong-Ji,YAO Gang
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2822   Download 2442
Received:January 26, 2005    Revised:April 18, 2005
> 中文摘要: 前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题.对延迟步数≥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.
文章编号:     中图分类号:    文献标志码:
基金项目: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 (国家杰出青年科学基金) 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 (国家杰出青年科学基金)
Foundation items:
Reference text:

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

WANG Hong-Ji,YAO Gang.On the Structure of Binary Feedforward Inverse Finite Automata with Delay 3.Journal of Software,2007,18(1):40-49