@InProceedings{	  HagenahM98mfcs,
  author	= "Christian Hagenah and Anca Muscholl",
  title		= "Computing $\epsilon$-Free NFA from Regular Expressions in
		  $O(n \log^{2}(n))$ Time",
  volume	= "1450",
  year		= "1998",
  pages		= "277--285",
  publisher	= "Springer",
  address	= "Heidelberg",
  series	= "Lecture Notes in Computer Science",
  booktitle	= "Mathematical Foundations of Computer Science 1998, 23rd
		  International Symposium, MFCS'98, Brno, Czech Republic,
		  August 24-28, 1998, Proceedings",
  editor	= "Brim, Lubos and Gruska, Josef and Zlatuska, Jiri",
  doi		= "10.1007/BFb0055777",
  abstract	= "The standard procedure to transform a regular expression
		  to an $\epsilon$-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
		  $\epsilon$-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) + \mathrm{size of the
		  output})$. On a CREW PRAM the construction is possible in
		  time $O(\log(n))$ using $O(n + (\mathrm{size of the
		  output})/\log(n))$ processors."
}