{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T14:09:00Z","timestamp":1790431740250,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T00:00:00Z","timestamp":1591833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1917924"],"award-info":[{"award-number":["1917924"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100015089","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2889, N00014-19-1-2318"],"award-info":[{"award-number":["N00014-17-1-2889, N00014-19-1-2318"]}],"id":[{"id":"10.13039\/100015089","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,11]]},"DOI":"10.1145\/3385412.3386021","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:40:10Z","timestamp":1591494010000},"page":"780-793","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Fast graph simplification for interleaved Dyck-reachability"],"prefix":"10.1145","author":[{"given":"Yuanbo","family":"Li","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qirun","family":"Zhang","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Reps","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"POPL","author":"Chatterjee Krishnendu","year":"2018","unstructured":"Krishnendu Chatterjee, Bhavya Choudhary, and Andreas Pavlogiannis. 2018. Optimal Dyck reachability for data-dependence and alias analysis. PACMPL 2, POPL (2018), 30:1\u201330:30."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Swarat Chaudhuri. 2008. Subcubic algorithms for recursive state machines. In POPL. 159\u2013169.","DOI":"10.1145\/1328438.1328460"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349311"},{"key":"e_1_3_2_1_4_1","volume-title":"Scalable Flow-Sensitive Pointer Analysis for Java with Strong Updates. In ECOOP 2012 - Object-Oriented Programming - 26th European Conference, Beijing, China, June 11-16, 2012. Proceedings. 665\u2013687","author":"De Arnab","year":"2012","unstructured":"Arnab De and Deepak D\u2019Souza. 2012. Scalable Flow-Sensitive Pointer Analysis for Java with Strong Updates. In ECOOP 2012 - Object-Oriented Programming - 26th European Conference, Beijing, China, June 11-16, 2012. Proceedings. 665\u2013687."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277667"},{"key":"e_1_3_2_1_6_1","volume-title":"14th International Symposium, SAS 2007, Kongens Lyngby, Denmark, August 22-24, 2007, Proceedings. 265\u2013280","author":"Hardekopf Ben","year":"2007","unstructured":"Ben Hardekopf and Calvin Lin. 2007. Exploiting Pointer and Location Equivalence to Optimize Pointer Analysis. In Static Analysis, 14th International Symposium, SAS 2007, Kongens Lyngby, Denmark, August 22-24, 2007, Proceedings. 265\u2013280."},{"key":"e_1_3_2_1_7_1","volume-title":"Introduction to Formal Language Theory","author":"Harrison M. A.","unstructured":"M. A. Harrison. 1978. Introduction to Formal Language Theory. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA."},{"key":"e_1_3_2_1_8_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"1979","unstructured":"John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison-Wesley."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Wei Huang Yao Dong Ana Milanova and Julian Dolby. 2015. Scalable and precise taint analysis for Android. In ISSTA. 106\u2013117.","DOI":"10.1145\/2771783.2771803"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Vineet Kahlon. 2009. Boundedness vs. Unboundedness of Lock Chains: Characterizing Decidability of Pairwise CFL-Reachability for Threads Communicating via Locks. In LICS. 27\u201336.","DOI":"10.1109\/LICS.2009.45"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"John Kodumal and Alexander Aiken. 2004. The set constraint\/CFL reachability connection in practice. In PLDI. 207\u2013218.","DOI":"10.1145\/996841.996867"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2015.9"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/349214.349241"},{"key":"e_1_3_2_1_14_1","volume-title":"Program analysis via graph reachability. Information &amp","author":"Reps Thomas W.","year":"1998","unstructured":"Thomas W. Reps. 1998. Program analysis via graph reachability. Information & Software Technology 40, 11-12 (1998), 701\u2013726."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345137"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Thomas W. Reps Susan Horwitz and Shmuel Sagiv. 1995. Precise Interprocedural Dataflow Analysis via Graph Reachability. In POPL. 49\u201361.","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349310"},{"key":"e_1_3_2_1_18_1","volume-title":"Program Flow Analysis: Theory and Applications, Steven S","author":"Sharir Micha","unstructured":"Micha Sharir and Amir Pnueli. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, Steven S. Muchnick and Neil D. Jones (Eds.). Prentice-Hall, 189\u2013234."},{"key":"e_1_3_2_1_19_1","volume-title":"POPL","author":"Sp\u00e4th Johannes","year":"2019","unstructured":"Johannes Sp\u00e4th, Karim Ali, and Eric Bodden. 2019. Context-, flow-, and field-sensitive data-flow analysis using synchronized Pushdown systems. PACMPL 3, POPL (2019), 48:1\u201348:29."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Manu Sridharan and Rastislav Bod\u00edk. 2006. Refinement-based contextsensitive points-to analysis for Java. In PLDI. 387\u2013400.","DOI":"10.1145\/1133981.1134027"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Manu Sridharan Denis Gopan Lexin Shan and Rastislav Bod\u00edk. 2005. Demand-driven points-to analysis for Java. In OOPSLA. 59\u201376.","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Hao Tang Xiaoyin Wang Lingming Zhang Bing Xie Lu Zhang and Hong Mei. 2015. Summary-Based Context-Sensitive Data-Dependence Analysis in Presence of Callbacks. In POPL. 83\u201395.","DOI":"10.1145\/2676726.2676997"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Guoqing Xu Atanas Rountev and Manu Sridharan. 2009. Scaling CFL-Reachability-Based Points-To Analysis Using Context-Sensitive Must-Not-Alias Analysis. In ECOOP. 98\u2013122.","DOI":"10.1007\/978-3-642-03013-0_6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Dacong Yan Guoqing (Harry) Xu and Atanas Rountev. 2011. Demanddriven context-sensitive alias analysis for Java. In ISSTA. 155\u2013165.","DOI":"10.1145\/2001420.2001440"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Qirun Zhang Michael R. Lyu Hao Yuan and Zhendong Su. 2013. Fast algorithms for Dyck-CFL-reachability with applications to alias analysis. In PLDI. 435\u2013446.","DOI":"10.1145\/2491956.2462159"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Qirun Zhang and Zhendong Su. 2017. Context-sensitive datadependence analysis via linear conjunctive language reachability. In POPL. 344\u2013358.","DOI":"10.1145\/3009837.3009848"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Qirun Zhang Xiao Xiao Charles Zhang Hao Yuan and Zhendong Su. 2014. Efficient subcubic alias analysis for C. In OOPSLA. 829\u2013845.","DOI":"10.1145\/2660193.2660213"}],"event":{"name":"PLDI '20: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation","location":"London UK","acronym":"PLDI '20","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages"]},"container-title":["Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385412.3386021","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3385412.3386021","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3385412.3386021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:49Z","timestamp":1750199929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385412.3386021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,11]]},"references-count":27,"alternative-id":["10.1145\/3385412.3386021","10.1145\/3385412"],"URL":"https:\/\/doi.org\/10.1145\/3385412.3386021","relation":{},"subject":[],"published":{"date-parts":[[2020,6,11]]},"assertion":[{"value":"2020-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}