Recursive State Machine Guided Graph Folding for Context-Free Language Reachability
summary
An algorithm called graph folding GF identifies adjacent node pairs that are provably removable for CFL‑reachability by examining only their incoming and outgoing edges via correspondence to a recursive state machine, runs in linear time in nodes as a linear time preprocessing, and preserves reachability. Implementation on value‑flow and alias clients reduces nodes by 60.96% and 38.93% and edges by 42.67% and 35.61%, yielding 4.65× and 3.21× speedups and 57.35% and 65.19% memory reductions; artifacts are available.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:03Context-free reachability
- 3:33Recursive state machines
- 5:00Graph folding
- 8:30Over-approximation
- 9:57Algorithm implementation
- 10:41Value flow performance
- 11:25Alias analysis performance
- 12:08Memory reduction
- 12:52Q&A
related talks
17mIterative-Epoch Online Cycle Elimination for Context-Free Language Reachability
14mFast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification
19mContext-Free Language Reachability via Skewed Tabulation
24mBounded Treewidth, Multiple Context-Free Grammars, and Downward Closures
17mA Better Approximation for Interleaved Dyck Reachability
16mAutomatically Deriving Control-Flow Graph Generators from Operational Semantics
15mFaster Reachability Analysis for LR(1) Parsers
15mDetecting and explaining (in-)equivalence of context-free grammars