Membership Testing for Semantic Regular Expressions
summary
Presents a concrete two-pass NFA-based algorithm that converts a SemRE and input into a linear-size query graph then runs DP to check satisfiable paths, proving non-nested cases run in O(|r|^2 |w|^2) while general nested queries hit a cubic bottleneck from boolean matrix–vector work. Experiments show the implementation massively outperforms a DP baseline, incurs ≈2× overhead over oracle interaction and makes ≈51% fewer oracle calls, and a reduction from triangle finding yields hardness and an Ω(|w|^2) oracle-query lower bound.
AI-written summary · about
chapters (8)
- 0:00Introduction to semantic regular expressions
- 2:26Membership testing problem
- 4:52Extending NFA for queries
- 7:19Query graph construction
- 13:16Performance analysis
- 15:40Lower bound proof
- 18:07Conclusion
- 18:29Q&A
related talks
16mScalable Synthesis of Regular Expressions From Only Positive Examples
22mReasoning about 'Reasoning about Reasoning' Semantics and Contextual Equivalence
35mLocal Statistics, Semidefinite Programming, and Community Detection II
31mARENA: Enhancing Abstract Refinement for Neural Network Verification
36mEnhanced and Efficient Reasoning in Large Language Models
30mComputational Barriers For Learning Some Generalized Linear Models
44mAutomated Scientific Discovery Using Insights from Problem Structure
01h 03mUnderstanding ReLU Networks Through Graph Problems and Polyhedra