二値アルファベット上の有限オートマトンの等価変換と状態数解析

• Item type: SIG Technical Reports(1)
• 公開日: 2008-03-07
• タイトル: 二値アルファベット上の有限オートマトンの等価変換と状態数解析
• タイトル / 言語: en
• タイトル: Equivalent Transformation of Finite Automata over a Two-Letter Alphabet and the State Complexity
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京電機大学理工学部情報システム工学科
• 著者所属: 東京電機大学理工学部情報システム工学科
• 著者所属(英): en
• 著者所属(英): Department of Computers and Systems Engineering, School of Science and Engineering, Tokyo Denki University
• 著者所属(英): en
• 著者所属(英): Department of Computers and Systems Engineering, School of Science and Engineering, Tokyo Denki University
• 著者名: 松浦, 昭洋; 齋藤, 祐輔
• 著者名(英): Akihiro, Matsuura; Yusuke, Saito
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 任意の非負整数αに対して，n 状態の非決定性有限オートマトン (NFA) で，そ等価な最小決定性有限オートマトン (DFA) が 2n ?α状態を持つものが存在するか，という問題は Iwama ら [3] によって提起された．本稿では、n ? 11 a ? 3n -3 [(a -1) / 3J] が奇数でかつnと互いに素である，という条件を満たす n と α に対して，n 状態 NFA で，その等価な最小 DFA が 2n -α 状態を持つものが存在することを示す．また，α < 4n ? 5 の範囲の 4 の倍数でない α に対しても，同様の NFA の存在を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In [3], Iwama et al. posed a problem which asks whether, for a given integer α, there exists a minimum n-state nondeterministic finite automaton (NFA) that is equivalent to a minimum deterministic finite automaton (DFA) with exactly 2n -α states. In this paper, we show that for all integers n 竕･ 11 and α, such that α 竕､ 3n - 3 and satisfying that [ (a - 1) / 3] is odd and is relatively prime with n, there exists a minimum n-state NFA whose equivalent minimum DFA has exactly 2n - α states. The results are then extended for α such that α 竕､ 4n - 5 when α is not divisible by four.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 24(2008-AL-117), p. 75-82, 発行日 2008-03-07
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会