Recursive State Machine Guided Graph Folding for Context-Free Language Reachability
Abstract
Context-free language reachability (CFL-reachability) is a fundamental framework for program analysis. A large variety of static analyses can be formulated as CFL-reachability problems, which determines whether specific source-sink pairs in an edge-labeled graph are connected by a reachable path, i.e., a path whose edge labels form a string accepted by the given CFL. Computing CFL-reachability is expensive. The fastest algorithm exhibits a slightly subcubic time complexity with respect to the input graph size. Improving the scalability of CFL-reachability is of practical interest, but reducing the time complexity is inherently difficult.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 06, 2023
- Source ID
- 10.1145/3591233
Entities
People
- Qirun Zhang
- Shin Hwei Tan
- Yulei Sui
- Yuxiang Lei
Organizations
- Concordia University
- Defense Advanced Research Projects Agency
- Georgia Tech
- National Science Foundation
- University of New South Wales