软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2007年
1期
40-49
,共10页
有限自动机%半输入存储%前馈逆%可逆性
有限自動機%半輸入存儲%前饋逆%可逆性
유한자동궤%반수입존저%전궤역%가역성
finite automata%semi-input memory%feedforward inverses%invertibility
前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题.对延迟步数≥3的前馈逆结构的刻划,则是一个长期的未解决问题.研究了二元延迟3步前馈逆有限自动机的结构.对于自治有限自动机Ma的状态图为圈的二元延迟3步弱可逆半输入存储有限自动机C(Ma,f ),给出了其长3极小输出权分别为1,2,8三种情形下结构的一种刻画.由于C(Ma,f )延迟3步弱可逆当且仅当它是延迟3步弱逆,因此,得到了二元延迟3步前馈逆有限自动机结构的一种部分刻画.
前饋逆有限自動機的結構是有限自動機可逆性理論中的基本問題.對延遲步數≥3的前饋逆結構的刻劃,則是一箇長期的未解決問題.研究瞭二元延遲3步前饋逆有限自動機的結構.對于自治有限自動機Ma的狀態圖為圈的二元延遲3步弱可逆半輸入存儲有限自動機C(Ma,f ),給齣瞭其長3極小輸齣權分彆為1,2,8三種情形下結構的一種刻畫.由于C(Ma,f )延遲3步弱可逆噹且僅噹它是延遲3步弱逆,因此,得到瞭二元延遲3步前饋逆有限自動機結構的一種部分刻畫.
전궤역유한자동궤적결구시유한자동궤가역성이론중적기본문제.대연지보수≥3적전궤역결구적각화,칙시일개장기적미해결문제.연구료이원연지3보전궤역유한자동궤적결구.대우자치유한자동궤Ma적상태도위권적이원연지3보약가역반수입존저유한자동궤C(Ma,f ),급출료기장3겁소수출권분별위1,2,8삼충정형하결구적일충각화.유우C(Ma,f )연지3보약가역당차부당타시연지3보약역,인차,득도료이원연지3보전궤역유한자동궤결구적일충부분각화.
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(Ma,f) 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(Ma,f) 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.
