A dichotomy for regular expression membership testing

DOI10.1109/FOCS.2017.36MaRDI QIDQ6946352zbMATH OpenFDO

Authors Kasper Green Larsen, Allan Grønlund, Karl Bringmann

Publication date 6 August 2025

Full work available at URL https://hdl.handle.net/11858/00-001M-0000-002C-5300-F

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(5)

• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Co-lexicographically ordering automata and regular languages. I
• Fine-grained hardness for edit distance to a fixed sequence
• Faster combinatorial k-clique algorithms
• Text indexing for simple regular expressions

This page was built for publication: A dichotomy for regular expression membership testing

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