Fast Graph Simplification for Interleaved-Dyck Reachability
Abstract
Many program-analysis problems can be formulated as graph-reachability problems. Interleaved Dyck language reachability ( InterDyck -reachability) is a fundamental framework to express a wide variety of program-analysis problems over edge-labeled graphs. The InterDyck language represents an intersection of multiple matched-parenthesis languages (i.e., Dyck languages). In practice, program analyses typically leverage one Dyck language to achieve context-sensitivity, and other Dyck languages to model data dependencies, such as field-sensitivity and pointer references/dereferences. In the ideal case, an InterDyck -reachability framework should model multiple Dyck languages simultaneously .
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- May 27, 2022
- Source ID
- 10.1145/3492428
Entities
People
- Qirun Zhang
- Thomas Reps
- Yuanbo Li
Organizations
- Defense Advanced Research Projects Agency
- Georgia Tech
- National Science Foundation
- Office of Naval Research
- University of Wisconsin–Madison