RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

| Abstract | PDF (368.2 KB) | References |

RAIRO-Theor. Inf. Appl. 42, 285-307 (2008)
DOI: 10.1051/ita:2007035

Efficient weighted expressions conversion

Faissal Ouardi and Djelloul Ziadi

L.I.T.I.S., University of Rouen, France; Faissal.Ouardi@univ-rouen.fr; Djelloul.Ziadi@univ-rouen.fr

(Received March 23, 2005. Accepted June 22, 2007. Published online 6 September 2007.)

Abstract
J. Hromkovic et al. have given an elegant method to convert a regular expression of size n into an $\varepsilon$ -free nondeterministic finite automaton having O(n) states and $O(n\log^2(n))$ transitions. This method has been implemented efficiently in $O(n\log^2(n))$ 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(n\log^2(n))$ time.

Mathematics Subject Classification. 03D15, 68Q45

Key words: Formal languages and automata -- complexity of computation

© EDP Sciences 2007