Bit-Parallel Algorithms for Translating Regular Expressions into NFAs(Automata,<Special Section>Foundations of Computer Science)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2007-02-01

著者

• Miyazaki Takashi

  Nagano National College of Technology

• Yamamoto Hiroaki

  Faculty Of Engineering Shinshu University

• OKAMOTO Masayuki

  Faculty of Engineering, Shinshu University

• Okamoto Masayuki

  Faculty Of Engineering Shinshu University

関連論文

• Investigation of Linearity of Photoacoustic Characteristics on Semiconductors Measured by Michelson Interferometry : Photoacoustic Spectroscopy
• Electric Field Effect on Subband State Transitions Peaks in the Photoluminescence from a GaAlAs Quantum Well Structure
• An Optimal Nonlinear Regulator Design with Neural Network and Fixed Point Theorem (Special Section on Neural Nets, Chaos and Numerics)
• Bit-Parallel Algorithms for Translating Regular Expressions into NFAs(Automata,Foundations of Computer Science)
• A Note on Leaf Reduction Theorem for Reversal and Leaf-Bounded Alternating Turing Machines
• D-4-1 Searching an Encrypted XML Document Using Keywords

スポンサーリンク