Efficient weighted expressions conversion

Faissal Ouardi; Djelloul Ziadi

RAIRO - Theoretical Informatics and Applications (2007)

  • 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(nlog2(n)) transitions. This method has been implemented efficiently in O(nlog2(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(nlog2(n)) time.

How to cite

top

Ouardi, Faissal, and Ziadi, Djelloul. "Efficient weighted expressions conversion." RAIRO - Theoretical Informatics and Applications 42.2 (2007): 285-307. <http://eudml.org/doc/92872>.

@article{Ouardi2007,
abstract = { 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(nlog2(n)) transitions. This method has been implemented efficiently in O(nlog2(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(nlog2(n)) time. },
author = {Ouardi, Faissal, Ziadi, Djelloul},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Formal languages and automata; complexity of computation; formal series; weighted regular expression; weighted automaton},
language = {eng},
month = {9},
number = {2},
pages = {285-307},
publisher = {EDP Sciences},
title = {Efficient weighted expressions conversion},
url = {http://eudml.org/doc/92872},
volume = {42},
year = {2007},
}

TY - JOUR
AU - Ouardi, Faissal
AU - Ziadi, Djelloul
TI - Efficient weighted expressions conversion
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/9//
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 ε-free nondeterministic finite automaton having O(n) states and O(nlog2(n)) transitions. This method has been implemented efficiently in O(nlog2(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(nlog2(n)) time.
LA - eng
KW - Formal languages and automata; complexity of computation; formal series; weighted regular expression; weighted automaton
UR - http://eudml.org/doc/92872
ER -

References

top
  1. V. Antimirov, Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci.155 (1996) 291–319.  
  2. A. Brüggemann-Klein, Regular expressions into finite automata. Theoret. Comput. Sci.120 (1993) 197–213.  
  3. J. Berstel and C. Reutenauer. Rational series and their languages. Springer-Verlag, Berlin (1988).  
  4. P. Caron and M. Flouret, Glushkov construction for series: the non commutative case. Int. J. Comput. Math.80 (2003) 457–472.  
  5. P. Caron and D. Ziadi, Characterization of Glushkov automata. Theoret. Comput. Sci.231 (2000) 75–90.  
  6. J.-M. Champarnaud and D. Ziadi, Computing the equation automaton of regular expression in O(s2) 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.  
  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.  
  8. V.-M. Glushkov, The abstract theory of automata. Russian Math. Surveys16 (1961) 1–53.  
  9. C. Hagenah and A. Muscholl, Computing ε-free NFA from regular expression in O(nlog2(n)) time. RAIRO-Theor. Inf. Appl.34 (2000) 257–277.  
  10. U. Hebisch and H.J. Weinert, Semirings: algebraic theory and applications in computer science. World Scientific, Singapore (1993).  
  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.  
  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.  
  13. W. Kuich and J. Salomaa, Semirings, automata, languages. Springer-Verlag, Berlin (1986).  
  14. S. Lombardy and J. Sakarovitch, Derivatives of regular expression with multiplicity, Proc. of MFCS 2002. Lect. Notes Comput. Sci.2420 (2002) 471–48.  
  15. R.F. McNaughton and H. Yamada, Regular expressions and state graphs for automata. IEEE T. Electron. Comput.9 (1960) 39–47.  
  16. M.P. Schützenberger, On the definition of a family of automata. Inform. Control6 (1961) 245–270.  
  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 Stevin4 (1997) 177–203.  

NotesEmbed ?

top

You must be logged in to post comments.