{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:05:22Z","timestamp":1784199922893,"version":"3.55.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2022YFB3103900"],"award-info":[{"award-number":["2022YFB3103900"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Jiangsu Provincial Key R&D Program","award":["BG2024028"],"award-info":[{"award-number":["BG2024028"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62402474; 62132020; 62202452; HW2024006"],"award-info":[{"award-number":["62402474; 62132020; 62202452; HW2024006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,10,9]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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\u2014those 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.<\/jats:p>","DOI":"10.1145\/3763065","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:49:50Z","timestamp":1759999790000},"page":"416-443","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-3055-8929","authenticated-orcid":false,"given":"Chenghang","family":"Shi","sequence":"first","affiliation":[{"name":"Institute of Computing Technology, CAS, Beijing, China"},{"name":"University of Chinese Academy of Sciences, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0304-8942","authenticated-orcid":false,"given":"Dongjie","family":"He","sequence":"additional","affiliation":[{"name":"Chongqing University, Chongqing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-0931-8767","authenticated-orcid":false,"given":"Haofeng","family":"Li","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology, CAS, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4162-0404","authenticated-orcid":false,"given":"Jie","family":"Lu","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology, CAS, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4476-0541","authenticated-orcid":false,"given":"Lian","family":"Li","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology, CAS, Beijing, China"},{"name":"University of Chinese Academy of Sciences, Beijing, China"},{"name":"Zhongguancun Laboratory, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0380-3506","authenticated-orcid":false,"given":"Jingling","family":"Xue","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1177220"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_30"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1075382.1075387"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594299"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167515.1167488"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1985793.1985827"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158118"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","unstructured":"Swarat Chaudhuri. 2008. Subcubic algorithms for recursive state machines. In Proceedings of the 35th annual ACM SIGPLAN- SIGACT symposium on Principles of programming languages. 159\u2013169. doi:10.1145\/1328438.1328460","DOI":"10.1145\/1328438.1328460"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-44245-2_12"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02737-6_16"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297033"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","unstructured":"Ben Hardekopf and Calvin Lin. 2007. The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation. 290\u2013299. doi:10.1145\/1273442.1250767","DOI":"10.1145\/1273442.1250767"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3622832"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","unstructured":"Dongjie He Jingbo Lu and Jingling Xue. 2021. Context Debloating for Object-Sensitive Pointer Analysis. In 2021 36th IEEE\/ACM International Conference on Automated Software Engineering (ASE). 79\u201391. doi:10.1109\/ASE51524.2021.9678880","DOI":"10.1109\/ASE51524.2021.9678880"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2022.30"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","unstructured":"Dongjie He Jingbo Lu and Jingling Xue. 2024a. Artifact of \u201cA CFL-Reachability Formulation of Callsite-Sensitive Pointer Analysis with Built-In On-The-Fly Call Graph Construction\u201d. doi:10.5281\/zenodo.l1061891","DOI":"10.5281\/zenodo.l1061891"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2024.18"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41540-6_23"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656451"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563343"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","unstructured":"Yuxiang Lei Yulei Sui Ding Shuo and Qirun Zhang. 2022b. Artifact of \u201cTaming transitive redundancy for context-free language reachability\u201d. (2022). doi:10.5281\/zenodo.7066401","DOI":"10.5281\/zenodo.7066401"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","unstructured":"Yuxiang Lei Yulei Sui Shin Hwei Tan and Qirun Zhang. 2023a. Artifact of\u201cRecursive State Machine Guided Graph Folding for Context-Free Language Reachability\u201d. doi:10.5281\/zenodo.7787371","DOI":"10.5281\/zenodo.7787371"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591233"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025160"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ECOOP.2016.15"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","unstructured":"Yuanbo Li Qirun Zhang and Thomas Reps. 2020. Fast graph simplification for interleaved Dyck-reachability. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. 780\u2013793. doi:10.1145\/3385412.3386021","DOI":"10.1145\/3385412.3386021"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360574"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00049-9"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","unstructured":"Mehryar Mohri and Mark-Jan Nederhof. 2001. Regular Approximation of Context-Free Grammars through Transformation. Springer Netherlands Dordrecht 153\u2013163 doi:10.1007\/978-94-015-9719-7_6","DOI":"10.1007\/978-94-015-9719-7_6"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.3115\/980691.980716"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.3115\/1611533.1611535"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9470-7_12"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","unstructured":"Thomas Reps Susan Horwitz and Mooly Sagiv. 1995. Precise interprocedural dataflow analysis via graph reachability. In Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 49\u201361. doi:10.1145\/199448.199462","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/193173.195287"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349310"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","unstructured":"Chenghang Shi Dongjie He Haofeng Li Jie Lu Lian Li and Jingling Xue. 2025. Artifact of \"Fast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification\". doi:10.5281\/zenodo.16911404","DOI":"10.5281\/zenodo.16911404"},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3650212.3680346"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE56229.2023.00118"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","unstructured":"Chenghang Shi Haofeng Li Yulei Sui Jie Lu Lian Li and Jingling Xue. 2024b. PEARL: A Multi-Derivation Approach to Efficient CFL-Reachability Solving. IEEE Transactions on Software Engineering (2024). doi:10.1109\/TSE.2024.3437684","DOI":"10.1109\/TSE.2024.3437684"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563339"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192418"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","unstructured":"Manu Sridharan Stephen J Fink and Rastislav Bodik. 2007. Thin slicing. In Proceedings of the 28th ACM SIGPLAN conference on programming language design and implementation. 112\u2013122. doi:10.1145\/1250734.1250748","DOI":"10.1145\/1250734.1250748"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2018.2869336"},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","unstructured":"Tian Tan and Yue Li. 2023. Tai-e: A Developer-Friendly Static Analysis Framework for Java by Harnessing the Good Designs of Classics (ISSTA 2023). Association for Computing Machinery New York NY USA 1093\u20131105. doi:10.1145\/3597926.3598120","DOI":"10.1145\/3597926.3598120"},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062359"},{"key":"e_1_3_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2019.00091"},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037744"},{"key":"e_1_3_2_54_1","unstructured":"James O. Westgard. n.d.. Lesson 34: What is an acceptable CV?.https:\/\/westgard.com\/lessons\/z-stats-basic-statistics\/lesson34.html Accessed: 2025-01-12."},{"key":"e_1_3_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03013-0_6"},{"key":"e_1_3_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649862"},{"key":"e_1_3_2_57_1","doi-asserted-by":"publisher","unstructured":"Mihalis Yannakakis. 1990. Graph-theoretic methods in database theory. In Proceedings of the ninth ACM SIGACT-SIGMOD- SIGART symposium on Principles of database systems. 230\u2013242. doi:10.1145\/298514.298576","DOI":"10.1145\/298514.298576"},{"key":"e_1_3_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656400"},{"key":"e_1_3_2_59_1","doi-asserted-by":"publisher","unstructured":"Qirun Zhang Michael R Lyu Hao Yuan and Zhendong Su. 2013. Fast algorithms for Dyck-CFL-reachability with applications to alias analysis. In Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation. 435\u2013446. doi:10.1145\/2491956.2462159","DOI":"10.1145\/2491956.2462159"},{"key":"e_1_3_2_60_1","doi-asserted-by":"publisher","unstructured":"Qirun Zhang Xiao Xiao Charles Zhang Hao Yuan and Zhendong Su. 2014. Efficient subcubic alias analysis for C. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications. 829\u2013845. doi:10.1145\/2660193.2660213","DOI":"10.1145\/2660193.2660213"},{"key":"e_1_3_2_61_1","doi-asserted-by":"publisher","unstructured":"Xin Zheng and Radu Rugina. 2008. Demand-driven alias analysis for C. In Proceedings of the 35th annual ACM SIGPLAN- SIGACT symposium on Principles of programming languages. 197\u2013208. doi:10.1145\/1328438.1328464","DOI":"10.1145\/1328438.1328464"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:05:28Z","timestamp":1784196328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":60,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763065"],"URL":"https:\/\/doi.org\/10.1145\/3763065","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2024-10-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}