Efficient weighted expressions conversion

Ouardi, Faissal ; Ziadi, Djelloul

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 285-307 / Harvested from Numdam

Résumé

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.

Détail

Publié le : 2008-01-01

MR 2401263 | Zbl 1157.68042

DOI : https://doi.org/10.1051/ita:2007035
Classification:  03D15,  68Q45

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 $\varepsilon $-free NFA from regular expression in $O(n\log ^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 $\varepsilon $-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