Postal address
Department of Theoretical Physics, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India.
Secretariat phones
+91-22-2278 2244 +91-22-2278 2156
+91-22-2278 2777 +91-22-2280 4611 +91-22-2280 4610
Secretariat email
"theophys" The mailhost for DTP is

Please write to cmspjc at theory dot tifr dot res dot in for getting email announcements and any suggestions regarding CMSP Journal Club.

Condensed Matter and Statistical Physics Journal Club

Talk Details

Title Derivatives of Regular Expressions
Speaker Abhay Parvate
Date Wed, 01 Jun 2011
Time 14:30
Venue A 304


In the advent of functional programming, the interest in the concept of derivatives of regular expressions [1] has been revived [2]. Apart from being elegant, it seems to be the only automata way of handling extended regular expressions, i. e. expressions including logical AND and NOT, which then can describe any boolean operations.

In this talk the notion of a derivative of a regular expression [1] will be introduced and the properties of derivatives will be discussed. This will lead in a natural way to the construction of a deterministic finite automaton from an extended regular expression.

[1] J. A. Brzozowski, "Derivatives of regular expressions", Journal of the Association for Computing Machinery, 11(4) (1964) 481-494

[2] Scott Owens, John Reppy, Aaron Turon, "Regular expression derivatives reexamined", Journal of Functional Programming, 19(2) (2009) 173-190