{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:21:04Z","timestamp":1760059264122,"version":"build-2065373602"},"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":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0304-8942","authenticated-orcid":false,"given":"Dongjie","family":"He","sequence":"additional","affiliation":[{"name":"Chongqing University, Chongqing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1177220"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_30"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1075382.1075387"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594299"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167515.1167488"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1985793.1985827"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158118"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328460"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Shuo Ding and Qirun Zhang. 2023. Mutual Refinements of Context-Free Language Reachability. In Static Analysis Manuel V. Hermenegildo and Jos\u00e9 F. Morales (Eds.). Springer Nature Switzerland Cham. 231\u2013258. isbn:978-3-031-44245-2 https:\/\/doi.org\/10.1007\/978-3-031-44245-2_12 10.1007\/978-3-031-44245-2_12","DOI":"10.1007\/978-3-031-44245-2_12"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02737-6_16"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297033"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250767"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3622832"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE51524.2021.9678880"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2022.30"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Dongjie He Jingbo Lu and Jingling Xue. 2024. Artifact of \u201cA CFL-Reachability Formulation of Callsite-Sensitive Pointer Analysis with Built-In On-The-Fly Call Graph Construction\u201d. https:\/\/doi.org\/10.5281\/zenodo.11061891 10.5281\/zenodo.11061891","DOI":"10.5281\/zenodo.11061891"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2024.18"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41540-6_23"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656451"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563343"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","unstructured":"Yuxiang Lei Yulei Sui Ding Shuo and Qirun Zhang. 2022. Artifact of \u201cTaming transitive redundancy for context-free language reachability\u201d. https:\/\/doi.org\/10.5281\/zenodo.7066401 10.5281\/zenodo.7066401","DOI":"10.5281\/zenodo.7066401"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7787371"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591233"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025160"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2016.15"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386021"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360574"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00049-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9719-7_6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.3115\/980691.980716"},{"volume-title":"Context-free parsing through regular approximation. FSMNLP \u201909","author":"Nederhof Mark-Jan","key":"e_1_2_1_33_1","unstructured":"Mark-Jan Nederhof. 1998. Context-free parsing through regular approximation. FSMNLP \u201909. Association for Computational Linguistics, USA. 13\u201324. isbn:9757679348 https:\/\/doi.org\/doi\/10.5555\/1611533.1611535"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9470-7_12"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/193173.195287"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349310"},{"key":"e_1_2_1_39_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\". https:\/\/doi.org\/10.5281\/zenodo.16911404 10.5281\/zenodo.16911404","DOI":"10.5281\/zenodo.16911404"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3650212.3680346"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE56229.2023.00118"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2024.3437684"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563339"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192418"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250748"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2018.2869336"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597926.3598120"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062359"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2019.00091"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037744"},{"key":"e_1_2_1_53_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_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03013-0_6"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649862"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298576"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656400"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462159"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660213"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","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":[[2025,10,9]],"date-time":"2025-10-09T17:46:17Z","timestamp":1760031977000},"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":[{"type":"electronic","value":"2475-1421"}],"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"}}]}}