Campus Event Calendar
Event Entry
What and Who
Tight Bounds for Regular Expression Pattern Matching and Membership (Master thesis)
Philipp Schepper
Fachrichtung Informatik - Saarbrücken
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 16 January 2020
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
The classical O(nm) time algorithms for regular expression pattern matching and membership can be improved by a factor of about log^{3/2}(n).
Instead of focusing on general patterns we focus on homogeneous patterns of bounded depth in this thesis only.
For them a classification splitting the types in easy (strongly sub-quadratic) and hard (essentially quadratic time under SETH) is known.
We take a fine-grained look at the hard pattern types from this classification and show that few types allow super-poly-logarithmic improvements while the algorithms for the other pattern types can only be improved by a constant number of log-factors, assuming the Formula-SAT Hypothesis.
Contact
Karl Bringmann
--email hidden
passcode not visible
logged in users only
Karl Bringmann, 01/07/2020 07:56 -- Created document.