Efficient weighted expressions conversion
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, p. 285-307
J. Hromkovic et al. have given an elegant method to convert a regular expression of size n into an ε-free nondeterministic finite automaton having O(n) states and O(nlog 2 (n)) transitions. This method has been implemented efficiently in O(nlog 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(nlog 2 (n)) time.
@article{ITA_2008__42_2_285_0,
     author = {Ouardi, Faissal and Ziadi, Djelloul},
     title = {Efficient weighted expressions conversion},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     pages = {285-307},
     doi = {10.1051/ita:2007035},
     zbl = {1157.68042},
     mrnumber = {2401263},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2008__42_2_285_0}
}
Ouardi, Faissal; Ziadi, Djelloul. Efficient weighted expressions conversion. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, pp. 285-307. doi : 10.1051/ita:2007035. http://www.numdam.org/item/ITA_2008__42_2_285_0/

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

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

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

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

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

[6] J.-M. Champarnaud and D. Ziadi, Computing the equation automaton of regular expression in O(s 2 ) 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 1904574 | Zbl 0990.68085

[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 2102520 | Zbl 1098.68066

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

[9] C. Hagenah and A. Muscholl, Computing ε-free NFA from regular expression in O(nlog 2 (n)) time. RAIRO-Theor. Inf. Appl. 34 (2000) 257-277. | Numdam | MR 1809860 | Zbl 0971.68091

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

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

[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 2064469 | Zbl 1014.68082

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

[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 2064481

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

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

[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 1440674 | Zbl 0915.68123