Bit-Parallel Algorithms for Translating Regular Expressions into NFAs

• YAMAMOTO Hiroaki

  the Faculty of Engineering, Shinshu University

• MIYAZAKI Takashi

  the Nagano National College of Technology

• OKAMOTO Masayuki

  the Faculty of Engineering, Shinshu University

Abstract

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 bit-parallel algorithms for translating regular expressions into Glushkov automata (position automata) and follow automata using Thompson automata. For Glushkov automata, we will give an algorithm which runs in O(n+m[m/W]) time and space. For follow automata, we will give a randomized algorithm which runs in O(n+m[m/W]) expected time and O(n+m[m/W]) space. We rely on a W-bit uniform RAM for estimating the complexities of algorithms. Since the best known algorithms for these automata runs in O(n+m^2) time and space, our algorithms achieve an almost W-fold speed-up.

Journal

• IEICE Trans. Inf. & Syst., D

  IEICE Trans. Inf. & Syst., D 90 (2), 418-427, 2007-02-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• regular expression
• finite automaton

Details

• CRID: 1571980077439045376
• NII Article ID: 110007519485
• NII Book ID: AA10826272
• ISSN: 09168532
• Text Lang: en
• Data Source:
  • CiNii Articles