| 講演名 | 2017-05-13 ドブリュイングラフと状態数最小化有限オートマトンの等価性について 高橋 芳明(ソラール), 伊藤 暁(山口大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 一つの系列の中にある長さnのすべてのビットパターンが現れる周期系列をn次のドブリュイン系列という．本稿では，可能なすべてのドブリュイン系列を調べるために導入されたドブリュイングラフと呼ばれる有向グラフと正規言語(0+1)^*1(0+1)^(n-1)を受理する最小状態数決定性有限オートマトンの状態遷移図の構造的同一性を証明する．また，本結果を 進ドブリュイングラフとの等価性に拡張するためには，状態間の同値性の再定義が必要であることを示す． |
| 抄録(英) | A de Bruijn sequence of order n on the alphabet {0,1} is a cyclic sequence in which every possible string of length n over {0,1} occurs exactly once. In order to enumerate all possible de Bruijn sequences, de Bruijn graphs were introduced. This study investigates the relationship between de Bruijn graphs and finite automata and proves the structural equality of de Bruijn graph of order n and the state transition diagram for minimum state deterministic finite automaton which accepts regular language (0+1)^*1(0+1)^(n-1) . We also point out that a certain modification of the definition of state equivalence is needed to extend this result to k-ary de Bruijn graphs. |
| キーワード(和) | ドブリュイン系列 / ドブリュイングラフ / 有限オートマトン / 状態数最小化 |
| キーワード(英) | de Bruijn sequence / de Bruijn graphs / finite automata / state-minimization |
| 資料番号 | COMP2017-11 |
| 発行日 | 2017-05-05 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2017/5/12(から2日開催) |
| 開催地（和） | 長崎県建設工業協同組合 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 伊藤 大雄(電通大) / 堀山 貴史(埼玉大) |
| 委員長氏名（英） | Hiro Ito(Univ. of Electro-Comm.) / 堀山 貴史(埼玉大) |
| 副委員長氏名（和） | 宇野 裕之(阪府大) |
| 副委員長氏名（英） | Yushi Uno(Osaka Pref. Univ.) |
| 幹事氏名（和） | 脊戸 和寿(成蹊大) / 斎藤 寿樹(九工大) / 岡本 吉央(電通大) / 川原 純(NAIST) / 河村 彰星(東大) |
| 幹事氏名（英） | Kazuhisa Seto(Seikei Univ.) / Toshiki Saito(Kyushu Inst. of Tech.) / 岡本 吉央(電通大) / 川原 純(NAIST) / 河村 彰星(東大) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ドブリュイングラフと状態数最小化有限オートマトンの等価性について |
| サブタイトル（和） | |
| タイトル（英） | On Equivalence of de Bruijn Graphs and State-minimized Finite Automata |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ドブリュイン系列 / de Bruijn sequence |
| キーワード(2)（和/英） | ドブリュイングラフ / de Bruijn graphs |
| キーワード(3)（和/英） | 有限オートマトン / finite automata |
| キーワード(4)（和/英） | 状態数最小化 / state-minimization |
| 第 1 著者 氏名（和/英） | 高橋 芳明 / Yoshiaki Takahashi |
| 第 1 著者 所属（和/英） | 防府市青少年科学館(略称：ソラール) Hofu Science Museum(略称：Solar) |
| 第 2 著者 氏名（和/英） | 伊藤 暁 / Akira Ito |
| 第 2 著者 所属（和/英） | 山口大学(略称：山口大) Yamaguchi University(略称：Yamaguchi Univ.) |
| 発表年月日 | 2017-05-13 |
| 資料番号 | COMP2017-11 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | COMP-28 |
| ページ範囲 | pp.77-83(COMP), |
| ページ数 | 7 |
| 発行日 | 2017-05-05 (COMP) |