Fast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification
summary
MoYe is a regularization-based graph simplification that prunes edges that cannot lie on any CFL-reachable source-to-sink path by over-approximating the context-free grammar with a regular language, compiling that to a DFA and computing configuration trains to mark contributing edges. It runs as a linear pre-analysis in the number of edges, is implemented in Python 3 and LVM, yields graph-size reductions of ~60–70%, and speeds two client analyses by about 10× and 15× while cutting memory use substantially.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 1:05CFL-reachability framework
- 4:40Client-driven simplification goals
- 6:25Regularization via automaton
- 9:18Evaluation results
- 11:48Conclusion
- 12:08Q&A
related talks
15mRecursive State Machine Guided Graph Folding for Context-Free Language Reachability
17mIterative-Epoch Online Cycle Elimination for Context-Free Language Reachability
31mIndexing the Extended Dyck-CFL Reachability for Context-Sensitive Program Analysis
17mA Better Approximation for Interleaved Dyck Reachability
19mContext-Free Language Reachability via Skewed Tabulation
15mFaster Reachability Analysis for LR(1) Parsers
24mBounded Treewidth, Multiple Context-Free Grammars, and Downward Closures
21mUniversal High-Performance CFL-Reachability via Matrix Multiplication