PaperlayerView exact revision on arXiv

Source-linked AI summary

Which Regular Expression Patterns are Hard to Match?

Arturs Backurs, Piotr Indyk

arXiv:1511.07070v2cs.CCcs.DS

TL;DR

Regular-expression matching has a general O(mn) algorithm, but substantially faster algorithms are known for some special cases, with no systematic classification of easy and hard expression types. This paper classifies matching and membership by formula depth and shows a depth-dependent complexity dichotomy, while improving the Word Break dynamic-programming bound.

  • Problem

    The general regular-expression algorithm runs in O(mn), and despite faster algorithms for special cases, a systematic classification of tractable and hard types was lacking.

    Source: §1 · pp. 2–3

  • Method

    The paper classifies matching and membership for homogeneous regular-expression formulas by depth and operator type, using upper-bound algorithms and conditional hardness reductions.

    Source: §1 · pp. 3–4

  • Results

    The classification separates near-linear cases from SETH-hard cases across depths two and three, and the Word Break dynamic-programming bound is improved.

    Source: §1 · pp. 3, 4, 7

  • Takeaways & Limitations

    Expression depth and operator type distinguish regular-expression variants with near-linear algorithms from those resistant to strongly sub-quadratic algorithms under SETH.

    Source: §1 · p. 3

    The lower-bound claims are conditional: they rely on SETH via reductions from unbalanced Orthogonal Vectors.

    Source: §2 · p. 8

Abstract

from arXiv · show

Regular expressions constitute a fundamental notion in formal language theory and are frequently used in computer science to define search patterns. A classic algorithm for these problems constructs and simulates a non-deterministic finite automaton corresponding to the expression, resulting in an $O(mn)$ running time (where $m$ is the length of the pattern and $n$ is the length of the text). This running time can be improved slightly (by a polylogarithmic factor), but no significantly faster solutions are known. At the same time, much faster algorithms exist for various special cases of regular expressions, including dictionary matching, wildcard matching, subset matching, word break problem etc. In this paper, we show that the complexity of regular expression matching can be characterized based on its {\em depth} (when interpreted as a formula). Our results hold for expressions involving concatenation, OR, Kleene star and Kleene plus. For regular expressions of depth two (involving any combination of the above operators), we show the following dichotomy: matching and membership testing can be solved in near-linear time, except for "concatenations of stars", which cannot be solved in strongly sub-quadratic time assuming the Strong Exponential Time Hypothesis (SETH). For regular expressions of depth three the picture is more complex. Nevertheless, we show that all problems can either be solved in strongly sub-quadratic time, or cannot be solved in strongly sub-quadratic time assuming SETH. An intriguing special case of membership testing involves regular expressions of the form "a star of an OR of concatenations", e.g., $[a|ab|bc]^*$. This corresponds to the so-called {\em word break} problem, for which a dynamic programming algorithm with a runtime of (roughly) $O(n\sqrt{m})$ is known. We show that the latter bound is not tight and improve the runtime to $O(nm^{0.44\ldots})$.

1 Introduction

The paper classifies regular-expression matching and membership by formula depth, addressing the lack of a systematic account of which pattern types are tractable. It finds sharp differences across depth-two and depth-three types, including a faster algorithm for Word Break.

Our techniques

  • The classification uses homogeneous formula types, and depth-three hardness reductions from Orthogonal Vectors use operator-specific gadgets and transformations between related expression types.For example, hardness transfers between ·+· and ·|·, and between ·+| and ·|+.Source: §1 · pp. 3, 6, 7

Results

  • At depth two, nearly all matching and membership cases are near-linear; concatenations of stars are SETH-hard, while concatenations of pluses admit O(n log^2 m) matching.Depth-two membership is mostly linear, while several matching types have nontrivial algorithms.Source: §1 · p. 3
  • At depth three, matching types beginning with concatenation are SETH-hard; types beginning with star are linear, while plus inherits complexity from the final two operators.Types beginning with OR are either SETH-hard when followed by concatenation or linear-time solvable.Source: §1 · p. 3

Our techniques

  • For depth-two upper bounds, concatenations of ORs reduce to superset matching, ORs of sequences to dictionary matching, and plus-concatenation to standard pattern matching.The near-linear algorithm for concatenations of pluses reduces to subset matching and wildcard matching.Source: §1 · p. 4

