Fine-Grained Complexity of Regular Expression Pattern Matching and Membership

Schepper, Philipp
(2020) Fine-Grained Complexity of Regular Expression Pattern Matching and Membership.
In: UNSPECIFIED.
Conference: ESA European Symposium on Algorithms

[img]
Preview
Text
LIPIcs-ESA-2020-80.pdf - Published Version
Available under License Creative Commons Attribution.

Download (896kB) | Preview

Abstract

The currently fastest algorithm for regular expression pattern matching and membership improves the classical O(nm) time algorithm by a factor of about log^{3/2}n. Instead of focussing on general patterns we analyse homogeneous patterns of bounded depth in this work. For them a classification splitting the types in easy (strongly sub-quadratic) and hard (essentially quadratic time under SETH) is known. We take a very fine-grained look at the hard pattern types from this classification and show a dichotomy: 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.

Actions

Actions (login required)

View Item View Item