Scalable Synthesis of Regular Expressions From Only Positive Examples
summary
Synthesis system extends Regex+ with a pragmatic ranking function (Bayesian simplicity vs. specificity) and three search modes: VSA enumeration (complete), beam search (fast, approximate), and an admissible A heuristic* that uses pairwise subproblems. Evaluation uses 412 human-study benchmarks and shows a 90x reduction in memory and 1.9x speedup versus the VSA baseline while retaining optimality guarantees; beam search solves more cases under timeout but loses optimality.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:43Motivating Example
- 1:39Challenges
- 2:53Pragmatic ranking function
- 4:05Studying Reality
- 5:15Walkthrough Example
- 9:20Evaluation
- 12:08Specific Example (Correct)
- 12:54Specific Example (Wrong)
- 13:40Specific Example (Fixed)
- 14:05Main Takeaways
related talks
13mGenetic Regex
38mProgram Synthesis: A Dream Realized?
15mAccelerating Rule-matching Systems with Learned Rankers
47mBig Ideas in Program Synthesis
16mJust-in-Time Learning for Bottom-Up Enumerative Synthesis
23mMembership Testing for Semantic Regular Expressions
01h 10mNeurosymbolic Program Synthesis: Bridging Perception and Reasoning in Real-World(…)
17mExplainable Program Synthesis by Localizing Specifications