Campus Event Calendar
Event Entry
New for: D3
What and Who
Extended Regular Expressions: Succinctness and Decidability
Dominik Freydenberger
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 22 July 2011
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Most modern implementations of regular expression engines allow the use of variables (also called back references). Unlike "classical" regular expressions, the resulting extended regular expressions (which, in the literature, are also called practical regular expressions, rewbr, or regex) are able to express non-regular languages.
As we shall see, extended regular-expressions cannot be minimized effectively (neither with respect to length, nor number of variables), and the tradeoff in size between extended and ``proper'' regular expressions is not bounded by any recursive function.
Moreover, all these results hold even if the extended regular expressions contain only a single variable.
Contact
Timo Kötzing
--email hidden
passcode not visible
logged in users only
Timo Kötzing, 07/15/2011 19:21 -- Created document.