| Presentation | 2011-01-18 A Regular Expression Matching Circuit Based on a Decomposed Automaton Hiroki NAKAHARA, Tsutomu SASAO, Munehiro MATSUURA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we propose a regular expression matching circuit based on a decomposed automaton. To implement regular expressions on the hardware, first, we convert them to a non-deterministic finite automaton (NFA). Then, to reduce the number of states, we convert the NFA into a modular non-deterministic finite automaton with unbounded multi-character transition (MNFAU). Next, to realize it by a feasible amount of the hardware, we decompose the MNFAU into the deterministic finite automaton (DFA) and the NFA. The DFA part is implemented by an off-chip memory and a simple sequenser, while the NFA part is implemented by a cascade of logic cells. Also, this paper shows that the MNFAU based implementation is superior to the DFA and the NFA based ones, with respect to the area and time complexity. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | VLD2010-98,CPSY2010-53,RECONF2010-67 |
| Date of Issue |
| Conference Information | |
| Committee | RECONF |
|---|---|
| Conference Date | 2011/1/10(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Reconfigurable Systems (RECONF) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Regular Expression Matching Circuit Based on a Decomposed Automaton |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | Hiroki NAKAHARA |
| 1st Author's Affiliation | Department of Computer Science and Electronics, Kyushu Institute of Technology() |
| 2nd Author's Name | Tsutomu SASAO |
| 2nd Author's Affiliation | Department of Computer Science and Electronics, Kyushu Institute of Technology |
| 3rd Author's Name | Munehiro MATSUURA |
| 3rd Author's Affiliation | Department of Computer Science and Electronics, Kyushu Institute of Technology |
| Date | 2011-01-18 |
| Paper # | VLD2010-98,CPSY2010-53,RECONF2010-67 |
| Volume (vol) | vol.110 |
| Number (no) | 362 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |