弱可逆有限オートマトンの分解に関するいくつかの結果

• Item type: SIG Technical Reports(1)
• 公開日: 1994-11-18
• タイトル: 弱可逆有限オートマトンの分解に関するいくつかの結果
• タイトル / 言語: en
• タイトル: Some Results on Decomposability of Weakly Invertible Finite Automata
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma Univercity
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma Univercity
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma Univercity
• 著者名: 鮑豊; 五十嵐, 善英; 于小梅
• 著者名(英): Feng, Bao; Yoshihide, Igarashi; Xiaomei, Yu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文で取り扱う弱可逆性有限オートマトン(FAと略記する）は入力系列を同じ長さの出力系列に変換する変換器である。長さt+1の入力系列の最初の文字が出力系列と初期状態から一意に決るとき、その変換器を遅れtのWIFAという。入力アルファベットと出力アルファベットが同じで、その大きさがnである変換器をn?WIFAで表す。n>1のとき、二つの遅れ1のn?WIFAに分解できない遅れ2のn?WIFAが存在することを示し。任意の素数pについて、遅れ1のp?WIFAは遅れ0のn?WIFAと単位遅れ回路に分解できることを示す。また2?WIFAが遅れ0のWIFAとk個の単位遅れ回路に分解できるのは、Mの全ての状態が遅れkを持つとき、かつそのときに限ることを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A weakly invertible finite automaton (WIFA for short) is an invertible transducer which converts a finite input string into an output string of the same-length. A finite automaton is called a WIFA with delay t if and only if the first letter of the input string of length t+1 is uniquely determined by the coorresponding output string and the initial state. The composition of two WIFAs is their natural concatenation, which is again a WIFA whose delay is the sum of the delays of the two WIFAs. Previously, seldom is known about the decomposition of a WIFA into the WIFAs with smaller delay. In this paper We present various results on this subject. The interest of this topic comes from both theory and application aspects. In order to capture the essence of the decompposability problem, we only conc entrate on the WIFAs such that the output alphabet is the same as the input alphabet. We call M=(X,X,S,δ,λ) an n-FA if |X|=n. We prove that for any n>1, there exist some n-WIFAs with delay 2 which cannot be decomposed into two n-WIFAs with delay 1. and that for any prime number p, every strongly connected p-WIFA with delay 1, can be decomposed into a WIFA with delay 0 and a delay unit. A delay unit is a special WIFA with delay 1, which is actually a logic memory cell. For any 2-WIFA M, M can be decomposed into a WIFA with delay 0 and k connected delay units if and only if all the states of M have delay k.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1994, 号 100(1994-AL-042), p. 17-24, 発行日 1994-11-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会