Efficient weighted expressions conversion

Ouardi, Faissal; Ziadi, Djelloul

doi:10.1051/ita:2007035

Ouardi, Faissal ; Ziadi, Djelloul

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

Résumé

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 (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.

MR Zbl

DOI : 10.1051/ita:2007035

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

@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},
     pages = {285--307},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     doi = {10.1051/ita:2007035},
     mrnumber = {2401263},
     zbl = {1157.68042},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007035/}
}

TY  - JOUR
AU  - Ouardi, Faissal
AU  - Ziadi, Djelloul
TI  - Efficient weighted expressions conversion
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 285
EP  - 307
VL  - 42
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007035/
DO  - 10.1051/ita:2007035
LA  - en
ID  - ITA_2008__42_2_285_0
ER  -

%0 Journal Article
%A Ouardi, Faissal
%A Ziadi, Djelloul
%T Efficient weighted expressions conversion
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 285-307
%V 42
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007035/
%R 10.1051/ita:2007035
%G en
%F 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/articles/10.1051/ita:2007035/

Bibliographie
Cité par

[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 (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 | 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 $ε$ -free NFA from regular expression in $O (n {log}^{2} (n))$ 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 $ε$ -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

Cité par Sources :