A general framework for the derivation of regular expressions
Caron, Pascal ; Champarnaud, Jean-Marc ; Mignot, Ludovic
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014), p. 281-305 / Harvested from Numdam
Access to full text

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.

Publié le : 2014-01-01
DOI : https://doi.org/10.1051/ita/2014010
Classification:  68Q45 
@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},
     volume = {48},
     year = {2014},
     pages = {281-305},
     doi = {10.1051/ita/2014010},
     mrnumber = {3302489},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 281-305. doi : 10.1051/ita/2014010. http://gdmltest.u-ga.fr/item/ITA_2014__48_3_281_0/

[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] V.M. Antimirov and P.D. Mosses, Rewriting extended regular expressions. Theoret. Comput. Sci. 143 (1995) 51-72. | MR 1330673 | Zbl 0873.68104

[3] G. Berry and R. Sethi, From regular expressions to deterministic automata. Theoret. Comput. Sci. 48 (1986) 117-126. | MR 889664 | Zbl 0626.68043

[4] J.A. Brzozowski, Derivatives of regular expressions. J. Assoc. Comput. Mach. 11 (1964) 481-494. | MR 174434 | Zbl 0225.94044

[5] J.A. Brzozowski, Quotient complexity of regular languages. J. Automata, Languages and Combinatorics 15 (2010) 71-89.

[6] J.A. Brzozowski and E.L. Leiss, On equations for regular languages, finite automata, and sequential networks. Theoret. Comput. Sci. 10 (1980) 19-35. | MR 549752 | Zbl 0415.68023

[7] P. Caron, J.-M. Champarnaud and L. Mignot, 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. | Zbl pre05903563

[8] J.-M. Champarnaud, F. Ouardi and D. Ziadi, An efficient computation of the equation K-automaton of a regular K-expression. Fundam. Inform. 90 (2009) 1-16. | MR 2494599 | Zbl 1161.68518

[9] J.-M. Champarnaud and D. Ziadi, Canonical derivatives, partial derivatives, and finite automaton constructions. Theoret. Comput. Sci. 239 (2002) 137-163. | MR 1932893 | Zbl 1061.68109

[10] J. Clarke, An algorithm for RELAX NG validation. Implementation Report (2002).

[11] J.-H. Conway, Regular algebra and finite machines. Chapman and Hall (1971). | Zbl 0231.94041

[12] A. Ginzburg, A procedure for checking equality of regular expressions. J. ACM 14 (1967) 355-362. | Zbl 0155.34501

[13] L. Ilie and S. Yu, Follow automata. Inf. Comput. 186 (2003) 140-162. | MR 2001743 | Zbl 1059.68063

[14] D. Krob, Differentation of K-rational expressions. Internat. J. Algebra Comput. 2 (1992) 57-87. | MR 1167528 | Zbl 0785.68065

[15] S. Lombardy and J. Sakarovitch, Derivatives of rational expressions with multiplicity. Theoret. Comput. Sci. 332 (2005) 141-177. | MR 2122501 | Zbl 1070.68074

[16] M. Might, D. Darais and D. Spiewak, Parsing with derivatives: a functional pearl, in ICFP, edited by M.M.T. Chakravarty, Zh. Hu and O. Danvy. ACM (2011) 189-195.

[17] J. Myhill, Finite automata and the representation of events. WADD TR-57-624 (1957) 112-137.

[18] A. Nerode, Linear automata transformation, in Proc. of AMS 9 (1958) 541-544. | Zbl 0089.33403

[19] S. Owens, J.H. Reppy and A. Turon, Regular-expression derivatives re-examined. J. Funct. Program. 19 (2009) 173-190. | MR 2486568 | Zbl 1163.68317

[20] J. Sakarovitch, 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 2214022 | Zbl 1172.68526

[21] M. Sulzmann and K.Z.M. Lu, Partial derivative regular expression pattern matching. Manuscript (2007).

[22] K. Thompson, Regular expression search algorithm. Comm. ACM 11 (1968) 419-422. | Zbl 0164.46205