| Presentation | 2004-09-17 Faster Bit-Parallel Algorithms for Translating Regular Expressions into NFAs Hiroaki YAMAMOTO, Takashi MIYAZAKI, Masayuki OKAMOTO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The aim of the paper is to design efficient bit-parallel algorithms for translating regular expressions into nondeterministic finite automata (NFAs). Let r be a regular expression over an alphabet Σ, and let n be the length of r and let m be the number of symbols of Σ occurring in r. Then we present a bit-parallel algorithm for translating regular expressions into Glushkov automata (position automata), which runs in O(n+m^2/W) time and space, where W is word-length of a computer. Since the best known algorithm runs in O(n+m^2) time and space, our algorithm achieves an almost W-fold speed-up. Furthermore, we show a bit-parallel algorithm which constructs a follow automaton in O(n+m^2 log m/W) time and O(n+m^2/W) space. If we are allowed to use a more space, then we can improve the running time so that it becomes O(n+m^2/W). |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | regular expression / Glushkov automaton / Follow automaton |
| Paper # | COMP2004-27 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2004/9/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 | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Faster Bit-Parallel Algorithms for Translating Regular Expressions into NFAs |
| Sub Title (in English) | |
| Keyword(1) | regular expression |
| Keyword(2) | Glushkov automaton |
| Keyword(3) | Follow automaton |
| 1st Author's Name | Hiroaki YAMAMOTO |
| 1st Author's Affiliation | Faculty of Engineering, Shinshu University() |
| 2nd Author's Name | Takashi MIYAZAKI |
| 2nd Author's Affiliation | Nagano National College of Technology |
| 3rd Author's Name | Masayuki OKAMOTO |
| 3rd Author's Affiliation | Faculty of Engineering, Shinshu University |
| Date | 2004-09-17 |
| Paper # | COMP2004-27 |
| Volume (vol) | vol.104 |
| Number (no) | 317 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |