scientific article; zbMATH DE number 7651219

DOI10.4230/LIPICS.ESA.2020.80MaRDI QIDQ5874553FDOQ5874553

Authors: Philipp Schepper 

Publication date: 7 February 2023

Full work available at URL: https://arxiv.org/abs/2008.02769

Title of this publication is not available (Why is that?)

zbMATH Keywords

pattern matchingdichotomyregular expressionfine-grained complexity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Efficient string matching
• Size-depth tradeoffs for Boolean formulae
• Space/time trade-offs in hash coding with allowable errors
• Fast Pattern Matching in Strings
• Verifying candidate matches in sparse and wildcard matching
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• Programming Techniques: Regular expression search algorithm
• Faster Regular Expression Matching
• A Four Russians algorithm for regular expression pattern matching
• Title not available (Why is that?)
• More Applications of the Polynomial Method to Algorithm Design
• Title not available (Why is that?)

Cited In (4)

• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Complexity of regex crosswords
• Succinctness of the Complement and Intersection of Regular Expressions

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874553)