Results

  • For depth-three membership, concatenation-leading types are SETH-hard, most OR-leading types are linear, and star- or plus-leading types include the Word Break cases.The OR-leading exception is |·∗; ∗|· and +|· correspond to Word Break.Source: §1 · pp. 4, 7
  • The Word Break dynamic program improves from roughly O(nm^0.5 log^O(1) n) to roughly O(nm^(0.5-1/18)) using convolutions, with randomized one-sided error.The algorithm precomputes information reused during the dynamic program.Source: §1 · p. 7

2 Preliminaries

The preliminaries define regular-expression syntax and depth-based types, then introduce Orthogonal Vectors as the basis for the paper’s reductions. They also establish that some depth-three types reduce to depth-two types.

2 Preliminaries

  • The reductions use unbalanced Orthogonal Vectors: determine whether a vector from A has zero dot product with a vector from B.A faster-than-(MN)^(1−δ) algorithm for the stated unbalanced instances would violate SETH, according to the cited results.Source: §2 · p. 8
  • Subset matching requires each pattern-location set to be contained in the aligned text-location set; superset matching reverses that inclusion, while wildcard matching permits either aligned symbol to be a wildcard.Source: §2 · p. 8
  • Regular expressions combine symbols using concatenation, OR, plus, and star; these respectively concatenate languages, take their union, or allow one-or-more and zero-or-more repetitions.The empty word is included in the language of a starred expression.Source: §2 · pp. 8–9
  • A homogeneous depth-k expression has the same operator at each tree level, and its type records those level operators.Expressions are represented as rooted labeled trees; internal nodes need not have a fixed number of children.Source: §2 · p. 9
  • For types beginning with plus, or with OR followed by plus, plus can be removed because p+ occurs in the text exactly when p does.Source: §2 · p. 9

3 Reductions for the Pattern Matching problem

This section reduces orthogonal-vector detection to regular-expression substring matching across four pattern types, using constructions linear in the vector-set dimensions and sizes. For the “·+·” type, vector gadgets encode orthogonality so that an orthogonal pair yields a substring derivable from the pattern.

3.1 Hardness for type “|·|”

  • For type “|·|”, a pattern and text of sizes O(Md) and O(Nd), constructible in O(Nd) time, encode an orthogonal pair exactly as a substring derivable from the pattern.The construction works for A and B subsets of {0, 1}^d.Source: §3.1 · p. 10

3.2 Hardness for type “|·+”

  • For type “|·+”, a pattern and text of sizes O(Md) and O(Nd), constructible in O(Nd) time, encode an orthogonal pair exactly as a substring derivable from the pattern.The construction works for A and B subsets of {0, 1}^d.Source: §3.2 · p. 11

3.3 Hardness for type “·∗”

  • For type “·∗”, when M ≤ N, a pattern and text of sizes O(Md) and O(Nd), constructible in O(Nd) time, encode an orthogonal pair exactly as a substring derivable from the pattern.The coordinate gadgets derive a text vector gadget from a pattern vector gadget exactly when their vectors are orthogonal.Source: §3.3 · pp. 12–13

3.4 Hardness for type “·+·”

  • For type “·+·”, when M ≤ N, a pattern formed by concatenating “+” of sequences and a text of sizes O(Md) and O(Nd) encode an orthogonal pair exactly as a derivable substring.The construction takes O(Nd) time.Source: §3.4 · p. 14
  • A text vector gadget VG'(b) can be derived from VG(a) if and only if a · b = 0.Coordinate gadget CG'(v, i) can be derived from CG(u, i) exactly when uv = 0.Source: §3.4 · p. 15
  • If A and B contain an orthogonal pair, a substring of t can be derived from p.This is the sufficiency direction established by Lemma 7; the supplied passages do not include the converse proof.Source: §3.4 · p. 15

V G(1d) V G0 V G(ai) V G0

The reductions encode Orthogonal Vectors instances as regular-expression matching or membership problems across several operator types. Their gadget constructions and transformations establish the corresponding hardness results.

V G(1d) V G0 V G(ai) V G0

  • The gadget-alignment argument proves that deriving a substring from the pattern implies an orthogonal vector pair, completing the reduction’s reverse direction.The proof uses the pattern groups and their alignment with text groups to identify a pair whose inner product is zero.Source: V G(1d) V G0 V G(ai) V G0 · pp. 16–17

