Taming transitive redundancy for context-free language reachability
Abstract
Given an edge-labeled graph, context-free language reachability (CFL-reachability) computes reachable node pairs by deriving new edges and adding them to the graph. The redundancy that limits the scalability of CFL-reachability manifests as redundant derivations, i.e., identical edges can be derived multiple times due to the many paths between two reachable nodes. We observe that most redundancy arises from the derivations involving transitive relations of reachable node pairs. Unfortunately, existing techniques for reducing redundancy in transitive-closure-based problems are either ineffective or inapplicable to identifying and eliminating redundant derivations during on-the-fly CFL-reachability solving.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 31, 2022
- Source ID
- 10.1145/3563343
Entities
People
- Qirun Zhang
- Shuo Ding
- Yulei Sui
- Yuxiang Lei
Organizations
- Defense Advanced Research Projects Agency
- Georgia Tech
- University of Technology Sydney