.png){kind=icon}
.png){kind=icon}
Return
Fast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification
.png){kind=icon}
PRE
AI
DOI：10.1145/3763065.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Context-free language (CFL) reachability is a critical framework for various program analyses, widely adopted despite its computational challenges due to cubic or near-cubic time complexity. This often leads to significant performance degradation in client applications. Notably, in real-world scenarios, clients typically require reachability information only for specific source-to-sink pairs, offering opportunities for targeted optimization. We introduce MOYE, an effective regularization-based graph simplification technique designed to enhance the performance of client-driven CFL-reachability analyses by pruning non-contributing edges-those that do not participate in any specified CFL-reachable paths. MOYE employs a regular approximation to ensure exact reachability results for all designated node pairs and operates linearly with respect to the number of edges in the graph. This lightweight efficiency makes MOYE a valuable pre-processing step that substantially reduces both computational time and memory requirements for CFL-reachability analysis, outperforming a recent leading graph simplification approach. Our evaluations with two prominent CFL-reachability client applications demonstrate that MOYE can substantially improve performance and reduce resource consumption.
Keywords:
CFL-Reachability
Graph Simplification
Journal
P
IF:
2.8
Papers:
308
Citations:
4.7K