3.5 Hardness for type “·|·”

  • Replacing bounded repetitions in the “·+·” construction with finite ORs preserves the reduction and yields hardness for type “·|·”.The transformed pattern remains no more expressive than the original, while retaining the derivations needed for the reduction.Source: §3.5 · pp. 17–18

3.6 Hardness for type “·+|”

  • A construction of type “·+|” matches a substring of the text if and only if the input sets contain an orthogonal vector pair.The construction takes O(Nd) time, with pattern size O(Md) and text size O(Nd).Source: §3.6 · p. 18

3.7 Hardness for type “·|+”

  • A construction of type “·|+” derives a substring of the text if and only if the input sets contain an orthogonal vector pair.The proof adapts the “·+|” construction by replacing an OR of symbols under plus with an OR of their individual plus expressions.Source: §3.7 · p. 20

4 Reductions for the Membership problem

The membership reductions encode Orthogonal Vectors instances for five regular-expression types, showing that membership can express the corresponding orthogonality test.

4.1 Hardness for type “·∗”

  • For type “·∗”, membership holds exactly when the input sets contain an orthogonal vector pair.The reduction constructs the pattern and text in O(Nd) time, with both sizes bounded by O(Nd).Source: §4.1 · p. 21

4.2 Hardness for type “·+·”

  • For type “·+·”, a constructed pattern derives the text exactly when the input sets contain an orthogonal vector pair.The proof wraps the substring-matching reduction with expressions that derive the text’s remaining prefix and suffix.Source: §4.2 · pp. 21–22

4.3 Hardness for type “·|·”

  • For type “·|·”, the reduction constructs a pattern that derives the text exactly when the input sets contain an orthogonal vector pair.It modifies the “·+·” pattern while retaining the same text.Source: §4.3 · p. 23

4.4 Hardness for type “·+|”

  • For type “·+|”, membership holds exactly when the input sets contain an orthogonal vector pair.The construction adapts the earlier substring-matching reduction and adds plus expressions to derive the text’s remaining prefix and suffix.Source: §4.4 · p. 23

4.5 Hardness for type “·|+”

  • For type “·|+”, the constructed pattern derives the text exactly when the input sets contain an orthogonal vector pair.The reduction adapts the type “·|+” matching construction and provides expressions for the text’s remaining prefix and suffix.Source: §4.5 · p. 24

5 Algorithms

The section develops algorithms and reductions for several regular-expression problems, including a faster Word Break algorithm and run-length-encoded matching methods for specified pattern types.

5.1 Algorithm for the Word Break problem

5.2 Algorithm for type “·+”

  • In O(|p|+|t|) time, matching a pattern of type “·+” reduces to one Subset Matching instance and one Wildcard Matching instance.The reductions encode maximal runs of equal symbols; their combined results enforce symbol-count lower bounds and exact counts for runs without plus operators.Source: §5.2 · pp. 29–30

5.3 Algorithm for types “|∗·” and “|+·”

  • O(|p|+|t|) time decides membership for patterns of type “|∗·” or “|+·”.After linear-time suffix-tree and lowest-common-ancestor preprocessing, each repeated alternative is checked by testing whether its sequence is a prefix of the text and divides the text length; the plus case excludes empty text.Source: §5.3 · p. 30

5.4 Algorithms for types “|·+” and “∗·+”

  • O(|p|+|t|) time decides membership for patterns of type “|·+” or “∗·+”.Source: §5.4 · p. 30
  • For type “|·+”, encode each alternative’s runs as exact or minimum symbol counts, then test whether the text’s runs satisfy the stated alignment conditions.The text is run-length encoded, and each alternative is processed in O(|p_i|) time.Source: §5.4 · pp. 30–31
  • For type “∗·+”, the algorithm encodes the repeated expression’s runs and handles cases according to whether its first and last runs have different or the same types.When the endpoint types are the same, derivability requires a repetition-count condition and compatibility with a constructed sequence that merges the text’s first and last runs.Source: §5.4 · p. 31
  • When the first and last runs of the repeated expression have different types, the text’s run count must be divisible by the expression’s run count.The method also compares the text’s runs with a repeated encoding of the expression.Source: §5.4 · p. 31
  • Both “∗·+” subcases run in O(|p| + |t|) time.Source: §5.4 · p. 31

Related papers

Loading 1511.07070v2…