2012/12/20 by Pascal Caron, Jean-Marc Champarnaud, Ludovic Mignot
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algebra over a field #Algorithm #Automaton #Chemical Synthesis and Analysis #Computation #Computer science #Construct (python library) #Expression (computer science) #Formalism (music) #Logic, programming, and type systems #Mathematical analysis #Mathematics #Programming language #Pure mathematics #Regular expression #Scheme (mathematics) #Set (abstract data type) #Theoretical computer science #cs.FL #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.1051/ita/2014010
published as RAIRO-Theor. Inf. Appl. 48 (2014) 281-305 · 22 pages
arxiv created 2012/12/20 · openalex publication_date 2014/05/27 · arxiv updated 2019/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.