Advanced Search

J. Hromkovic et al. have given an elegant method to convert a regular expression of size $n$ into an $\epsilon$-free nondeterministic finite automaton having $O\left(n\right)$ states and $O\left(n{log}^2\left(n\right)\right)$ transitions. This method has been implemented efficiently in $O\left(n{log}^2\left(n\right)\right)$ time by C. Hagenah and A. Muscholl. In this paper we extend this method to weighted regular expressions and we show that it can be achieved in $O\left(n{log}^2\left(n\right)\right)$ time.

J. Hromkovic . have given an elegant method to convert a regular expression of size into an -free nondeterministic finite automaton having states and log ) transitions. This method has been implemented efficiently in log ) time by C. Hagenah and A. Muscholl. In this paper we extend this method to weighted regular expressions and we show that it can be achieved in log ) time.