Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time

Hagenah, Christian, and Muscholl, Anca. "Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time." RAIRO - Theoretical Informatics and Applications 34.4 (2010): 257-277. <http://eudml.org/doc/222051>.

@article{Hagenah2010,
abstract = { The standard procedure to transform a regular expression of size n to an ϵ-free nondeterministic finite automaton yields automata with O(n) states and O(n2) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic et al. showed how to build an ϵ-free NFA with only O(n log2(n)) transitions. The current lower bound on the number of transitions is Ω(n log(n)). A rough running time estimation for the common follow sets (CFS) construction proposed by Hromkovič et al. yields a cubic algorithm. In this paper we present a sequential algorithm for the CFS construction which works in time O(n log(n) + size of the output). On a CREW PRAM the CFS construction can be performed in time O(log(n)) using O(n + (size of the output)/log(n)) processors. We also present a simpler proof of the lower bound on the number of transitions. },
author = {Hagenah, Christian, Muscholl, Anca},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Epsilon-free nondeterministic automata; regular expressions; common follow sets construction.; nondeterministic finite automaton},
language = {eng},
month = {3},
number = {4},
pages = {257-277},
publisher = {EDP Sciences},
title = {Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time},
url = {http://eudml.org/doc/222051},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Hagenah, Christian
AU - Muscholl, Anca
TI - Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 4
SP - 257
EP - 277
AB - The standard procedure to transform a regular expression of size n to an ϵ-free nondeterministic finite automaton yields automata with O(n) states and O(n2) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic et al. showed how to build an ϵ-free NFA with only O(n log2(n)) transitions. The current lower bound on the number of transitions is Ω(n log(n)). A rough running time estimation for the common follow sets (CFS) construction proposed by Hromkovič et al. yields a cubic algorithm. In this paper we present a sequential algorithm for the CFS construction which works in time O(n log(n) + size of the output). On a CREW PRAM the CFS construction can be performed in time O(log(n)) using O(n + (size of the output)/log(n)) processors. We also present a simpler proof of the lower bound on the number of transitions.
LA - eng
KW - Epsilon-free nondeterministic automata; regular expressions; common follow sets construction.; nondeterministic finite automaton
UR - http://eudml.org/doc/222051
ER -