scientific article; zbMATH DE number 7651219

DOI10.4230/LIPICS.ESA.2020.80MaRDI QIDQ5874553zbMATH OpenFDO

Authors Philipp Schepper

Publication date 7 February 2023

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

zbMATH Keywords

pattern matchingdichotomyregular expressionfine-grained complexity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A Four Russians algorithm for regular expression pattern matching
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Efficient string matching
• Fast Pattern Matching in Strings
• Faster Regular Expression Matching
• More applications of the polynomial method to algorithm design
• Programming Techniques: Regular expression search algorithm
• Size-depth tradeoffs for Boolean formulae
• Space/time trade-offs in hash coding with allowable errors
• The polynomial method in circuit complexity applied to algorithm design (invited talk)
• Tighter connections between Formula-SAT and shaving logs
• Verifying candidate matches in sparse and wildcard matching

Cited in

(4)

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

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)