\title{Computing $\eps$-Free NFA from Regular Expressions 
in $O(n \log^2(n))$ Time}



\author{Christian Hagenah and Anca Muscholl}

\institute{Institut f\"ur Informatik, Universit\"at Stuttgart,\\
  Breitwiesenstr.~20-22, 70565 Stuttgart, Germany }


  The standard procedure to transform a regular expression to an
  $\eps$-free NFA
  yields a quadratic blow-up of the number of transitions. For
  a long time this was viewed as an unavoidable fact. Recently Hromkovi\u{c}
  et.al.~\cite{hsw97} exhibited a construction yielding $\eps$-free NFA with
  $O(n \log^2(n))$ transitions. A rough estimation of the time needed for their
  construction shows a cubic time bound. The known lower bound is $\Omega(n
  \log(n))$.  In this paper we present a sequential
  algorithm for the construction described in \cite{hsw97} which
  works in time $O(n \log(n) + \mbox{size of the output})$. On a CREW PRAM
  the construction is possible in time $O(\log(n))$ using $O(n + (\mbox{size of
  the output})/\log(n))$ processors.