The aim of this paper is to design a theoretical framework that allows us to perform the computation of regular expression derivatives through a space of generic structures. Thanks to this formalism, the main properties of regular expression derivation, such as the finiteness of the set of derivatives, need only be stated and proved one time, at the top level. Moreover, it is shown how to construct an alternating automaton associated with the derivation of a regular expression in this general framework. Finally, Brzozowski's derivation and Antimirov's derivation turn out to be a particular case of this general scheme and it is shown how to construct a DFA, a NFA and an AFA for both of these derivations.
Mots-clés : regular expressions, alternating automata, derivation, partial derivation
@article{ITA_2014__48_3_281_0, author = {Caron, Pascal and Champarnaud, Jean-Marc and Mignot, Ludovic}, title = {A general framework for the derivation of regular expressions}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {281--305}, publisher = {EDP-Sciences}, volume = {48}, number = {3}, year = {2014}, doi = {10.1051/ita/2014010}, mrnumber = {3302489}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2014010/} }
TY - JOUR AU - Caron, Pascal AU - Champarnaud, Jean-Marc AU - Mignot, Ludovic TI - A general framework for the derivation of regular expressions JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2014 SP - 281 EP - 305 VL - 48 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2014010/ DO - 10.1051/ita/2014010 LA - en ID - ITA_2014__48_3_281_0 ER -
%0 Journal Article %A Caron, Pascal %A Champarnaud, Jean-Marc %A Mignot, Ludovic %T A general framework for the derivation of regular expressions %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 281-305 %V 48 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2014010/ %R 10.1051/ita/2014010 %G en %F ITA_2014__48_3_281_0
Caron, Pascal; Champarnaud, Jean-Marc; Mignot, Ludovic. A general framework for the derivation of regular expressions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 3, pp. 281-305. doi : 10.1051/ita/2014010. http://archive.numdam.org/articles/10.1051/ita/2014010/
[1] Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155 (1996) 291-319. | MR | Zbl
,[2] Rewriting extended regular expressions. Theoret. Comput. Sci. 143 (1995) 51-72. | MR | Zbl
and ,[3] From regular expressions to deterministic automata. Theoret. Comput. Sci. 48 (1986) 117-126. | MR | Zbl
and ,[4] Derivatives of regular expressions. J. Assoc. Comput. Mach. 11 (1964) 481-494. | MR | Zbl
,[5] Quotient complexity of regular languages. J. Automata, Languages and Combinatorics 15 (2010) 71-89.
,[6] On equations for regular languages, finite automata, and sequential networks. Theoret. Comput. Sci. 10 (1980) 19-35. | MR | Zbl
and ,[7] Partial derivatives of an extended regular expression, in LATA, vol. 6638 of Lect. Notes Comput. Sci. Edited by A.H. Dediu, S. Inenaga and C. Martín-Vide. Springer (2011) 179-191.
, and ,[8] An efficient computation of the equation K-automaton of a regular K-expression. Fundam. Inform. 90 (2009) 1-16. | MR | Zbl
, and ,[9] Canonical derivatives, partial derivatives, and finite automaton constructions. Theoret. Comput. Sci. 239 (2002) 137-163. | MR | Zbl
and ,[10] An algorithm for RELAX NG validation. Implementation Report (2002).
,[11] Regular algebra and finite machines. Chapman and Hall (1971). | Zbl
,[12] A procedure for checking equality of regular expressions. J. ACM 14 (1967) 355-362. | Zbl
,[13] Follow automata. Inf. Comput. 186 (2003) 140-162. | MR | Zbl
and ,[14] Differentation of K-rational expressions. Internat. J. Algebra Comput. 2 (1992) 57-87. | MR | Zbl
,[15] Derivatives of rational expressions with multiplicity. Theoret. Comput. Sci. 332 (2005) 141-177. | MR | Zbl
and ,[16] Parsing with derivatives: a functional pearl, in ICFP, edited by M.M.T. Chakravarty, Zh. Hu and O. Danvy. ACM (2011) 189-195.
, and ,[17] Finite automata and the representation of events. WADD TR-57-624 (1957) 112-137.
,[18] Linear automata transformation, in Proc. of AMS 9 (1958) 541-544. | Zbl
,[19] Regular-expression derivatives re-examined. J. Funct. Program. 19 (2009) 173-190. | MR | Zbl
, and ,[20] The language, the expression, and the (small) automaton, in CIAA, vol. 3845 of Lect. Notes Comput. Sci. Edited by J. Farré, I. Litovsky and S. Schmitz. Springer (2005) 15-30. | MR | Zbl
,[21] Partial derivative regular expression pattern matching. Manuscript (2007).
and ,[22] Regular expression search algorithm. Comm. ACM 11 (1968) 419-422. | Zbl
,Cité par Sources :