(2020) Fine-Grained Complexity of Regular Expression Pattern Matching and Membership.
In: European Symposium on Algorithms.
Conference:
ESA European Symposium on Algorithms
|
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.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Conference: | ESA European Symposium on Algorithms |
| Depositing User: | Philipp Schepper |
| Date Deposited: | 22 Jan 2021 09:02 |
| Last Modified: | 12 Oct 2022 19:02 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3345 |
Actions
Actions (login required)
 |
View Item |