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

Christian Hagenah; Anca Muscholl

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 4, page 257-277
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHagenah, 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 -

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.