Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.80
URN: urn:nbn:de:0030-drops-129464
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12946/
Schepper, Philipp
Fine-Grained Complexity of Regular Expression Pattern Matching and Membership
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{schepper:LIPIcs:2020:12946,
author = {Philipp Schepper},
title = {{Fine-Grained Complexity of Regular Expression Pattern Matching and Membership}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {80:1--80:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12946},
URN = {urn:nbn:de:0030-drops-129464},
doi = {10.4230/LIPIcs.ESA.2020.80},
annote = {Keywords: Fine-Grained Complexity, Regular Expression, Pattern Matching, Dichotomy}
}
| Keywords: | Fine-Grained Complexity, Regular Expression, Pattern Matching, Dichotomy | |
| Seminar: | 28th Annual European Symposium on Algorithms (ESA 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 26.08.2020 |
