License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12946/
Go to the corresponding LIPIcs Volume Portal

Schepper, Philipp

Fine-Grained Complexity of Regular Expression Pattern Matching and Membership

pdf-format:
LIPIcs-ESA-2020-80.pdf (0.9 MB)

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
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI