Efficient weighted expressions conversion

Faissal Ouardi; Djelloul Ziadi

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2008)

  • Volume: 42, Issue: 2, page 285-307
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Ouardi, Faissal, and Ziadi, Djelloul. "Efficient weighted expressions conversion." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 42.2 (2008): 285-307. <http://eudml.org/doc/245363>.

@article{Ouardi2008,
abstract = {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.},
author = {Ouardi, Faissal, Ziadi, Djelloul},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {formal languages and automata; complexity of computation; formal series; weighted regular expression; weighted automaton},
language = {eng},
number = {2},
pages = {285-307},
publisher = {EDP-Sciences},
title = {Efficient weighted expressions conversion},
url = {http://eudml.org/doc/245363},
volume = {42},
year = {2008},
}

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
PB - EDP-Sciences
VL - 42
IS - 2
SP - 285
EP - 307
AB - 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.
LA - eng
KW - formal languages and automata; complexity of computation; formal series; weighted regular expression; weighted automaton
UR - http://eudml.org/doc/245363
ER -

References

top
  1. [1] V. Antimirov, Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155 (1996) 291–319. Zbl0872.68120MR1379579
  2. [2] A. Brüggemann-Klein, Regular expressions into finite automata. Theoret. Comput. Sci. 120 (1993) 197–213. Zbl0811.68096MR1247207
  3. [3] J. Berstel and C. Reutenauer. Rational series and their languages. Springer-Verlag, Berlin (1988). Zbl0668.68005MR971022
  4. [4] P. Caron and M. Flouret, Glushkov construction for series: the non commutative case. Int. J. Comput. Math. 80 (2003) 457–472. Zbl1033.68058MR1983304
  5. [5] P. Caron and D. Ziadi, Characterization of Glushkov automata. Theoret. Comput. Sci. 231 (2000) 75–90. Zbl0952.68084MR1732178
  6. [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. Zbl0990.68085MR1904574
  7. [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. Zbl1098.68066MR2102520
  8. [8] V.-M. Glushkov, The abstract theory of automata. Russian Math. Surveys 16 (1961) 1–53. Zbl0104.35404MR138529
  9. [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. Zbl0971.68091MR1809860
  10. [10] U. Hebisch and H.J. Weinert, Semirings: algebraic theory and applications in computer science. World Scientific, Singapore (1993). Zbl0934.16046MR1704233
  11. [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. Zbl1014.68093MR1837505
  12. [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. Zbl1014.68082MR2064469
  13. [13] W. Kuich and J. Salomaa, Semirings, automata, languages. Springer-Verlag, Berlin (1986). Zbl0582.68002MR817983
  14. [14] S. Lombardy and J. Sakarovitch, Derivatives of regular expression with multiplicity, Proc. of MFCS 2002. Lect. Notes Comput. Sci. 2420 (2002) 471–48. Zbl1014.68085MR2064481
  15. [15] R.F. McNaughton and H. Yamada, Regular expressions and state graphs for automata. IEEE T. Electron. Comput. 9 (1960) 39–47. Zbl0156.25501
  16. [16] M.P. Schützenberger, On the definition of a family of automata. Inform. Control 6 (1961) 245–270. Zbl0104.00702MR135680
  17. [17] D. Ziadi, Algorithmique parallèle et séquentielle des automates. Thesis, LIR report, Université de Rouen (1996). 
  18. [18] D. Ziadi, Quelques aspects théoriques et algorithmiques des automates. Thesis, Université de Rouen (2002). 
  19. [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. Zbl0915.68123MR1440674

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.