| Presentation | 2017-05-13 On Equivalence of de Bruijn Graphs and State-minimized Finite Automata Yoshiaki Takahashi, Akira Ito, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | de Bruijn sequence / de Bruijn graphs / finite automata / state-minimization |
| Paper # | COMP2017-11 |
| Date of Issue | 2017-05-05 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2017/5/12(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiro Ito(Univ. of Electro-Comm.) / 堀山 貴史(埼玉大) |
| Vice Chair | Yushi Uno(Osaka Pref. Univ.) |
| Secretary | Yushi Uno(Seikei Univ.) / (Kyushu Inst. of Tech.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On Equivalence of de Bruijn Graphs and State-minimized Finite Automata |
| Sub Title (in English) | |
| Keyword(1) | de Bruijn sequence |
| Keyword(2) | de Bruijn graphs |
| Keyword(3) | finite automata |
| Keyword(4) | state-minimization |
| 1st Author's Name | Yoshiaki Takahashi |
| 1st Author's Affiliation | Hofu Science Museum(Solar) |
| 2nd Author's Name | Akira Ito |
| 2nd Author's Affiliation | Yamaguchi University(Yamaguchi Univ.) |
| Date | 2017-05-13 |
| Paper # | COMP2017-11 |
| Volume (vol) | vol.117 |
| Number (no) | COMP-28 |
| Page | pp.pp.77-83(COMP), |
| #Pages | 7 |
| Date of Issue | 2017-05-05 (COMP) |