Efficient weighted expressions conversion

Ouardi, Faissal; Ziadi, Djelloul

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, pp. 285-307.

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.

Classification : 03D15, 68Q45
Mots clés : formal languages and automata, complexity of computation

[1] V. Antimirov, Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155 (1996) 291-319. | MR | Zbl

[2] A. Brüggemann-Klein, Regular expressions into finite automata. Theoret. Comput. Sci. 120 (1993) 197-213. | MR | Zbl

[3] J. Berstel and C. Reutenauer. Rational series and their languages. Springer-Verlag, Berlin (1988). | MR | Zbl

[4] P. Caron and M. Flouret, Glushkov construction for series: the non commutative case. Int. J. Comput. Math. 80 (2003) 457-472. | MR | Zbl

[5] P. Caron and D. Ziadi, Characterization of Glushkov automata. Theoret. Comput. Sci. 231 (2000) 75-90. | MR | Zbl

[6] J.-M. Champarnaud and D. Ziadi, Computing the equation automaton of regular expression in $O\left(s^2\right)$ space and time, in CPM 2001, Combinatorial Pattern Matching, edited by A. Amir and G.M. Landau. Lect. Notes Comput. Sci. 2089 (2001) 157-168. | MR | Zbl

[7] J.-M. Champarnaud, E. Laugerotte, F. Ouardi and D. Ziadi, From regular weighted expressions to finite automata. Int. J. Fond. Comput. Sci. 15 (2004) 687-700. | MR | Zbl

[8] V.-M. Glushkov, The abstract theory of automata. Russian Math. Surveys 16 (1961) 1-53. | MR | Zbl

[9] C. Hagenah and A. Muscholl, Computing $\epsilon$-free NFA from regular expression in $O\left(n{log}^2\left(n\right)\right)$ time. RAIRO-Theor. Inf. Appl. 34 (2000) 257-277. | Numdam | MR | Zbl

[10] U. Hebisch and H.J. Weinert, Semirings: algebraic theory and applications in computer science. World Scientific, Singapore (1993). | MR | Zbl

[11] U. Hromkovic, J. Seibert and T. Wilke, Translating regular expressions into small $\epsilon$-free nondeterministic finite automata. J. Comput. System Sci. 62 (2001) 565-588. | MR | Zbl

[12] L. Ilie and S. Yu, Algorithms for computing small NFAs, in Proc 27th MFCS, Warszawa, 2002, edited by K. Diks and W. Rytter. Lect. Notes Comput. Sci. (2002) 328-340. | MR | Zbl

[13] W. Kuich and J. Salomaa, Semirings, automata, languages. Springer-Verlag, Berlin (1986). | MR | Zbl

[14] S. Lombardy and J. Sakarovitch, Derivatives of regular expression with multiplicity, Proc. of MFCS 2002. Lect. Notes Comput. Sci. 2420 (2002) 471-48. | MR

[15] R.F. Mcnaughton and H. Yamada, Regular expressions and state graphs for automata. IEEE T. Electron. Comput. 9 (1960) 39-47. | Zbl

[16] M.P. Schützenberger, On the definition of a family of automata. Inform. Control 6 (1961) 245-270. | MR | Zbl

[17] D. Ziadi, Algorithmique parallèle et séquentielle des automates. Thesis, LIR report, Université de Rouen (1996).

[18] D. Ziadi, Quelques aspects théoriques et algorithmiques des automates. Thesis, Université de Rouen (2002).

[19] D. Ziadi, J.-L. Ponty and J.-M. Champarnaud, Passage d'une expression rationnelle à un automate fini non-déterministe. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 177-203. | MR | Zbl