Ouardi, Faissal; Ziadi, Djelloul
Efficient weighted expressions conversion
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2 , p. 285-307
Zbl 1157.68042 | MR 2401263
doi : 10.1051/ita:2007035
URL stable : http://www.numdam.org/item?id=ITA_2008__42_2_285_0

Classification:  03D15,  68Q45
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.

Bibliographie

[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